Beispielbeweise zur Teilbarkeit mittels vollständiger Induktion

Beispiel 5417A

Man zeige, dass 10n−110^n-1 durch 99 teilbar ist für alle natürlichen Zahlen n≥1n\geq 1.

Lösung

Induktionsanfang: Für n=1n=1 gilt sicher 9∣99|9.
Induktionsschritt: 10n+1=10⋅10n−1=9⋅10n+10n−110^{n+1}=10\cdot 10^n-1=9\cdot 10^n+10^n-1
Es ist nach Induktionsvoraussetzung 9∣10n−19|10^n-1 und sicher auch 9∣9⋅10n9|9\cdot 10^n. Damit ist die Behauptung bewiesen. □\qed
 
 

Beispiel 15VX

4∣5n+74|5^n+7

Lösung

Induktionsanfang: 4∣12=51+74|12=5^1+7.
Induktionsschritt: 5n+1+7=5⋅5n+7=5n+7+4⋅5n5^{n+1}+7=5\cdot 5^n+7=5^n+7+4\cdot 5^n.
Es gilt 4∣5n+74|5^n+7 nach Induktionsvoraussetzung und natürlich 4∣4⋅5n4|4\cdot 5^n. □\qed
Dieses Beispiel kann auch ohne Induktion unter Benutzung von Kongruenzen gelöst werden.
7≡3mod  47\equiv 3\mod 4 und 5≡1mod  45\equiv 1\mod 4 also auch 5n≡1n≡1mod  45^n\equiv 1^n\equiv 1\mod 4 und damit 51+7≡1+4≡0mod  45^1+7\equiv 1+4\equiv 0\mod 4.

Im großen Garten der Geometrie kann sich jeder nach seinem Geschmack einen Strauß pflücken.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Natürliche Zahlen