Zuerst mal etwas Grundsätzliches zur Rekursion:
Meistens besitzt man zum Beenden der Rekursion nur einen bekannten Wert, z.B. \(f(0)\). Es ist aber völlig OK, wenn man zwei (oder viele) bekannte Werte benötigt (und diese auch besitzt), z.B. \(f(0)\) und \(f(1)\), wie bei Fibonacci.
Jetzt zu deiner Aufgabe:
Wie viele unterschiedliche Folgen der Länge \( n+1 \) kann man aus den Zeichen \( 0,1 \) bilden, in denen mindestens einmal zwei Nullen hintereinander stehen?
Zum Verständnis lohnt es sich, erst mal alle möglichen Folgen der Länge \( n+1 \) in drei Klassen einzuteilen:
\(A_n\) sind alle Folgen der Länge \( n+1 \). Davon gibt es \( a_n = 2^{n+1} \) Stück.
\(B_n\) sind die Folgen, die ein \(0,0\) Paar enthalten.
\(C_n\) sind die Folgen, die kein \(0,0\) Paar enthalten und auf eine \(0\) enden.
\(D_n\) sind die Folgen, die kein \(0,0\) Paar enthalten und auf eine \(1\) enden.
Sicher gilt \( a_n = b_n + c_n + d_n \).
In der Rekursion hängen wir an die Folgen der Länge \(n\) hinten eine \(0\) oder eine \(1\) an.
\( b_n = 2 \cdot b_{n-1} + c_{n-1} \), mit \(0\) oder \(1\) an einer \(B\)-Folge oder einer weiteren \(0\) an einer \(C\)-Folge.
\( c_n = d_{n-1} \), mit einer \(0\) an einer \(D\)-Folge.
\( d_n = c_{n-1} + d_{n-1} \), mit einer \(1\) an einer \(C\)- oder \(D\)-Folge.
Wenn man genau hinschaut, kann man jetzt eine Fibonacci-Folge erkennen:
\( d_n = d_{n-2} + d_{n-1} \)
und unsere Summenformel vereinfacht sich zu
\( a_n = b_n + d_{n+1} \)
Eine zulässige Lösung wäre also
\( b_n = 2^{n+1} - d_{n+1} \), ohne Rekursion.
\( d_n = d_{n-2} + d_{n-1} \), analog Fibonacci.
Sonstiger Berufsstatus, Punkte: 242