Beispiel 3:
Teilbarkeiten (I)
Auch Teilbarkeiten lassen sich mit Hilfe der vollständigen Induktion beweisen.
Meistens wenden wir die Induktionsvoraussetzung erst am Ende an. Das Vorgehen ist
weitgehend gleich: wenn jeder Summand durch eine Zahl teilbar ist, dann ist auch
die gesamte Summe durch diese Zahl teilbar. Bei den Umformungen ist es Ziel, dass die
Induktionsvoraussetzung wieder zum Vorschein kommt.
Beweisen Sie: \(3*4^n+6 \) ist für alle natürlichen Zahlen n \( \geq{1} \) durch 9 ohne Rest teilbar.
Induktionsanfang
n=1
\(3*4^1+6 = 18\), 18 ist durch 9 teilbar, wahre Aussage.
Induktionsschluss
- Induktionsvoraussetzung:
\(3*4^k+6 \) ist durch 9 teilbar.
- Induktionsbehauptung:
\(3*4^{(k+1)} +6 \) ist durch 9 teilbar.
Anwendung der Potenzgesetze führt zu:
\(3*4*4^k +6 \)
Wir wollen erreichen, dass die IV sichtbar wird,
der Trick: wir addieren 18-18 und sortieren um.
Dieses zu erkennen ist der schwierigste Teil der Aufgabe.
\(3*4*4^k +6~~~ +18-18 \)
\(3*4*4^k +24~~~ -18 \)
\(4*(3*4^k +6)~~ -18 \)
In der Klammer steht die IV, d. h. der erste Summand ist durch 9 teilbar. Auch -18 ist durch 9 teilbar.
Also ist der gesamte Ausdruck durch 9 teilbar.
q.e.d.