TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 14

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$

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Lösungsvorschlag

$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

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

Zu zeigen ist, dass für x₁ = 1 und x_k+1 = x_k + 8k für k ≥ 1 allgemein gilt:
x_n = (2n - 1)², für alle n ≥ 1.

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

IA: P(1) ist wahr denn
x₂ = (2·2 - 1)² = 9 und
x₁₊₁=x₁ + 8·1 = (2·1 - 1)² + 8·1 = 9.

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

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