Rekursionsformel für eine Folge finden

Question

Aufgabe:

Für n∈ℕ sei b_n die Anzahl der 0-1 Folgen der Länge n, in denen zwei direkt aufeinanderfolgende Nullen vorkommen

a) b_1, b₂  und b₃ bestimmen

b) die Rekursionsformel für b_n finden 

Ich hänge bei einer Aufgabe ein wenig, vielleicht kann mir jemanden helfen.

Danke schonmal

Comments

b_n  =  b_n-1 + b_n-2 + 2^n-2

---

Das ist keine echte rekursive Bildungsvorschrift, sondern eine gemischt rekursiv/explizite Vorschrift.

Rekursiv ist sie erst dann, wenn du den letzten Summanden ohne den expliziten Zugriff auf den Wert von n hinbekommst.

Zudem fehlen die Anfangsglieder (was ich dir keineswegs vorwerfe, denn das wäre eine minimalst zu erbringende Eigenleistung des Fragestellers).

Aber der Fragesteller hat nur einmal kurz Luft geholt und ist wieder abgetaucht.

---

Na gut, dann eben
b_n  =  3b_n-1 - b_n-2 - 2b_n-3

---

Meine erste Gleichung lässt sich leicht anschaulich "ohne Worte" beweisen :

Meine zweite Version lässt sich mit der Hilfsgröße  Δ_n = b_n - b_n-1  in die etwas gefälligere Form umschreiben zu  b_n = 3Δ_n-1 + 2Δ_n-2 .  Sieht jemand einen direkten einfachen Beweis für diese Gleichung ?

---

lässt sich leicht anschaulich "ohne Worte" beweisen :

Ich versuche es dann doch mal mit Worten.

Die Anzahl der 0-1-Folgen der Länge n mit mindestens einer Doppel-Null ist:

Anzahl der Folgen der Länge n-1, die bereits eine Doppel-Null hatten

plus

Anzahl der Folgen der Länge n-1, die keine Doppel-Null hatten, aber auf 0 enden und somit mit einer weiteren 0 fortgesetzt werden können.

---

Kannst du das näher erläutern ?
Immerhin ist die Anzahl der Folgen der Länge 6 mit einer Doppelnull größer als die Anzahl aller Folgen der Länge 5 überhaupt .

---

Was soll ich näher erläutern? Die Klassifizierung der beiden Möglichkeiten ist doch eindeutig.

---

Aber offenbar - darauf wollte ich dich hinweisen - ist sie falsch.

---

Du hast das Recht auf eine eigene Meinung.

---

So eigen ist sie nicht :  http://oeis.org/A008466

---

Ich bleibe dabei: Die Klassifizierung stimmt. Der zweite Fall ist nur  schwer zu berechnen.

---

Und im ersten Fall unterschlägst du, dass es nicht nur eine mögliche Fortsetzung gibt.

---

Einverstanden. Hier habe ich das "mal 2" unterschlagen-

---

Der zweite Fall  (Anzahl der Folgen der Länge n-1, die keine Doppel-Null hatten aber auf 0 enden)  ist nur  schwer zu berechnen.

Warum schwer ?  Es ist doch einfach die Anzahl der Folgen der Länge n-2, die keine Doppel-Null haben und das ist wiederum Fibo(n)  [ in der Zählung Fibo(3) = 2 ] .

Jetzt bleibt dir nur noch die Aufgabe, aus dem Ganzen eine Rekursion für b_n zusammenzubasteln.