Das wird immer nachgefragt, daher poste ich hier die Antworten auf alle Fragen bezüglich Induktionsbeweise.

[spoiler=Definition]Vollständige Induktion

Der Beweis durch vollständige Induktion ist ein oft angewendetes Verfahren zum Beweis von Sätzen der Form „Für jede natürliche Zahl n gilt ...“. Dazu zeigt man zuerst, dass die Aussage für n=0 (oder auch einen anderen Anfangswert n0) gilt, und danach, dass sie immer auch für n+1 gilt, wenn sie für n gilt. Die vollständige Induktion lässt sich mit einem Domino-Effekt vergleichen. Man stellt die Steine so auf, dass, wenn einer umfällt, auch immer der nächste umfällt (n -> n+1), und stößt den ersten Stein um (n=0).

Quelle: Wikipedia[/spoiler]

Hier ist die allgemeine Struktur des Beweises:

Beispiel:

1. Behauptung: [tex]1 + 3 + ... + (2n+1) = (n+1)^2[/tex]

2. Induktionsanfang:
[tex]\mbox{Die Behauptung gilt für }n = 0:\quad(2\cdot0+1) = 1 = (0+1)^2\mbox{ ist eine wahre Aussage.}[/tex]

3. Induktionsannahme:
[tex]\mbox{Sei die Behauptung } 1 + 3 + ... + (2n+1) = (n+1)^2 \mbox{ für ein beliebiges } n \mbox{ gültig.}[/tex]

4. Induktionsschritt: [tex]n\to n+1[/tex]

5. Zu zeigen:
[tex]1 + 3 + ... + (2n+1) + (2n+3) = \left( \left( n + 1 \right) + 1 \right)^2[/tex]

6. Beweis:
[tex]\begin{align*} 1+3+\ldots+\left(2n+1\right)+\left(2n+3\right) & =\left(1+3+\ldots+\left(2n+1\right)\right)+\left(2n+3\right)\\ & \overset{I.A.}{=}\left(n+1\right)^+\left(2n+3\right)\\ & =\left(n+1\right)^+2\left(n+1\right)+1\\ & =\left(\left(n+1\right)+1\right)^ \end{align*}[/tex]

6. Also gilt die Behauptung auch für n+1, damit ist die Aussage nach dem Induktionsprinzip bewiesen.