Rekursion Binärsystem

Butterbrot

Aktives Mitglied
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

Aktives Mitglied
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
 

Neue Themen


Oben