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.