pathterminuspages/brkmnd.dk/aboutcontactabout me

Øvelser 1.2.4

[Datalogi/Logic in Computer Science (Huth,Ryan)/Kapitel 1]

Opgave 7

Induktionsopgaver.

a) Vis at $$(2 \cdot 1 - 1) + (2 \cdot 2 - 1) + ... + (2 \cdot n - 1) = n^2$$ Induktionsstart: $$ 2 \cdot 1 - 1 = 1 = 1^2 $$ Induktionsskridt:
Lad $venstresiden = x$
Lad $x = n^2$ $$ x + (2(n + 1) - 1) = n^2 + (2(n + 1) - 1) = \\ n^2 + 2n + 2 - 1 = n^2 + 2n + 1 = (n + 1)^2 $$ Og vi har vist hvad vi skulle.

b) Lad k og l være naturlige tal. Vi siger at $l$ deler $k$ hvis der eksisterer et naturligt tal $p$ så $k = pl$. Vis at $$ 7 \mid 11^n - 4^n, \forall n \ge 1 $$ Vi skal bruge et lille lemma: $$ a \mid b \lor a \mid c \Rightarrow a \mid bc \\ bevisV : a = bp \Rightarrow ac = bpc: a, b, c, p \in \mathbb{N} $$ Da $c \in \mathbb{N}$, gælder $a \mid ac$.
bevisH: $$a = cp \Rightarrow ab = cpb$$ Da $b \in \mathbb{N}$, gælder $a \mid ab$
Og endnu et:
$$ a | b \land a | c \Rightarrow a | b + c $$ Bevis: $$ ap = b \land aq = c \Rightarrow b + c = ap + aq = a(p + q) $$ Bevis:
Induktionsstart: $$ 11^1 - 4^1 = 7 $$ som deles af $7$
Induktionsskridt:
Lad $7 | 11^n - 4^n$ $$ 11^{n + 1} - 4^{n + 1} = \\ 11 \cdot 11^n - 4 \cdot 4^n = \\ 4(11^n - 4^n) + 7 \cdot 11^n $$ af lemmaerne og antagelsen følger: $$ 7 | 4(11^n - 4^n) \land 7 | 7 \cdot 11^n \Rightarrow 7 | 4(11^n - 4^n) + 7 \cdot 11^n $$ Og vi har vist det vi skulle.

c) Vis at: $$1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$$ Bevis: Induktionsstart: $$ 1^2 = \frac{2 .sdot 3}{6} = 1 $$ Induktionsskridt:
Lad venstreside være $x$ Lad højreside være $y$
Lad $x = y$ $$ x + (n + 1)^2 = y + (n + 1)^2 = \\ \frac{n(n + 1)(2n + 1)}{6} + \frac{6(n + 1)^2}{6} = \\ \frac{2n^3 + n^2 + 2n^2 + n + 6n^2 + 6 + 12n}{6} = \\ \frac{(2n^3 + 7n^2 + 6n) + (2n^2 + 7n + 6)}{6} = z \\ $$ Herfra kan vi regne følgende: $$ n(n + 2)(2(n + 1) + 1) = \\ 2n^3 + 3n^2 + 4n^2 + 6n = \\ 2n^3 + 7n^2 + 6n $$ og $$ (n + 2)(2(n + 1) + 1) = \\ (n + 2)(2n + 3) = 2n^2 + 3n + 4n + 6 = \\ 2n^2 + 7n + 6 $$ Og vi får altså: $$ z = \frac{n(n + 2)(2(n + 1) + 1) + (n + 2)(2(n + 1) + 1)}{6} \Rightarrow \\ z = \frac{(n + 1)(n + 2)(2(n + 1) + 1)}{6} $$

d) Vis at (basecase: n = 4): $$2^n \ge n + 12$$ Bevis:
Induktionsstart: $$ 2^4 = 16 \ge 4 + 12 = 16 $$ Induktionsskridt:
Lad $2^n \ge n + 12$ $$ 2^n \ge n + 12 \Rightarrow \\ 2^{n + 1} \ge 2n + 24 \gt 2n + 13 \gt n + 13 = (n + 1) + 12 $$ De sidste par ligheder følger af at $n \gt 1$. For $n = 3$ fås $8 \ge 3 + 12 = 15$ hvilket er løgn.

e) Et posthus sælger kun 2¢ og 3¢ frimærker. Vis at enhver porto på 2¢ eller derover kan betales med frimærker fra dette posthus. Istedet for at bruge hintet kan vi løse opgaven på følgende måde:
En porto større end 2¢ kan være lige eller ulige. For lige skriver vi 2n, n \in \mathbb{N}. For ulige skriver vi 2n + 1, n \in \mathbb{N}. - Er portoen lige, frankeres med n 2¢ mærker. - Er portoen ulige og givet ved m = 2n + 1, frankeres med : 2(n - 1) + 2 + 1 = 2(n - 1) + 3 dvs. (n - 1) 2¢ mærker og 1 3¢ mærke.

f) Udeladt for nu.

Opgave 8

Denne opgave handler om Fibonaccital.
Lad $F_1 = 1, F_2 = 1 og F_{n + 1} = F_n + F_{n - 1}$ for alle $n \ge 2$. Sådan er Fibonaccital defineret.
Vis at $2 | F_{3n}, n \ge 1$.
Lemma: $$ ulige + lige = ulige $$ bevis: $2n + 2m + 1 = 2(m + n) + 1$ $$ lige + lige = lige $$ bevis: $2n + 2m = 2(m + n)$ $$ ulige + ulige = lige $$ bevis: $2n + 1 + 2m + 1 = 2(m + n + 1)$

Bevis:
Induktionsstart: $$ F_3 = 1 + 1 = 2 \Rightarrow 2 | F_3 $$ Induktionsskridt:
Lad $F_{3n}$ være lige.
Vi får: $F_{3(n + 1)} = F_{3n + 3} = F_{3n + 1} + F_{3n + 2}$
Derudover: $F_{3n + 2} = F_{3n} + F_{3n + 1}$
Lad nu $F_{3n + 1}$ være ulige.
Da er $F_{3n + 2} = F_{3n + 1} + F_{3n}$ ulige ifølge lemmaet.
Og $F_{3n + 3}$ er lige.

Lad $F_{3n + 1}$ være lige.
Da er $F_{3n + 2} = F_{3n + 1} + F_{3n}$ lige ifølge lemmaet.
Og $F_{3n + 3}$ er lige.

Opgave 10

Vis (at der er fejl i):

$$ n^2 + 5n + 1 er lige for alle n \ge 1 $$

a) Induktionsstarten : $1 + 5 + 1 = 7$ - som ikke er lige! Starten fejler.

b) ...

c) ...

d) Vis at udsagnet er ulige for $n \ge 1$.
Bevis:
Induktionsstart: $$ 1^2 + 5 + 1 = 7 $$ som er ulige.

Induktionsskridt:
Lad $a_n = n^5 + 5n + 1$ være ulige.
Nu fås: $$ a_{n + 1} = (n + 1)^2 + 5(n + 1) + 1 = \\ n^2 + 1 + 2n + 5 + 5n + 1 = \\ (n^2 + 5n + 1) + 2n + 6 = a_n + 2(n + 3) $$ og af lemmaerne fra sidste opgave følger at $a_{n + 1}$ er ulige.

CommentsGuest Name:Comment: