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:
![{\displaystyle \sum _{i=1}^{n}i={\frac {n*(n+1)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/744241a687c528a4719c952fc0b8aef4b474b4ab)
Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:
![{\displaystyle \sum _{i=1}^{n}i+(n+1)=\sum _{i=1}^{n+1}i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dec6168e409f45b0776ed4d7f44bae5c22f02669)
![{\displaystyle \sum _{i=1}^{n}i+(n+1)={\frac {n*(n+1)}{2}}+(n+1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe96036d7b9d4603cf1d420b5d96839cf2016ef5)
![{\displaystyle \sum _{i=1}^{n+1}i={\frac {(n+1)*(n+2)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c0ff73d094a40b6cd4b9c24fd53fec18ee7711e)
/* Die Perle */
Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.
![{\displaystyle {\frac {n*(n+1)}{2}}+n+1={\frac {(n+1)*(n+2)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df3d93acb61d3dea7e032a08fd6a8d1c96fa16cb)
![{\displaystyle {\frac {n*(n+1)}{2}}+{\frac {2n+2}{2}}={\frac {(n+1)*(n+2)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5d9805654d71d52dc3ea9f2f9885c0144d0ce80)
![{\displaystyle {\frac {n*(n+1)+2n+2}{2}}={\frac {(n+1)*(n+2)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e15d8d3a3b323cfc04679338b169a53d2a15e4e6)
![{\displaystyle {\frac {n^{2}+n+2n+2}{2}}={\frac {n^{2}+3n+2}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23cf0ed9932938a7bdb2a44ec77c4b95e81f97ec)
![{\displaystyle {\frac {n^{2}+3n+2}{2}}={\frac {n^{2}+3n+2}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/712147e35d6d9556eda185f92c7328b7ccbecac4)
Damit ist die vollständige Induktion für
abgeschlossen und bewiesen.
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:
![{\displaystyle \sum _{i=1}^{n}2i-1=n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d025ebb112b28361722165a685a05fc6678a0d4)
Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:
![{\displaystyle \sum _{i=1}^{n}2i-1+(2(n+1)-1)=\sum _{i=1}^{n+1}2i-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b1cce637ffdecbbd7e3ba5b7b0df75997466e22)
![{\displaystyle \sum _{i=1}^{n}2i-1+(2(n+1)-1)=n^{2}+(2(n+1)-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9572d321c395b28a864024e3214a889a278342c0)
![{\displaystyle \sum _{i=1}^{n+1}2i-1=(n+1)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85fc6f090a88549436e9631c1ceaee042fc41a2f)
/* Die Perle */
Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.
![{\displaystyle n^{2}+(2(n+1)-1)=(n+1)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cc56ae720d0e9a2e0c1fc605eec61e08399f326)
![{\displaystyle n^{2}+2n+2-1=n^{2}+2n+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b087bd5d27dcf48ad58901f075b0698a9ca69bbe)
![{\displaystyle n^{2}+2n+1=n^{2}+2n+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89992cb23b2c6fa203dac0e27c6ee2fbee21bf06)
Damit ist die vollständige Induktion für
abgeschlossen und bewiesen.
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:
![{\displaystyle 1+\sum _{i=0}^{n}2^{i}=2^{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/057d8e3fa1e74d50d63b5319d2ac4c11b0c0cda2)
Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:
![{\displaystyle 1+\sum _{i=0}^{n}2^{i}+2^{n+1}=1+\sum _{i=0}^{n+1}2^{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90519fb6eccfad9bddc073421d2ab96ecf3564f0)
![{\displaystyle 1+\sum _{i=0}^{n}2^{i}+2^{n+1}=2^{n+1}+2^{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c0d34d055d0f9282308314cced170b9778ed673)
![{\displaystyle 1+\sum _{i=0}^{n+1}2^{i}=2^{n+2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39fc4ac1c7af46f2113c9156f914f92473407a7d)
/* Die Perle */
Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.
![{\displaystyle 2^{n+1}+2^{n+1}=2^{n+2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/526fbdda9e6944a09106457fef6bf6516d0a8d9f)
![{\displaystyle 2*2^{n+1}=2^{n+2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3bfeb32574d1af71e2b235ba47b81d5c79de7d4)
![{\displaystyle 2^{n+2}=2^{n+2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c72c43645d519397706ed5912ce128f0d19c2c0)
Damit ist die vollständige Induktion für
abgeschlossen und bewiesen.