TU Wien:Mathematik 1 UE (diverse)/Übungen WS10/Beispiel 9

Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge $x_{0}=1$ und $x_{k+1}=x_{k}+18\cdot k+15$ für $k\geq 1$ allgemein gilt:
$x_{n}=(3\cdot n+1)^{2}$, für alle $n\geq 0$

Lösungsvorschlag

Induktionsvorraussetzung

$x_{n}=(3\cdot n+1)^{2}$
ausquadriert damit wir uns später beim vergleichen einfacher tun:

$x_{n}=9\cdot n^{2}+6\cdot n+1$

Überprüfung Induktionsanfang

n = 0:

$x_{0}=1\qquad$
$x_{0}=(3\cdot 0+1)^{2}=1$

n = 1 (k = 0):

$x_{1}=x_{0}+18\cdot k+15=1+0+15=16\qquad$
$x_{1}=(3\cdot n+1)^{2}=(3\cdot 1+1)^{2}=16$

n = 2 (k = 1):

$x_{2}=x_{1}+18\cdot k+15=16+18\cdot 1+15=49\qquad$
$x_{2}=(3\cdot n+1)^{2}=(3\cdot 2+1)^{2}=49$

Der Anfang ist also richtig!

Induktionsschritt

$n\rightarrow n+1$

daraus folgt die Induktionsbehauptung, indem man für jedes n in der Induktionsvorraussetzung n+1 einsetzt

Induktionsbehauptung

$x_{n+1}=(3\cdot (n+1)+1)^{2}$

Jetzt muss man zeigen, dass sich das wieder auf die Vorraussetzung zurückführen lässt. Dazu vereinfachen wir erst mal die Behauptung
$x_{n+1}=(3\cdot (n+1)+1)^{2}=(3n+4)^{2}$
Als nächstes benutzen wir die rekursive Darstellung der Folge (das im Index ein k steht, stört nicht weiter; Variabelnamen sind geduldig)
$x_{n+1}=x_{n}+18\cdot n+15$
in beiden Fällen haben wir ein $x_{n+1}$, wodurch wir die beiden Formeln gleichsetzen kann
$(3\cdot n+4)^{2}=x_{n}+18\cdot n+15$
$9\cdot n^{2}+24\cdot n+16=x_{n}+18\cdot n+15$
$9\cdot n^{2}+6\cdot n+1=x_{n}$
Wie man sieht entspricht das der Induktionsvorraussetzung, wodurch die Behauptung bewiesen ist.