0 Daumen
312 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community