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.
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.
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.