Teilbarkeitsaufgaben

siehe: Teilbarkeit

Beispiel für Teilbarkeitsaufgaben der vollständige Induktion

Für alle $n\in \mathbb{N}$ gilt:
$4n^3-n$ ist ohne Rest
durch 3 teilbar
3 | $(4n^3-n)$

Beweis: IndAnf: $n=0$
$4\cdot 0^3-0=0=3\ast 0$
Also: 3 | 0

Induktionschrintt: Angenommen
3 | ($4n^3-n$) für ein $n\ge 0$

Zu zeigen, dass 3 | ($4(n+1{)}^3-(n+1)$) gilt:
$4(n+1{)}^3-(n+1)$
$=4(n^3+3n^2+3n+1)-(n+1)$
$=4n^3+12n^2+12n+4-n-1$
$=(4n^3-n)+(12n^2+12n+3)$
$=(4n^3-n)+3(4n^2+4n+1)$
Der Summand in der letzten Zeile ist nach Induktionsvoraussetzung durch 3 teilbar, der zweite Summand ist offensichtliuch ein Vielfaches von 3 und damit ebenso durch 3 teilbar.

Manchmal ist es nicht möglich aus $A(n)$ diereckt $A(n+1)$ zu folgern. Mann benötigt dann:

$A(k)$ ist wahr für alle $n_0\le k\le n$

Mann nennt dies starke Induktion.