Rekursions-Training

Eine Treppe mit 6 Stufen wird mit Schritten der Länge 1 oder 2 bestiegen. Wie viele Schrittfolgen gibt es?

Ein $2\times5$-Streifen wird mit $2\times1$-Dominosteinen gepflastert. Wie viele Pflasterungen gibt es?

Wie viele Binärwörter der Länge 5 enthalten keine zwei benachbarten Einsen?

Wie viele geordnete Summendarstellungen von 7 mit Summanden 1 und 2 gibt es?

Leite rekursiv her, dass eine $n$-elementige Menge $2^n$ Teilmengen besitzt.

Wie viele Binärwörter der Länge 5 enthalten weder 000 noch 111 als Teilwort?

Nutze $D_n=(n-1)(D_{n-1}+D_{n-2})$ mit $D_1=0,D_2=1$, um $D_5$ zu berechnen.

Welche Angaben sind nötig, damit $a_n=a_{n-1}+a_{n-2}$ eine Folge eindeutig bestimmt? Begründe.