Rekursion und Induktion. f(0) = 0, f(1) = 2 und f(n) = 4f(n − 1) − 4f(n − 2) für alle n ≥ 2.

Question

Die Funktion f : N → N wird wie folgt rekursiv definiert:

f(0) = 0, f(1) = 2 und f(n) = 4f(n − 1) − 4f(n − 2) für alle n ≥ 2.

Erzeugen Sie die Werte von f(n) für alle n ≤ 5, entdecken Sie dadurch eine einfache nichtrekursive Formel für f(n) und weisen Sie deren Gültigkeit für alle n ∈ N mit vollständiger Induktion nach!

Answer 1

Das Aufstellen der Werte von \(f(n)\) für \(n=0\) bis \(n=5\) sollte kein Problem sein. Folgende Tabelle läuft bis \(n=6\): $$\begin{array}{ccc} n & f(n) & \\ \hline 0 & 0 & 0 \\ 1 & 2 & 2^1 \\ 2 & 8 & 2^3 \\ 3 & 24 & 3 \cdot 2^3 \\ 4 & 64 & 2^6 \\ 5 & 160 & 5 \cdot 2^5 \\ 6 & 384 & 3 \cdot 2^7\end{array} $$ In der dritten Spalte habe ich die Primzahl-Zerlegung von \(f(n)\) eingetragen. Vielleicht fällt auf, dass \(2^n\) jedes \(f(n)\) teilt. Dividiert man \(f(n)\) durch \(2^n\) dann bleibt \(n\) übrig. Also liegt der Verdacht nahe, dass $$f(n) = n \cdot 2^n$$ Der Induktionsanfang ist mit obiger Tabelle bereits geschehen. Bleibt noch der Induktionsschritt: $$\begin{aligned} f(n+1) &= 4(f(n) - f(n-1)) \\ &= 4(n \cdot 2^n - (n-1)2^{n-1} ) \\ &= 4 \cdot 2^{n-1} (2n - n + 1) \\ &= (n+1)2^{n+1}\end{aligned}$$ q.e.d.