Gegeben ist ein \( 1 \times n \) großes Feld und hinreichend viele blaue Steine der Größe \( 1 \times 1 \), rote Steine der Größe \( 1 \times 1 \) und grüne Steine der Grösse \( 1 \times 2 \).
a) Wir suchen eine rekursive Formel für die Anzahl der Möglichkeiten \( M(n) \), ein \( 1 \times n \) großes Feld mit Steinen abzudecken. Überlegen Sie sich zuerst, wie viele Möglichkeiten es für ein \( 1 \times 1,1 \times 2 \), \( 1 \times 3 \) und \( 1 \times 4 \) großes Feld gibt und finden Sie dann eine Formel für \( M(n) \), die auf Werte von \( M \) für kleinere \( n \) zurückgreift. (Vergessen Sie nicht auf die Basisfälle in der Lösung.)
b) Finden Sie eine explizite Formel für \( M(n) \) mit den Mitteln der VO.