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\ge 1$ allgemein gilt:
$x_n=(3\cdot n+1{)}^2$, für alle $n\ge 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$
$x_0=(3\cdot 0+1{)}^2=1$

n = 1 (k = 0):

$x_1=x_0+18\cdot k+15=1+0+15=16$
$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$
$x_2=(3\cdot n+1{)}^2=(3\cdot 2+1{)}^2=49$

Der Anfang ist also richtig!

Induktionsschritt

$n\to 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.