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}=a{x}_k+b$ für $k\ge 0$ (wobei $a,b\in ℝ$ ) allgemein gilt:
$x_n=a^n+b\frac{a^n-1}{a-1}$, für alle $n\ge 0$

Lösungsansatz

Induktionsanfang
k=0 ; n=1
$x_1=a\ast 1+b=a+b$
$x_1=a^1+b\frac{a^1-1}{a-1}=a+b$

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

Induktionsschritt
- Induktionsvorraussetzung
$x_n=a^n+b\frac{a^n-1}{a-1}$, für alle $n\ge 0$

- Induktionsbehauptung - n -> n+1

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

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

$a{x}_n+b=a^n+1+b\frac{a^n+1-1}{a-1}$

Für $x_n$ einsetzen:

$a\ast (a^n+b\frac{a^n-1}{a-1})+b=a^{n+1}+b\frac{a^{n+1}-1}{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+\mathrm{...}+q^n)=\frac{q^{n+1}-1}{q-1}$
  
  
• Für n-1: $\sum _{k=0}^{n-1}{q}^k=(q^0+q^1+q^2+\mathrm{...}+q^{n-1})=\frac{q^n-1}{q-1}$

Induktionsanfang
Laut Angabe: $x_0=1$

$x_1=a\ast x_0+b=a\ast 1+b=a+b$ und

$y_1=a^n+b\frac{a^n-1}{a-1}=a^1+b\frac{a^1-1}{a-1}=a+b\frac{1}{1}=a+b$

$=>x=y$

Induktionsvorraussetzung
$a\ast x_k+b=a^n+b\frac{a^n-1}{a-1}$ für $k=n-1$

Induktionsbehauptung
n zu n+1

$a\ast x_n+b=a^{n+1}+b\frac{a^{n+1}-1}{a-1}$

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

$a\ast (a^n+b\frac{a^n-1}{a-1})+b=a^{n+1}+b\frac{a^{n+1}-1}{a-1}$

a in die Klammer multiplizieren:

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

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

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

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

Geometrische Reihe zurück einsetzen:
$a^{n+1}+b\frac{a^{n+1}-1}{a-1}=a^{n+1}+b\frac{a^{n+1}-1}{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\ast x_0+b=a\ast 1+b=a+b$ und

$y_1=a^n+b\frac{a^n-1}{a-1}=a^1+b\frac{a^1-1}{a-1}=a+b\frac{1}{1}=a+b$

$=>x=y$

Induktionsvorraussetzung
$a\ast x_k+b=a^n+b\frac{a^n-1}{a-1}$ für $k=n-1$

Induktionsbehauptung
n zu n+1

$a\ast x_n+b=a^{n+1}+b\frac{a^{n+1}-1}{a-1}$

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

$a\ast (a^n+b\frac{a^n-1}{a-1})+b=a^{n+1}+b\frac{a^{n+1}-1}{a-1}$

a in die Klammer multiplizieren:

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

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

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

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

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

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

Q.E.D.