Vollständige Induktion Induktionsschritt?
Aufgabe:
Sei a eine ganze Zahl. Beweisen Sie: Für alle n ∈ ℕ = {1,2,3, ... } gilt:
(a-1) | (an -1)
Ich würde hierfür die vollständige Induktion nehmen.
IA:
(a - 1) | (a1 - 1) = (a - 1)
Das ist offensichtlich wahr.
IV: (a-1) | (an -1) ist wahr für ein n aus ℕ.
IS: Zu zeigen: dass es für n + 1 gilt, wenn es für ein n gilt
das macht mir jetzt irgendwie Schwierigkeiten. Also ich muss ja n mit n+1 ersetzen.
Also: a^(n+1)-1 ist durch (a-1) teilbar
Wie kann ich das beweisen?
3 Antworten
Hallo,
a^(n+1) ist a*a^n.
a*a^n=(a-1+1)*a^n=(a-1)*a^n+a^n.
a^(n+1)-1 ist also (a-1)*a^n+a^n-1.
a^n*(a-1) teilt a-1, denn es ist ein ganzzahliges Vielfaches davon.
a^n-1 teilt laut IV a-1, kann also durch k*(a-1) ersetzt werden.
a^(n+1)-1 ist also gleich a^n*(a-1)+k*(a-1)=(a^n+k)*(a-1) und damit ein ganzzahliges Vielfaches von a-1.
Herzliche Grüße,
Willy
Hinweis:
Darin findest du nun a^n - 1 wieder und kannst nach Induktionsvoraussetzung nutzen, dass a^n - 1 durch a - 1 teilbar ist, es also eine ganze Zahl k mit a^n - 1 = k * (a - 1) gibt.
Es gibt dann also eine ganze Zahl k mit...
Versuche damit nun weiter zu zeigen, dass es eine ganze Zahl k' gibt, sodass
ist, womit du dann gezeigt hättest, dass dann auch a^(n+1) - 1 durch a - 1 teilbar ist.
============
Hier ein kompletter Lösungsvorschlag zum Vergleich:
Eine ähnliche Lösung könnte so aussehen:
Hier wurde aus dem a^(n+1) ein a rausgezogen, und eine 0 eingefügt (das +a - a). Dann kann die Induktionsvoraussetzung verwendet werden.