Einstieg in ...   Mathematik, vollständige Induktion




3. Beispiel

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, dass \(3*4^n+6 \) für alle natürlichen Zahlen n \( \geq{1} \) durch 9 ohne Rest teilbar ist.


Induktionsanfang

n=1

\(3*4^1+6 = 18\), 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.

\(3*4*4^k +6 \) Anwendung der Potenzgesetze

Um die IV anwenden zu können, müssen wir die 4 ausklammern, erhöhen der 6 auf 24 durch Addition von 18-18.

\(3*4*4^k +6~~~ +18-18 \)

\(3*4*4^k +24~~~ -18 \)

\(4*(3*4^k +6)~~ -18 \)

Wegen der IV ist der erste Summand durch 9 teilbar. Der zweite Summand ist durch 9 teilbar.

Also ist der gesamte Ausdruck durch 9 teilbar.      q.e.d.