Für \( n \in \mathbb{N} \) sei \( T_{n} \) die Menge der Tupel in \( \{0,1\}^{n} \), die keine zwei aufeinanderfolgenden Nullen enthalten und \( A_{n} \) deren Anzahl, d. \( \mathrm{h} \).
\( T_{n}:=\left\{\left(x_{1}, \ldots, x_{n}\right) \in\{0,1\}^{n} \mid\right. \) Für alle \( k \in\{1, \ldots, n-1\} \) gilt \( x_{k} \neq 0 \) oder \( \left.x_{k+1} \neq 0\right\} \)
Für jedes \( n \in \mathbb{N} \) sei \( A_{n} \) die Anzahl der Elemente von \( T_{n} \). (Für \( n=3 \operatorname{sind} T_{n}=\{(0,1,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)\} \) und \( \left.A_{n}=5 .\right) \)
(a) Bestimmen Sie \( T_{n} \) und \( A_{n} \) für \( n \in\{1,2,4\} \).
(b) Geben Sie eine Rekursionsgleichung für \( A_{n} \) an.
Begründen Sie, wieso die von Ihnen angegebene Rekursionsgleichung gilt!
Hinweis: Ein typisches Vorgehen bei solchen Aufgaben ist es, sich zunächst zu überlegen, mit welcher Ziffer \( x_{n} \) oder mit welchen Ziffernfolgen \( x_{n-1}, x_{n} \) (ggf. bis \( x_{n-k}, \ldots, x_{n} \) für passendes \( k \) ) die Tupel \( \left(x_{1}, \ldots, x_{n}\right) \) in \( T_{n} \) enden können, und anschließend zu überlegen, in welcher Beziehung die diesen Endziffern jeweils vorausgehenden kleineren Tupel \( \left(x_{1}, \ldots, x_{n-1}\right) \) oder \( \left(x_{1}, \ldots, x_{n-2}\right)\left(\right. \) oder \( \left.\left(x_{1}, \ldots, x_{n-k-1}\right)\right) \) zu den Mengen \( T_{n-1} \) oder \( T_{n-2} \) (ggf. bis \( T_{n-k-1} \) ) ) stehen. Aus der Vorschrift (oder Beobachtung), wie sich die Tupel in \( T_{n} \) aus Tupeln in \( T_{n-1} \) usw. konstruieren lassen - und zwar so, dass Sie jedes Tupel in \( T_{n} \) auch genau einmal konstruieren - erhalten Sie dann die entsprechende Rekursionsgleichung für die Anzahl \( A_{n} \) dieser Tupel auf Basis der Anzahlen \( A_{n-1} \) usw. der kleineren Tupel.
(c) Erlauben wir in den Tupeln nicht nur die Ziffern 0 und 1 , sondern auch die 2 , so erhalten wir für die Anzahl \( B_{n} \) der Tupel der Länge \( n \) ohne aufeinanderfolgende Nullen die Werte \( B_{1}=3, B_{2}=8, B_{3}=22, \) usw. sowie die Rekursionsformel \( B_{n}=2 \cdot B_{n-1}+2 \cdot B_{n-2} \) für alle \( n \geq 3 \).
Leiten Sie eine explizite Formel für \( B_{n} \) her, d. h. berechnen Sie \( a_{1}, a_{2}, \lambda_{1}, \lambda_{2} \in \mathbb{R}, \) so dass \( B_{n}=a_{1} \cdot \lambda_{1}^{n}+ \) \( a_{2} \cdot \lambda_{2}^{n} \) für alle \( n \in \mathbb{N} \) gilt. (Aus Ihren Lösungen sollte ersichtlich sein, wie Sie zu diesen reellen Konstanten gelangen.
Hinweis: Es handelt sich um eine lineare Rekursion.
Problem/Ansatz:
Ich habe es geschafft \( T_{n} \) mit der Anzahl für ein n zu bilden. Weiß aber ehrlich gesagt nicht wie ich auf eine Rekursionsformel schließen könnte.
Ich bin mir auch nicht sicher, ob eine Rekursionsformel für A oder für T gefordert ist.
n = 1 A = 2
n = 2 A = 3
n = 3 A = 5
n = 4 A = 8
Alles was ich erkennen kann ist, dass diese Gleichung möglicherweise etwas mit der Fibonacci-Folge zu tuen hat, weil diese auch die Zahlen 2,3,5,8 enthält. Allerdings bin ich mir da nicht sicher.
Ich würde mich für Lösungswege / Lösungen für die b) und c) interessieren, damit ich diese mehr verstehen kann.
