Wie genau Beweise ich es jetzt? Rekursiv

Question

Aufgabe:

Es sei ai die Anzahl an Möglichkeiten, ein Feld der Größe 3 × n mit Steinen der Größe 1 × 3 zu pflastern.
Pflastern meint dabei, das Feld vollständig zu bedecken, ohne das ein Stein über das Feld hinaus ragt. Die
Steine können gedreht werden.

I) ai, i = 1, ... , 5 angeben

II) Geben Sie einen rekursiven Ausdruck für an, inklusive Startwert(e), an und beweisen Sie ihn.

Problem/Ansatz:

Fangen wir mit I) an.

Für n = 1   Eine Möglichkeit

-------

-------

-------

Für n = 2   Eine Möglichkeit

-------	-------
-------	-------
-------	-------

Für n = 3   Zwei Möglichkeiten

------	------	------
------	------	------
------	------	------

↓	↓	↓
↓	↓	↓
↓	↓	↓

Für n = 4  Drei Möglichkeiten

↓	↓	↓	↓
↓	↓	↓	↓
↓	↓	↓	↓

→	→	→	↓
→	→	→	↓
→	→	→	↓

↓	←	←	←
↓	←	←	←
↓	←	←	←

Für n = 5  4 Möglichkeiten

↓	↓	↓	↓	↓
↓	↓	↓	↓	↓
↓	↓	↓	↓	↓

↓	↓	←	←	←
↓	↓	←	←	←
↓	↓	←	←	←

←	←	←	↓	↓
←	←	←	↓	↓
←	←	←	↓	↓

↓	←	←	←	↓
↓	←	←	←	↓
↓	←	←	←	↓

Also es gilt:

ai	an
1	1
2	1
3	2
4	3
5	4

1  =>  1 (+0)         1 => 2 (+1)            2 => 3 (+1)           3=>4 (+1)

Hier beginnt die II)

Vermutung: Die Formel lautet: a_n+1 = a_n + a_n-2 

_{Bsp: 4 = 3 + 1:       Testen mit n = 6:   4 + 2 = 6     => 6 Möglichkeiten (Selbsttest zeigte, 6 nur möglich "außer ich habe eine Formvergessen")}

Also gilt die Formel: Also haben wir einen Startwert sowie rekursiven Ausdruck

Wie genau Beweise ich es jetzt?

Meine Überlegung:    Die 1 x 3 großen Steinen spielen eine Rolle

Wir können Sie 1 x 3 auslegen oder in 3 x 1

heißt:  3x1 haben wir die Möglichkeit a_n Pflaster zu platzieren, da es keine andere Möglichkeit existiert

↓

↓

↓

bei 3x3    haben wir a_n-2 Möglichkeiten Pflaster zu platzieren, quasi vertikale oder horizontale

←	←	←
←	←	←
←	←	←

Durch die Summenregel gilt dann:      an+1 = an + an-2

Meine Frage an euch: Wäre es soweit richtig? oder habe ich irgendwo Logische Lücken

Comments

Bei einem 3 x (n+1 ) Feld:

Du kannst in die letzte Spalte ein Stein legen. Dann bleiben 3 x n Felder übrig mit \( a_n \) Möglichkeiten

Oder du legst da 3 Stein quer rein. Dann bleibt ein 3 x (n-2) Feld mit \( a_{n-2} \) Möglichkeiten.

Ergibt

\( a_{n+1} = a_n + a_{n-2} \)

mögliche Parkettierungen.

Answer 1

Beweisskizze:

Durch kombinatorische Überlegungen bin ich auf die explizite Form $$a_n=\sum_{i=0}^{\lfloor\frac{n}{3}\rfloor}\binom{n-2i}{i}$$ gekommen.

Durch Einsetzen und einer Fallunterscheidung von n+1 durch drei teilbar und n+1 nicht durch drei teilbar, kann man die rekursive Formel beweisen.

Falls du den genauen Beweis haben willst, schreib mir einfach. Ich hab jetzt den Beweis nur skizziert, weil, falls die Aufgabe für dich an Relevanz verloren hat, es die Schreibarbeit nicht wert ist.

LG