Gegeben
Für n ∈ N sei Tn die Menge der Tupel in {0, 1}^n, die keine zwei aufeinanderfolgenden Nullen enthalten und An deren Anzahl, d. h.
Tn := {(x1, . . . , xn) ∈ {0, 1}n | Für alle k ∈ {1, . . . , n − 1} gilt Xk ungleich 0 oder Xk+1 ungleich 0} .
Für jedes n ∈ N sei An die Anzahl der Elemente von Tn.
(Für n = 3 sind Tn = {(0, 1, 0),(0, 1, 1),(1, 0, 1),(1, 1, 0),(1, 1, 1)} und An = 5.)
Aufgabe:
Eine Rekursionsgleichung für An angeben und Begründen wieso diese Rekursionsgleichung gilt.
Problem/Ansatz:
Meine ermittelte Rekursionsgleichung ist: An+1 = An+An-1