Rekursive Folgen | MathePrisma

Der Domino-Day zeigt auf spektakuläre Weise, dass es praktisch möglich ist, Millionen von Dominosteinen umkippen zu lassen. Das erfordert Nerven, ein "ruhiges Händchen" und nimmt eine ganz lange Vorbereitungszeit in Anspruch. Mit Hilfe der vollständigen Induktion schaffst du es theoretisch in Minuten, unendlich viele Dominosteine kippen zu lassen. Du brauchst sie nicht einmal aufzustellen.

Das Prinzip beim Domino

Voraussetzung:	Der Abstand zwischen zwei Steinen ist kleiner als die Höhe des vorderen.
Behauptung:	Alle Dominosteine kippen. (im Fernsehen klappt's nicht immer, bei uns schon)

Es gibt nur zwei spannende Punkte:

Kippt der erste?

Kippt jeder durch den vorherigen?

Der Rest ist dann eigentlich langweilig...

Beweis:

Induktions- anfang:

Der erste Stein kippt, denn er wird manuell angestoßen.

Induktions- voraussetzung:

k Steine sind bereits gekippt.

Induktions- schluss:

Von k nach k+1 schließen.

Induktions- beweis:

Betrachte k+1 Steine: Nach Ind.-Vor. sind bereits die Steine 1,2,3,...,k gekippt. Da der Abstand zwischen dem k-ten und dem (k+1)-ten kleiner als die Höhe des k-ten ist, stößt der k-te bei dem Kippen den (k+1)-ten an. Da der (k+1)-te angestoßen wird, kippt er ebenfalls. Also kippen k+1 Steine.

Im Fernsehen klappt's nicht immer, bei uns schon!

Durch den Induktionsschluss wissen wir

Da n dabei beliebig groß werden kann, haben wir damit bewiesen, dass alle Dominosteine kippen.

Das Prinzip

Begriffsnetz

Vor.:

Welche Voraussetzungen gelten
(z.B. eine Rekursionsformel)?

Beh.:

Stelle eine zu beweisende Behauptung auf (z.B. eine explizite Formel).

Beweis:

Ind.-Anf.:

Zeige, dass die Behauptung für das kleinste k wahr ist.

Ind.-Vor.:

Die Behauptung gilt für alle Zahlen $\leq$ k.

Ind.-Schluss:

Wie hangelst du dich hoch (von k nach k+1)?

Ind.-Bew.:

Zeige die Gültigkeit der Behauptung für k+1 unter Verwendung der gültigen Behauptung für k und der Voraussetzung.

Folgt aus der Gültigkeit der Behauptung für ein k stets die Gültigkeit von k+1, dann gilt die Behauptung für alle n $\in \mathbb{N}$ .

Beispiel
Die ungeraden Zahlen

Vor.:

M(1)=1 und M(n)=M(n-1)+2 für alle n>1

Beh.:

M(n)=1+2·(n-1)

Beweis:

Ind.-Anf.:

M(1)=1+2·(1-1)=1 ist wahr.

Ind.-Vor.:

M(k)=1+2·(k-1)

Ind.-Schluss:

Von k nach k+1 schließen.

Ind.-Bew.:

M(k+1)
=M(k)+2		(nach Voraussetzung)
=(1+2·(k-1))+2 =1+2·k-2+2 =1+2·k		(nach Ind.-Vor.)

Damit gilt M(n)=1+2·(n-1) für alle n.

Beispiel
Die Quadratzahlen

Vor.:

M(1)=1 und M(n)=M(n-1)+(2n-1) für alle n>1

Beh.:

M(n)=n²

Beweis:

Ind.-Anf.:

M(1)=1 $^2$ = 1 ist wahr.

Ind.-Vor.:

M(k)=k $^2$

Ind.-Schluss:

Von k nach k+1 schließen.

Ind.-Bew.:

M(k+1)
=M(k)+(2(k+1)-1)		(nach Voraussetzung)
=k $^2$ + (2(k+1)-1) =k $^2$ +2k+1 =(k+1) $^2$		(nach Ind.-Vor.)

Damit gilt M(n)=n $^2$ für alle n.

Beispiel
Türme von Hanoi
(gibt's später)

Vor.:

M(1)=1 und M(n)=2M(n-1)+1 für alle n>1

Beh.:

M(n)=2ⁿ-1

Beweis:

Ind.-Anf.:

M(1)=2 $^1$ -1=1 ist wahr.

Ind.-Vor.:

M(k)=2 $^k$ - 1

Ind.-Schluss:

Von k nach k+1 schließen.

Ind.-Bew.:

M(k+1)
=2·M(k)+1		(nach Voraussetzung)
=2·(2 $^k$ -1)+1 =2·2 $^k$ -2+1 =2 $^{(k+1)}$ - 1		(nach Ind.-Vor.)

Damit gilt M(n)=2 $^n$ -1 für alle n.

Rekursive Folgen (Begriffsnetz)