Mengen auflisten mit verschiedenen Kriterien sowie Bestimmung der Kardinalität und finden einer Rekursionsvorschrift

Question

Aufgabe:

n ∈ ℕ für die Menge

                M_n := {(a1,...,a_n ∈{0,1}ⁿ : außerdem gibt es kein i ∈ {1,...,n-1}, so dass a_i = a_i+1 = 0},

0-1-Folgen der Länge n, in denen das Vorkommen von 00 verboten ist.

(a) Angeben der Mengen M2, M3 und M4 (Elemente auflisten). Dazu noch die Kardinalitäten der Mengen bestimmen.
(b) Für n ∈ ℕ liegt die Menge M_n durch Auflistung der Elemente vor. Geben Sie eine Vorschrift
an, wie Sie mit dieser Auflistung die Elemente aus M_n+1 finden können.
(c) Finden Sie mit Ihren Ideen aus Aufgabenteil (b) eine Rekursionsvorschrift1 für |M_n+1|.

Problem/Ansatz:

ich weiß bei der Aufgabe nicht wie ich da vorgehen muss und wo ich anzufangen habe. Es wäre nett, wenn mir jemand erklären könnte was zu tun ist. Ich verlange nicht die Lösung zu den Aufgaben, lediglich worauf ich zu achten habe und was ich bei einer derartigen Aufgabe zu tun habe.

Danke

Answer 1

Wenn Du die Anzahl \(|M_n|\) der möglichen Folgen der Länge \(n\) betrachtest, so kannst Du diese aufteilen nach$$|M_n| = k_{n(0)} + k_{n(1)}$$wobei \(k_{n(0)}\) die Anzahl der Folgen sein soll, die auf \(0\) enden und \(k_{n(1)}\) die Anzahl der Folgen, die auf \(1\) enden.

Wenn man nun den Übergang nach \(n+1\) macht, so kann man an jede der \(k_{n(0)}\)-Folgen nur eine \(1\) hängen, die \(0\) wäre ja eine Doppel-\(0\) und nicht erlaubt. Wohingegen man hinter alle der \(k_{n(1)}\)-Folgen sowohl eine \(0\) als auch eine \(1\) hängen kann. Man kann diese Anzahl also verdoppeln. Also ist:$$|M_{n+1}| = k_{n(0)} + 2 k_{n(1)}$$und natürlich lässt sich auch diese Menge in die mit \(0\) und die mit \(1\) endenden aufteilen$$|M_{n+1}| = k_{n+1(0)} + k_{n+1(1)}$$und es ist$$k_{n+1(0)} = k_{n(1)} \\ k_{n+1(1)} = k_{n(0)} + k_{n(1)}$$... mit dem Hinweis sollte alle Unterpunkte kein Problem mehr sein. Falls doch, so frage bitte nach.

Gruß Werner