TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/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\le k$ allgemein gilt:

$x_n=(2n-1{)}^2$, für alle $1\le 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)\mathrm{...}(1)$

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

$\Rightarrow x_2-x_1=8x|\mathrm{.........}(k-1)$

$\Rightarrow (1)+(2)+\mathrm{.......}(k-1)$

$x_k-x_{k-1}+x_{k-1}-x_{k-2}\mathrm{.........}{x}_3-x_2+x_2-x_1$

$8[(k-2)+(k-1)+\mathrm{.....}+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\le 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.