Vollständige Induktion - Versionsgeschichte

Administrator am 26. Januar 2026 um 11:50 Uhr

2026-01-26T11:50:43Z

← Nächstältere Version		Version vom 26. Januar 2026, 12:50 Uhr
Zeile 1:		Zeile 1:
	~~__INDEX__~~
	__NOTOC__		__NOTOC__
	Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage <br />		Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage <br />
Zeile 394:		Zeile 393:
	*[https://www.emath.de/Referate/induktion-aufgaben-loesungen.pdf Aufgabensammlung von Rainer Müller, PDF-Datei]		*[https://www.emath.de/Referate/induktion-aufgaben-loesungen.pdf Aufgabensammlung von Rainer Müller, PDF-Datei]
	*[https://www.youtube.com/watch?v=JirX7ssZ74s BrainFAQ]		*[https://www.youtube.com/watch?v=JirX7ssZ74s BrainFAQ]


	~~[[Kategorie:Seiten, die indexiert werden können]]~~

Administrator: /* Beispiel 2: Aufsummierung von Kubikzahlen */

2024-12-22T20:36:38Z

Beispiel 2: Aufsummierung von Kubikzahlen

← Nächstältere Version		Version vom 22. Dezember 2024, 21:36 Uhr
Zeile 218:		Zeile 218:
	<math>k^4+2k^3+k^2+4k^3+12k^2+12k+4 ~ = ~ k^4+2k^3+k^2+4k^3+12k^2+12k+4</math> <br />		<math>k^4+2k^3+k^2+4k^3+12k^2+12k+4 ~ = ~ k^4+2k^3+k^2+4k^3+12k^2+12k+4</math> <br />

	q.e.d. ~~<br />~~<br /><br />		q.e.d. <br /><br />

	=== Beispiel 3: Teilbarkeiten (I) ===		=== Beispiel 3: Teilbarkeiten (I) ===

Administrator: /* Induktionsschluss */

2024-12-22T20:35:55Z

Induktionsschluss

← Nächstältere Version		Version vom 22. Dezember 2024, 21:35 Uhr
Zeile 295:		Zeile 295:
	Also ist der gesamte Ausdruck durch 5 teilbar. <br />		Also ist der gesamte Ausdruck durch 5 teilbar. <br />

	q.e.d. <br /><br />~~<br />~~		q.e.d. <br /><br />


	=== Beispiel 5: Beweis einer Ungleichung ===		=== Beispiel 5: Beweis einer Ungleichung ===

Administrator: /* Induktionsanfang */

2024-12-22T20:35:07Z

Induktionsanfang

← Nächstältere Version		Version vom 22. Dezember 2024, 21:35 Uhr
Zeile 132:		Zeile 132:

	<u>Wichtig</u>: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere <br />		<u>Wichtig</u>: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere <br />
	wertlos und der Beweis ist nicht erbracht. ~~<br />~~<br /><br />		wertlos und der Beweis ist nicht erbracht. <br /><br />

	=== Beispiel 2: Aufsummierung von Kubikzahlen ===		=== Beispiel 2: Aufsummierung von Kubikzahlen ===

Administrator: /* Beispiel 5: Beweis einer Ungleichung */

2024-12-22T20:34:23Z

Beispiel 5: Beweis einer Ungleichung

← Nächstältere Version		Version vom 22. Dezember 2024, 21:34 Uhr
Zeile 309:		Zeile 309:
	<math>=,</math><math> ~ ></math> und <math>\geq</math> auftreten. Da in der Mitte (in der Induktionsvoraussetzung) ein "<math>></math>" steht, <br />		<math>=,</math><math> ~ ></math> und <math>\geq</math> auftreten. Da in der Mitte (in der Induktionsvoraussetzung) ein "<math>></math>" steht, <br />
	würde es genügen, wenn alle anderen Zeichen ein "<math>=</math>" wären.		würde es genügen, wenn alle anderen Zeichen ein "<math>=</math>" wären.


	==== Induktionsanfang ====		==== Induktionsanfang ====

Administrator: /* Beispiel 5: Beweis einer Ungleichung */

2024-12-22T20:33:52Z

Beispiel 5: Beweis einer Ungleichung

← Nächstältere Version		Version vom 22. Dezember 2024, 21:33 Uhr
Zeile 308:		Zeile 308:
	In der Abfolgekette von oben nach unten (wo die Punkte sind) dürfen nur die Zeichen <br />		In der Abfolgekette von oben nach unten (wo die Punkte sind) dürfen nur die Zeichen <br />
	<math>=,</math><math> ~ ></math> und <math>\geq</math> auftreten. Da in der Mitte (in der Induktionsvoraussetzung) ein "<math>></math>" steht, <br />		<math>=,</math><math> ~ ></math> und <math>\geq</math> auftreten. Da in der Mitte (in der Induktionsvoraussetzung) ein "<math>></math>" steht, <br />
	würde es genügen, wenn alle anderen Zeichen ein "<math>=</math>" wären. ~~<br /><br /><br />~~		würde es genügen, wenn alle anderen Zeichen ein "<math>=</math>" wären.

Administrator am 19. Dezember 2024 um 18:26 Uhr

2024-12-19T18:26:59Z

← Nächstältere Version		Version vom 19. Dezember 2024, 19:26 Uhr
Zeile 396:		Zeile 396:
	*[https://www.emath.de/Referate/induktion-aufgaben-loesungen.pdf Aufgabensammlung von Rainer Müller, PDF-Datei]		*[https://www.emath.de/Referate/induktion-aufgaben-loesungen.pdf Aufgabensammlung von Rainer Müller, PDF-Datei]
	*[https://www.youtube.com/watch?v=JirX7ssZ74s BrainFAQ]		*[https://www.youtube.com/watch?v=JirX7ssZ74s BrainFAQ]


			[[Kategorie:Seiten, die indexiert werden können]]

Administrator am 19. Dezember 2024 um 12:31 Uhr

2024-12-19T12:31:30Z

← Nächstältere Version		Version vom 19. Dezember 2024, 13:31 Uhr
Zeile 1:		Zeile 1:
			__INDEX__
	__NOTOC__		__NOTOC__
	Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage <br />		Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage <br />

Administrator: Die Seite wurde neu angelegt: „NOTOC Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage
für alle natürlichen Zahlen n, die größer oder gleich einem bestimmten
Anfangswert sind, bewiesen werden soll. Das Adjektiv "vollständig"
wird in der französischen und englischen Sprache nicht verwendet,
man spricht hier vom "preuve par induction" oder "Mathematical Induction".
Die vollständige Induktion besteht aus zwei Teilen:
…“

2024-10-12T20:10:48Z

Die Seite wurde neu angelegt: „__NOTOC__ Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage für alle natürlichen Zahlen n, die größer oder gleich einem bestimmten Anfangswert sind, bewiesen werden soll. Das Adjektiv "vollständig" wird in der französischen und englischen Sprache nicht verwendet, man spricht hier vom "preuve par induction" oder "Mathematical Induction". Die vollständige Induktion besteht aus zwei Teilen: …“

Neue Seite

__NOTOC__
Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage 
für alle natürlichen Zahlen n, die größer oder gleich einem bestimmten 
Anfangswert sind, bewiesen werden soll. Das Adjektiv "vollständig" 
wird in der französischen und englischen Sprache nicht verwendet, 
man spricht hier vom "preuve par induction" oder "Mathematical Induction". 

Die vollständige Induktion besteht aus zwei Teilen: 

- dem Induktionsanfang sowie 
- dem Induktionsschluss (manchmal auch Induktionsschritt genannt). 

Das Prinzip ist folgendes: Wir beweisen im Induktionsschluss die Richtigkeit einer 
Aussage für ein sogenanntes "n+1" unter der Voraussetzung, dass die Aussage 
für den Vorgänger "n" ebenfalls richtig ist. Das genügt aber noch nicht. Es ist zusätzlich zu zeigen, 
DASS die Aussage für n richtig ist. Das ist der Induktionsanfang. 
Üblicherweise wird mit dem Induktionsanfang begonnen, im ersten Beispiel wird davon abgewichen. 

=== Vorbemerkungen ===
Zunächst schauen wir einfach mal folgende Summen an: 

a) 1 + 3 = 4 
b) 1 + 3 + 5 = 9 
c) 1 + 3 + 5 + 7 = 16 
d) 1 + 3 + 5 + 7 + 9 = 25 
e) 1 + 3 + 5 + 7 + 9 + 11 = 36 
f) 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49 
g) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64 
h) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81 

Es ist hier so, dass wir z.B. das Ergebnis von f) in g) weiterverwenden können, 
wir brauchen also nicht aufs Neue 1 + 3 + 5 + 7 + 9 + 11 + 13 zu berechnen, 
sondern verkürzen auf 49 + 15 = 64. Und genauso von g) nach h) mit 64 + 17 = 81. 
Weiterhin sehen wir, dass auf der rechten Seite die Quadratzahlen von 2*2 bis 9*9 
stehen. 

Und nun zu unserem ersten Beispiel, im Internet schon über 1000 mal vorgeführt, 
die sogenannte "Gaußsche Summenformel". 

Sie ist benannt nach dem wohl größten Mathematiker aller Zeiten Carl Friedrich Gauß 
(1777-1855). Der bekam bereits als kleines Kind von seinem Lehrer die Aufgabe, 
alle Zahlen von 1 bis 100 zusammenzuzählen. Also 1 + 2 + 3 + 4 + ... + 99 + 100. 
Gauß änderte die Reihenfolge auf (100 + 1) + (99 + 2) + (98 + 3) + ... + (51 + 50). 
In jeder Klammer steht jetzt 101, so dass er die Rechnung verkürzte und das Produkt 
aus 101*50 (= 5050) berechnete. 

Wenn man nur bis zur 99 aufaddieren will, dann sieht die Paarbildung etwas anders aus, 
nämlich (99 + 1) + (98 + 2) ... bis zu + (51 + 49). Die alleinstehende 50 wird dann 
zum Schluss addiert. Das Ergebnis ist also 100*49 + 50 = 4950. 
Mit diesen Überlegungen kann man eine Gleichung aufstellen, die auf der rechten 
Seite eine "Turbo-Formel" enthält, mit der sich erheblich schneller rechnen läßt: 

<math>1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~.</math> 

Wenn man alle Zahlen von 1 bis 200 addieren will, dann rechnet man 200*(200+1):2, also 20.100 . 
Aber ist diese Formel für alle n korrekt? Das soll im ersten von sechs Beispielen bewiesen werden. 

=== Beispiel 1: Beweis der Gaußschen Summenformel ===
Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n <math> \geq{1} </math>gilt: 
<math>1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~.</math> 

Wir fangen (ausnahmsweise) mit dem Induktionsschluss an. Wir schreiben zuerst die sogenannte 
Induktionsvoraussetzung (manchmal auch Induktionsannahme genannt) auf. Das ist nichts anderes, 
als ein Abschreiben der Aufgabe. Dann folgt die Induktionsbehauptung; diese soll für das um eins 
vergrößerte n gelten. Die Umbenennung von "n" in "k" erfolgt, um zu zeigen, dass die Aussage 
für eine beliebige Zahl gelten soll und (noch) nicht für alle Zahlen. Viele Autoren verzichten auf 
die Umbuchstabierung. Vorübergehend setzen wir ein Fragezeichen über das Gleichheitszeichen. 

==== Induktionsschluss ====
Induktionsvoraussetzung: 

Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie für jedes 
beliebige n=k gelten. 

<math>1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k \stackrel{?}{=} \frac{k*(k+1)}{2} </math>. 

Induktionsbehauptung: 
Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie auch für den Nachfolger von k, 
also k+1 gelten. Das nennen wir die Induktionsbehauptung. 
<math>1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k ~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}</math> 

Empfehlung: Den Term "k+1" IMMER in Klammern setzen! 

Jetzt holen wir die rechte Seite der Induktionsvoraussetzung und nehmen dabei an, dass diese richtig ist. 

<math>\underbrace{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} ~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}</math> 

<math>~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}</math> 

Jetzt werden beide Seiten der Gleichung umgeformt. 

<math>~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + \frac{2*(k+1)}{2}\,~ \stackrel{?}{=} \frac{(k+1)*(k+2)}{2}</math> 

In allen Zählern die Klammern beseitigen: 

<math>~~~~~~~~~~~~~~~~~~~~\frac{k^2+k}{2}\, ~~~~~~~~~~~~~~~~~~~~~~~~~ + \frac{2k+2}{2}\,~~~~ \stackrel{?}{=} \frac{k^2+k+2k+2}{2}</math> 

Auf beiden Seiten die Nenner entfernen und die Zähler addieren führt zu: 

<math>k^2~+~3k~+2~=~k^2~+~3k~+2 </math> 

Die Induktionsbehauptung ist bewiesen, Bedingung ist die Richtigkeit der Induktionsvoraussetzung. 
Wir sind daher noch nicht fertig. Zunächst ist nur eine Dominosteinkette aufgestellt, die Steine stehen 
senkrecht und dicht genug nebeneinander. Wir wissen bis jetzt: Wenn der 27. Stein umfällt, dann fällt 
auch der nachfolgende 28. Stein um. Und danach der 29. Wenn der 142.367. Stein umfällt, dann fällt auch der 142.368. 
Stein um. Und wenn der erste Stein umfällt, dann fällt auch der zweite Stein um. Wir müssen aber noch 
zeigen, DASS ein erster Dominostein umfällt. Dieses ist unser Induktionsanfang. 

==== Induktionsanfang ====
Zunächst versuchen wir, alle Dominosteine ab dem 5. zu kippen und mit n=5 erhalten wir: 

<math>1 + 2 + 3 + 4 + 5 ~ = \frac{5*(5+1)}{2}~.</math> 
15 = 15, wahre Aussage. 

Der 5. Dominostein ist gefallen und alle nachfolgenden 
ebenfalls. Die Aussage ist bewiesen für alle n größer oder gleich fünf. 

Die Aufgabe verlangte jedoch die Untersuchung für alle n größer oder gleich eins. Also setzen wir n=1 ein. 

<math>1 ~ = ~ \frac{1*(1+1)}{2}</math> 

1 = 1, wahre Aussage. 

Mit Hilfe von Induktionsanfang und Induktionsschluss ist jetzt gezeigt: 

<math>1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}</math> 

ist gültig für alle natürlichen Zahlen n <math> \geq{1} </math>. 

Wichtig: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere 
wertlos und der Beweis ist nicht erbracht. 

=== Beispiel 2: Aufsummierung von Kubikzahlen ===
Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n <math> \geq{1} </math> gilt: 
<math>1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ n^3 = \frac{n^2(n+1)^2}{4}~.</math> 

Wir beginnen jetzt mit dem Induktionsanfang, wie es üblich ist. Das Fragezeichen 
über dem Gleichheitszeichen lassen wir weg. Wir formen in diesem Beispiel 
nur die linke Seite der Induktionsbehauptung um. Das erfordert, dass man die 
Möglichkeiten des Ausklammerns und binomische Formeln erkennt. 

==== Induktionsanfang ====
Wir setzen n=1: 

<math>1^3 ~ = \frac{1^2(1+1)^2}{4}\,</math> 

1=1, wahre Aussage. 

==== Induktionsschluss ====

Induktionsvoraussetzung: 

<math>1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 = \frac{k^2(k+1)^2}{4}~.</math> 

Induktionsbehauptung: 

<math>1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~.</math> 

Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung: 

<math>\underbrace{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}</math> 

<math>\frac{k^2(k+1)^2}{4}\, + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~.</math> 

Wir formen hier nur die linke Gleichungsseite um. 

Erweitern des zweiten Summanden (mal 4): 

<math>\frac{k^2(k+1)^2}{4}\, + ~ \frac{4(k+1)^3}{4} ~ </math>, 

<math>=\frac{k^2(k+1)^2\, + ~ 4(k+1)^3}{4} ~ </math>, 

auf die rechte Seite sehen, um eine geeignete Vorgehensweise herauszufinden. 

Zweckmäßig ist es, <math>(k+1)^2</math> ausklammern: 

<math>=\frac {(k+1)^2 [k^2+4(k+1)]}{4} ~ </math>, 

<math>=\frac {(k+1)^2 (k^2+4k+4)}{4} ~ </math> 

Binom im zweiten Faktor erkennen: 

<math>=\frac {(k+1)^2 (k+2)^2}{4} ~ </math>, 

<math>=\frac {(k+1)^2 ((k+1)+1)^2} {4} ~ </math> 

Und das ist gleich der rechten Seite der Induktionsbehauptung. 

q.e.d. 

(q.e.d ist die Abkürzung für qoud erat demonstrandum, übersetzt: was zu beweisen war. 
Auch ein kleines, leeres Quadrat am Ende des Beweises ist üblich.)

Eine zweite Lösungsmöglichkeit ist das Entfernen der Klammern auf beiden Seiten der IB, dann 
muss man das Binom nicht erkennen. Nachteil: man kann sich leichter verrechnen. 

<math>\underbrace{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}</math> 

<math>\frac{k^2(k+1)^2}{4}\, + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~</math> 

zweiter Summand erweitert (mal 4): 

<math>\frac{k^2(k+1)^2}{4}\, + ~~\frac{4(k+1)^3}{4} ~~ = \frac{(k+1)^2((k+1)+1)^2}{4}~</math>, 

beide Seiten mal 4: 

<math>k^2(k+1)^2 + 4(k^3+3k^2+3k+1)~ = ~(k+1)^2(k+2)^2</math> 

<math>k^2(k^2+2k+1)+4k^3+12k^2+12k+4~ = ~ (k^2+2k+1)(k^2+4k+4)</math> 

<math>k^4+2k^3+k^2+4k^3+12k^2+12k+4 ~ = ~ k^4+2k^3+k^2+4k^3+12k^2+12k+4</math> 

q.e.d. 

=== Beispiel 3: Teilbarkeiten (I) ===
Auch Teilbarkeiten lassen sich mit Hilfe der vollständigen Induktion beweisen. 
Meistens wenden wir die Induktionsvoraussetzung erst am Ende an. Das Vorgehen ist 
weitgehend gleich: wenn jeder Summand durch eine Zahl teilbar ist, dann ist auch 
die gesamte Summe durch diese Zahl teilbar. Bei den Umformungen ist es Ziel, dass die 
Induktionsvoraussetzung wieder zum Vorschein kommt. 

Beweisen Sie: <math>3*4^n+6 </math> ist für alle natürlichen Zahlen n <math> \geq{1} </math> durch 9 ohne Rest teilbar. 

==== Induktionsanfang ====

Wir setzen n=1 

<math>3*4^1+6 = 18</math>, 18 ist durch 9 teilbar, wahre Aussage. 

==== Induktionsschluss ====

Induktionsvoraussetzung: 

<math>3*4^k+6 </math> ist durch 9 teilbar. 

Induktionsbehauptung: 

<math>3*4^{(k+1)} +6 </math> ist durch 9 teilbar. 

Anwendung der Potenzgesetze führt zu: 

<math>3*4*4^k +6 </math> 

Wir wollen erreichen, dass die IV sichtbar wird, 
der Trick: wir addieren 18-18 und sortieren um. 
Dieses zu erkennen ist der schwierigste Teil der Aufgabe. 

<math>3*4*4^k +6~~~ +18-18 </math> 

<math>3*4*4^k +24~~~ -18 </math> 

<math>4*(3*4^k +6)~~ -18 </math> 

In der Klammer steht die IV, d. h. der erste Summand ist durch 9 teilbar. Auch -18 ist durch 9 teilbar. 

Also ist der gesamte Ausdruck durch 9 teilbar. 

q.e.d. 

=== Beispiel 4: Teilbarkeiten (II) ===
Beweisen Sie, dass <math>7^n-2^n </math> für alle natürlichen Zahlen n <math>\geq{1} </math> durch 5 ohne Rest teilbar ist. 

==== Induktionsanfang ====
Wir setzen n=1 

<math>7^1-2^1 </math> = 5, durch 5 teilbar, wahre Aussage. 

==== Induktionsschluss ====
Induktionsvoraussetzung: 

<math>7^k-2^k </math> ist durch 5 teilbar. 

Induktionsbehauptung: 

<math> 7^{(k+1)}-2^{(k+1)} </math> ist durch 5 teilbar. 

<math>7*7^k-2*2^k </math> 

Ziel soll sein, die IV sichtbar machen, dazu den ersten Faktor 7 zerlegen in 5 + 2. 

<math>(5+2)*7^k-2*2^k </math> 

<math>5*7^k+2*7^k-2*2^k </math> 

<math>5*7^k+2*(7^k-2^k) </math> 

Der erste Summand ist durch 5 teilbar. Mit der IV ist auch der zweite Summand durch 5 teilbar. 
Also ist der gesamte Ausdruck durch 5 teilbar. 

q.e.d. 

=== Beispiel 5: Beweis einer Ungleichung ===
Diesmal betrachten wir eine Ungleichung, besser wäre die Bezeichnung "Relation". 
Der Umgang mit den Zeichen =, <, >, <math> \geq </math>, <math> \leq </math> darf keine Schwierigkeiten machen. 

Beweisen Sie: <math>2^n > n^2 ~</math> für alle n > 4. 

Folgende Vorgehensweise ist bei Ungleichungen empfehlenswert: Man zieht die Induktionsbehauptung 
auseinander und setzt die Induktionsvoraussetzung in die Mitte. 
In der Abfolgekette von oben nach unten (wo die Punkte sind) dürfen nur die Zeichen 
<math>=,</math><math> ~ ></math> und <math>\geq</math> auftreten. Da in der Mitte (in der Induktionsvoraussetzung) ein "<math>></math>" steht, 
würde es genügen, wenn alle anderen Zeichen ein "<math>=</math>" wären. 

==== Induktionsanfang ====
Wir setzen <math>n=5</math> 

<math>2^5 > 5^2 ~ \Rightarrow ~ 32>25</math>, wahre Aussage. 

==== Induktionsschluss ====
Induktionsvoraussetzung: 

<math>2^k > k^2 ~</math> 

Induktionsbehauptung: 

<math>2^{(k+1)} > (k+1)^2 ~</math> 

Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung: 

<math> 2^{(k+1)} </math> 
* 
* 
* 
* 
<math>2^k ~</math> 
<math>></math> 
<math> k^2 ~</math> 
* 
* 
* 
* 
<math> (k+1)^2 ~</math> 

Zunächst sieht es gut aus. <math> 2^{(k+1)} </math> ist größer als <math> 2^{k} </math>. 
Aber es droht Ungemach, denn <math> k^2 ~</math> ist kleiner als <math> (k+1)^2 ~</math> 
und es dürfen in dieser Aufgabe nur die Zeichen <math>=,</math><math> ~ ></math> und <math>\geq</math> verwendet werden. 
Wir berechnen <math> 2^{(k+1)} ~ = ~ 2*2^k </math> und erweitern die Induktionsvoraussetzung 
mit zwei. Die IV muss auf beiden Seiten erweitert werden (damit die Aussage nicht 
verfälscht wird), deshalb wird <math> k^2 ~</math> ebenfalls verdoppelt. Das geschieht in 2.) und 3.) . 
Jetzt sieht es besser aus, es muss bewiesen werden, dass <math>2*k^2 \geq (k+1)^2</math> . 
Das geschieht durch eine v.I. innerhalb einer v.I. . 

Nochmal von vorne: 

1.) <math> 2^{(k+1)} </math> 
         <math>=</math> 
2.) <math> 2*2^k </math> 
         <math>></math> 
3.) <math> 2*k^2 </math> 
         <math>=</math> 
4.) <math>k^2+k^2 </math> 

                        Zu beweisen: <math>k^2 \geq {2*k+1}</math> für alle <math>k \geq 5</math>. 
                        '''Induktionsanfang''' 
                        4.1.) <math>n=5</math> 
                        4.2.) <math> 5^2>11 </math>, wahre Aussage. 
                        '''Induktionsschluss''' 
                        Induktionsvoraussetzung: 
                        4.3.) <math>k^2 \geq {2*k+1}</math> 
                        Induktionsbehauptung: 
                        4.4.) <math>(k+1)^2 \geq {2*(k+1)+1}</math> 
                        Beweis der Induktionsbehauptung: 
                        4.5.) <math>(k+1)^2</math> 
                                      <math>=</math> 

                        4.6.) <math>k^2+2*k+1 </math> 
                                      <math>\geq </math> 
                        4.7.) <math>2*k+1 +2*k+1</math> 
                                      <math>= </math> 
                        4.8.) <math>4*k+2</math> 
                                      <math>> </math> 
                        4.9.) <math>2*k+3</math> 
                                      <math>= </math> 
                        4.10.) <math>2*(k+1)+1</math> 
                        (q.e.d.) 
         <math>></math> 
5.) <math>k^2+2*k+1</math> 
         <math>=</math> 
6.) <math> (k+1)^2</math> 

q.e.d.

== Weblinks ==
*[https://www.youtube.com/watch?v=zM997Tpr59k&t=305s Vorlesung von Christian Spannagel]
*[https://www.emath.de/Referate/induktion-aufgaben-loesungen.pdf Aufgabensammlung von Rainer Müller, PDF-Datei]
*[https://www.youtube.com/watch?v=JirX7ssZ74s BrainFAQ]