Vollständige Induktion
Angewandt auf obiges Beispiel sieht das so aus:
Wir wollen eine Formel finden die die Summe aller ungeraden Zahlen von 1 bis n vereinfacht und, was wichtiger ist, wir wollen diese Formel beweisen:
1 = 1 ; 1 + 3 = 4 ; 1 + 3 + 5 = 9 ; 1 + 3 + 5 + 7 = 16
Vermutung: Die Summe aller natürlichen Zahlen von 1 bis n ergibt:
∑
i
=
1
n
i
=
n
∗
(
n
+
1
)
2
{\displaystyle \sum _{i=1}^{n}i={\frac {n*(n+1)}{2}}}
Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:
∑
i
=
1
n
i
+
(
n
+
1
)
=
∑
i
=
1
n
+
1
i
{\displaystyle \sum _{i=1}^{n}i+(n+1)=\sum _{i=1}^{n+1}i}
∑
i
=
1
n
i
+
(
n
+
1
)
=
n
∗
(
n
+
1
)
2
+
(
n
+
1
)
{\displaystyle \sum _{i=1}^{n}i+(n+1)={\frac {n*(n+1)}{2}}+(n+1)}
∑
i
=
1
n
+
1
i
=
(
n
+
1
)
∗
(
n
+
2
)
2
{\displaystyle \sum _{i=1}^{n+1}i={\frac {(n+1)*(n+2)}{2}}}
n
∗
(
n
+
1
)
2
+
n
+
1
=
(
n
+
1
)
∗
(
n
+
2
)
2
{\displaystyle {\frac {n*(n+1)}{2}}+n+1={\frac {(n+1)*(n+2)}{2}}}
Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.
n
∗
(
n
+
1
)
2
+
n
+
1
=
(
n
+
1
)
∗
(
n
+
2
)
2
{\displaystyle {\frac {n*(n+1)}{2}}+n+1={\frac {(n+1)*(n+2)}{2}}}
n
∗
(
n
+
1
)
2
+
2
n
+
2
2
=
(
n
+
1
)
∗
(
n
+
2
)
2
{\displaystyle {\frac {n*(n+1)}{2}}+{\frac {2n+2}{2}}={\frac {(n+1)*(n+2)}{2}}}
n
∗
(
n
+
1
)
+
2
n
+
2
2
=
(
n
+
1
)
∗
(
n
+
2
)
2
{\displaystyle {\frac {n*(n+1)+2n+2}{2}}={\frac {(n+1)*(n+2)}{2}}}
n
2
+
n
+
2
n
+
2
2
=
n
2
+
3
n
+
2
2
{\displaystyle {\frac {n^{2}+n+2n+2}{2}}={\frac {n^{2}+3n+2}{2}}}
n
2
+
3
n
+
2
2
=
n
2
+
3
n
+
2
2
{\displaystyle {\frac {n^{2}+3n+2}{2}}={\frac {n^{2}+3n+2}{2}}}
Damit ist die vollständige Induktion für
∑
i
=
1
n
2
i
−
1
=
n
2
{\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}
Wir wollen eine Formel finden die die Summe aller ungeraden Zahlen von 1 bis n vereinfacht und, was wichtiger ist, wir wollen diese Formel beweisen:
1 = 1 ; 1 + 3 = 4 ; 1 + 3 + 5 = 9 ; 1 + 3 + 5 + 7 = 16
Vermutung: Die Summe aller ungeraden Zahlen von 1 bis n ergibt eine Quadratzahl. Genauer gesagt:
∑
i
=
1
n
2
i
−
1
=
n
2
{\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}
Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:
∑
i
=
1
n
2
i
−
1
+
(
2
(
n
+
1
)
−
1
)
=
∑
i
=
1
n
+
1
2
i
−
1
{\displaystyle \sum _{i=1}^{n}2i-1+(2(n+1)-1)=\sum _{i=1}^{n+1}2i-1}
∑
i
=
1
n
2
i
−
1
+
(
2
(
n
+
1
)
−
1
)
=
n
2
+
(
2
(
n
+
1
)
−
1
)
{\displaystyle \sum _{i=1}^{n}2i-1+(2(n+1)-1)=n^{2}+(2(n+1)-1)}
∑
i
=
1
n
+
1
2
i
−
1
=
(
n
+
1
)
2
{\displaystyle \sum _{i=1}^{n+1}2i-1=(n+1)^{2}}
n
2
+
(
2
(
n
+
1
)
−
1
)
=
(
n
+
1
)
2
{\displaystyle n^{2}+(2(n+1)-1)=(n+1)^{2}}
Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.
n
2
+
(
2
(
n
+
1
)
−
1
)
=
(
n
+
1
)
2
{\displaystyle n^{2}+(2(n+1)-1)=(n+1)^{2}}
n
2
+
2
n
+
2
−
1
=
n
2
+
2
n
+
1
{\displaystyle n^{2}+2n+2-1=n^{2}+2n+1}
n
2
+
2
n
+
1
=
n
2
+
2
n
+
1
{\displaystyle n^{2}+2n+1=n^{2}+2n+1}
Damit ist die vollständige Induktion für
∑
i
=
1
n
2
i
−
1
=
n
2
{\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}
Wir wollen eine Formel finden die 1 plus die Summe aller 2er Potenzen von 20 bis 2n vereinfacht und, was wichtiger ist, wir wollen diese Formel beweisen:
1 + 1 = 2 ; 1 + 1 + 2 = 4 ; 1 + 1 + 2 + 4 = 8
Vermutung: 1 plus die Summe aller 2er Potenzen von 20 bis 2n ergibt die 2er Potenz 2n+1 . Genauer gesagt:
1
+
∑
i
=
0
n
2
i
=
2
n
+
1
{\displaystyle 1+\sum _{i=0}^{n}2^{i}=2^{n+1}}
Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:
1
+
∑
i
=
0
n
2
i
+
2
n
+
1
=
1
+
∑
i
=
0
n
+
1
2
i
{\displaystyle 1+\sum _{i=0}^{n}2^{i}+2^{n+1}=1+\sum _{i=0}^{n+1}2^{i}}
1
+
∑
i
=
0
n
2
i
+
2
n
+
1
=
2
n
+
1
+
2
n
+
1
{\displaystyle 1+\sum _{i=0}^{n}2^{i}+2^{n+1}=2^{n+1}+2^{n+1}}
1
+
∑
i
=
0
n
+
1
2
i
=
2
n
+
2
{\displaystyle 1+\sum _{i=0}^{n+1}2^{i}=2^{n+2}}
2
n
+
1
+
2
n
+
1
=
2
n
+
2
{\displaystyle 2^{n+1}+2^{n+1}=2^{n+2}}
Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.
2
n
+
1
+
2
n
+
1
=
2
n
+
2
{\displaystyle 2^{n+1}+2^{n+1}=2^{n+2}}
2
∗
2
n
+
1
=
2
n
+
2
{\displaystyle 2*2^{n+1}=2^{n+2}}
2
n
+
2
=
2
n
+
2
{\displaystyle 2^{n+2}=2^{n+2}}
Damit ist die vollständige Induktion für
∑
i
=
1
n
2
i
−
1
=
n
2
{\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}
