Wie viele Teilmengen, die keine zwei aufeinander folgenden Zahlen enthalten, besitzt die Menge {1,...,n}?

Question

Aufgabe:

Wie viele Teilmengen, die keine zwei aufeinander folgenden Zahlen enthalten, besitzt die Menge {1,...,n}?

Lösen Sie die Aufgabe mit einer Rekursion und vergessen Sie die leere Menge nicht.

Comments

Immer erst einmal kleine Beispiele überlegen:

n = 1: ∅, {1}

n = 2: ∅, {1}, {2}

n = 3: ∅, {1}, {2}, {3}, {1,3}

n = 4: ∅, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}

n = 5: ∅, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, {5}, {1,5}, {2,5}, {3,5}, {1,3,5}

Hier erkennst du hoffentlich ein Muster. Die Anzahl der Teilmengen wir also durch die Folge

$$a_1 = 2, a_2 = 3$$ $$a_{n} = a_{n-1} + a_{n-2}$$

beschrieben

Answer 1

Sei $P(n)$ die Menge aller Teilmengen von $\{1,\dots,n\}$, die keine zwei aufeinander folgenden Zahlen enthalten.

Die Elemente von $P(n)$ lassen sich in zwei Klassen einteilen:

• Mengen die Element von $P(n-1)$ sind.
  
• Mengen die aus Elemente von $P(n-2)$ entstanden sind indem $n$ hinzugefügt wurde.