# Rekursion Binärsystem



## Butterbrot (6. Dez 2015)

Morgen Community,

ich habe folgende Aufgabe:

4. Betrachten wir nun einen Wert im Binärsystem (d. h. bj ∈ {0; 1}) bestehend aus n Ziffern.
a) Bestimmen Sie für den Fall n > 2 die Anzahl f(n) der Zahlen im Binärsystem, die keine zwei
aufeinanderfolgenden Einsen enthalten. Geben Sie für f(n) eine linear rekursive Darstellung
an.
b) Ergänzen Sie Ihre Rekursionsgleichung um eine passende Anfangsbedingungen f(1). Sie
köonnen dabei davon ausgehen, dass f(0) = 1 angenommen werden kann.

Und ich bin ein bisschen baff, denn ich weiß leider nicht wie ich da anfangen soll. Ich wäre für den jeden Tipp dankbar. Danke im Voraus.


----------



## Butterbrot (14. Dez 2015)

Es ist zwar schon eine Weile her, aber leider hat keiner geantwortet. Ich bin mittlerweile selber auf die Antwort gekommen und kann das ja mal für zukünftige Leser posten, die auf das gleiche Problem stoßen werden. 
Die Bestimmung der Anzahl pro n entspricht den Fibonacci-Zahlen. D.h. f(n) = f(n-2) + f(n-1) mit der Anfangsbedingung dass f(1) = 1 und f(0) = 1 ist


----------

