Mit Hilfe der Fibonacci-Zahlen die Anzahl fn der Folgen der Länge n bestehend aus … bestimmen ?

Question

Bestimmen Sie mit Hilfe der Fibonacci-Zahlen die Anzahl fn der Folgen der L¨ange n bestehend aus Elementen der Menge {0,1}, so dass niemals zwei Nullen hintereinanderstehen. Beispielsweise ist die Folge 10111 erlaubt, die Folge 10011 nicht.
Hinweis: Man unterteile die Menge dieser Folgen in zwei disjunkte Teilmengen, n¨amlich mit 0 bzw. 1 als letztem Folgenglied (= Teile und Herrsche) und leite eine rekursive Beziehung fur diese Teilmenge her

Answer 1

Alle Folgen der Länge n+1 erhältst du, wenn du alle Folgen der Länge n hernimmst und dort ans Ende eine 1 anhängst oder eine Null anhängst (falls das erlaubt ist).

Baue mal von dieser Idee ausgehend alle Folgen der Länge 1, 2, 3, 4 bzw. 5 auf, dann siehst du das System.