TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 14

Aus VoWi
Zur Navigation springen Zur Suche springen

Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge x_{1}=1 und x_{k+1}= x_{k} + 8k für 1 \leq k allgemein gilt:

x_{n}= (2n -1)^2, für alle 1 \leq n

Lösungsvorschlag[Bearbeiten]

x_{k+1}=x_m~+~8k

~\Rightarrow x_k - x_{k-1}=8(k-1) ... (1)

~\Rightarrow x_{k-1} - x_{k-2}=8(k-2) ... (2)

\Rightarrow x_2-x_1=8~x |.........(k-1)

\Rightarrow(1)+(2)+.......(k-1)

x_k-x_{k-1}+x_{k-1}-x_{k-2}.........x_3-x_2+x_2-x_1

8[(k-2)+(k-1)+.....+2+1]

Links: x_k-x_1

Rechts: 8[\frac{1+(k-1)}{2}~(k-1)]

=4k(k-1)

4k^2-4k

\Rightarrow x_k=4k^2-4k+x_1

\Rightarrow x_k=4k^2-4k+1

\Rightarrow x_k=(2k-1)^2

Lösungsvorschlag von Jacko[Bearbeiten]

Induktionsanfang
k=1 : n=2 x_{2}= 1+8 = 9
x_{2}= (4-1)^2 = 9

damit ist der Induktionsanfang bewiesen (9=9)
Induktionsschritt
- Induktionsvorraussetzung
x_{n}= (2n -1)^2, für alle 1 \leq n

- Induktionsbehauptung - n -> n+1

zuerst wird folgender Term für n+1 berechnet: x_{n}= (2n -1)^2
x_{n+1}= (2(n+1) -1)^2 = (2n+2-1)^2 = (2n+1)^2

jetzt wird der zweite Term für n+1 berechnet: x_{k+1}= x_{k} + 8k
x_{n+1}= x_{n} + 8n = (2n -1)^2 + 8n = 4n^2 - 4n + 1 + 8n = 4n^2 + 4n + 1 = (2n+1)^2

(2n+1)^2 = (2n+1)^2
q.e.d.

Lösungsvorschlag von Tonico[Bearbeiten]

Zu zeigen ist, dass für x1 = 1 und xk+1 = xk + 8k für k ≥ 1 allgemein gilt:
xn = (2n - 1)2, für alle n ≥ 1.

IV: Sei P(n) die Aussage
xn+1 = xn + 8n, für alle n ≥ 1.

IA: P(1) ist wahr denn
x2 = (2·2 - 1)2 = 9 und
x1+1=x1 + 8·1 = (2·1 - 1)2 + 8·1 = 9.

IS: Aus P(n) folgt P(n + 1) ist gleichbedeutend mit
xn+1 = (2(n + 1) - 1)2 = 4n2 + 4n + 1 = (4n2 - 4n + 1) + 8n = (2n - 1)2 + 8n = xn + 8n

Daraus folgt, dass für alle n ≥ 1 die Aussage P(n) wahr ist.