\(4^n + 15n -1\)

für alle \(n\in\mathbb{N}\) durch 9 teilbar ist.

Induktionsanfang (n=1):
Wegen \(4^1+15\cdot 1-1=18=2\cdot 9\) ist die Behauptung für n=1 wahr.

Induktionsschritt von n nach n+1:
Wenn \(4^n + 15n -1\) durch 9 teilbar ist, dann ist auch \(4\cdot(4^n + 15n -1)\) durch 9 teilbar. Also ist

\(4^{n+1} + 15(n+1) -1=4\cdot(4^n + 15n -1)-45 n-18\)

durch 9 teilbar, weil jeder Summand durch 9 teilbar ist.
Damit haben wir beide Teile der Vollständigen Induktion erfolgreich durchgeführt und die Behauptung ist bewiesen.

□

Die Gültigkeit der Summenformel

\(1\cdot 2^1+2\cdot 2^2+3\cdot 2^3+\dots +n\cdot 2^n= (n-1)2^{n+1}+2 \)

soll für alle \(n\in\mathbb{N}\) nachgewiesen werden.

Induktionsanfang (n=1):
Hier steht auf der linken Seite nur der Term \(1\cdot 2^1\) und rechts \(0\cdot 2^2+2\), also ist die Summenformel für \(n=1\) wahr.

Induktionsschritt von n nach n+1:
Die Summenformel sei für ein n richtig. Addiert man auf der linken Seite noch einen weiteren Term, dann ist

\(1\cdot 2^1+2\cdot 2^2+\dots +n\cdot 2^n+(n+1)\cdot 2^{n+1}=(n-1)2^{n+1}+2+(n+1)\cdot 2^{n+1}=(2n)\cdot 2^{n+1}+2= n\cdot 2^{n+2}+2\).

Die Summenformel gilt also auch für die Zahl n+1 und nach dem Prinzip der Vollständigen Induktion somit für alle \(n\in\mathbb{N}\).

□