TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS13/Beispiel 78

Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge $x_{0}=1$ und $x_{k+1}=ax_{k}+b$ für $k\geq 0$ (wobei $a,b\in \mathbb {R}$ ) allgemein gilt:
$x_{n}=a^{n}+b{a^{n}-1 \over a-1}$, für alle $n\geq 0$

Lösungsansatz

Induktionsanfang
k=0 ; n=1
$x_{1}=a*1+b=a+b$
$x_{1}=a^{1}+b{a^{1}-1 \over a-1}=a+b$

damit ist der Induktionsanfang bewiesen (a+b=a+b)

Induktionsschritt
- Induktionsvorraussetzung
$x_{n}=a^{n}+b{a^{n}-1 \over a-1}$, für alle $n\geq 0$

- Induktionsbehauptung - n -> n+1

$x_{n+1}=a^{n}+1+b{a^{n}+1-1 \over a-1}$

Für $x_{n+1}$ einsetzen:

$ax_{n}+b=a^{n}+1+b{a^{n}+1-1 \over a-1}$

Für $x_{n}$ einsetzen:

$a*(a^{n}+b{a^{n}-1 \over a-1})+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Lösung mittels geometrischer Reihe

Aichingm (Diskussion) 22:06, 27. Mär. 2017 (CEST)

Hilfreiches

Geometrische Reihe:

• Für n: $\sum _{k=0}^{n}q^{k}=(q^{0}+q^{1}+q^{2}+...+q^{n})={q^{n+1}-1 \over q-1}$
  
  
• Für n-1: $\sum _{k=0}^{n-1}q^{k}=(q^{0}+q^{1}+q^{2}+...+q^{n-1})={q^{n}-1 \over q-1}$

Induktionsanfang
Laut Angabe: $x_{0}=1$

$x_{1}=a*x_{0}+b=a*1+b=a+b$ und

$y_{1}=a^{n}+b{a^{n}-1 \over a-1}=a^{1}+b{a^{1}-1 \over a-1}=a+b{1 \over 1}=a+b$

$=>x=y$

Induktionsvorraussetzung
$a*x_{k}+b=a^{n}+b{a^{n}-1 \over a-1}$ für $k=n-1$

Induktionsbehauptung
n zu n+1

$a*x_{n}+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Für $x_{n}$: $a^{n}+b{a^{n}-1 \over a-1}$ einsetzen:

$a*(a^{n}+b{a^{n}-1 \over a-1})+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

a in die Klammer multiplizieren:

$a^{n+1}+ab{a^{n}-1 \over a-1}+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Geometrische Reihe einsetzen:
$a^{n+1}+ab(q^{0}+q^{1}+q^{2}+...+q^{n-1})+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

a in die geometrische Reihe multiplizieren:
$a^{n+1}+b(q^{1}+q^{2}+q^{3}+...+q^{n})+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Ein b zur geometrische Reihe addieren:
$a^{n+1}+b(1+q^{1}+q^{2}+q^{3}+...+q^{n})=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Geometrische Reihe zurück einsetzen:
$a^{n+1}+b{a^{n+1}-1 \over a-1}=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Q.E.D.

Lösung mittels Umformung

Aichingm (Diskussion) 22:06, 27. Mär. 2017 (CEST)

Induktionsanfang
Laut Angabe: $x_{0}=1$

$x_{1}=a*x_{0}+b=a*1+b=a+b$ und

$y_{1}=a^{n}+b{a^{n}-1 \over a-1}=a^{1}+b{a^{1}-1 \over a-1}=a+b{1 \over 1}=a+b$

$=>x=y$

Induktionsvorraussetzung
$a*x_{k}+b=a^{n}+b{a^{n}-1 \over a-1}$ für $k=n-1$

Induktionsbehauptung
n zu n+1

$a*x_{n}+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Für $x_{n}$: $a^{n}+b{a^{n}-1 \over a-1}$ einsetzen:

$a*(a^{n}+b{a^{n}-1 \over a-1})+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

a in die Klammer multiplizieren:

$a^{n+1}+ab{a^{n}-1 \over a-1}+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

a in den Bruch multiplizieren:
$a^{n+1}+b{a^{n+1}-a \over a-1}+b=a^{n+1}+b{a^{n+1}-1 \over a-1}$

b herausheben:
$a^{n+1}+b({a^{n+1}-a \over a-1}+{1 \over 1})=a^{n+1}+b{a^{n+1}-1 \over a-1}$

weiter gleich:
$a^{n+1}+b({a^{n+1}-a \over a-1}+{a-1 \over a-1})=a^{n+1}+b{a^{n+1}-1 \over a-1}$

weiter gleich:
$a^{n+1}+b{a^{n+1}-a+a-1 \over a-1}=a^{n+1}+b{a^{n+1}-1 \over a-1}$

weiter gleich:
$a^{n+1}+b{a^{n+1}-1 \over a-1}=a^{n+1}+b{a^{n+1}-1 \over a-1}$

Q.E.D.