Beweisen dass eine rekursive Darstellung korrekt ist

Question

Aufgabe:

Fur n ∈ N sei An die Anzahl der n-stelligen Zahlen, die aus den Ziffern 0, 1, 2
bestehen, mit 1 beginnen und bei denen zwischen zwei von Null verschiedenen
Ziffern immer mindestens eine 0 steht.

Begründen Sie, dass  An fur n ≥ 3 die Rekursionsgleichung An = An−1+2·An−2
erfüllt und bestimmen Sie die Anfangswerte A1 und A2.

Problem/Ansatz:

Beweis mittels vollständiger Induktion

IA: Sei n = 3

|A1|  = |{1}| = 1

|A2| = |{10}| = 1

|A3| = |{100, 101, 102}| = 3

A3 = A2 + 2*A1 = 1 + 2 = 3

IV: Angenommen die Rekursionsgleichung gilt für ein n ∈ N

IS: Zu zeigen ist, dass die Behauptung auch für Ihren Nachfolger gilt:

An+1 = An + 2An-1

Ab hier weiß ich nicht weiter.

Lg

Answer 1

An+1 = alle um eine 0 am Schluss ergänzten Elemente aus A_n sowie alle um 01 am Schuss ergänzten Elemente aus A_n-1^.

Answer 2

Hallo ocuc,

Es war noch der Begründung für die Rekursionsvorschrift gefragt:

Ich nehme mal die möglichen n-stelligen Zahlen für \(n=4\). Da gibt es fünf Möglichkeiten:$$\begin{array}{rrrr} \color{green}1&\color{green}0&\color{green}0&0 \\ \color{green}1&\color{green}0&\color{green}1&0 \\ \color{green}1&\color{green}0&\color{green}2&0 \\ 1&0&0&1 \\  1&0&0&2 \end{array}$$Wenn man nun eine Stelle (hinten) anhängt, dann kann man dort überall eine \(0\) anhängen um eine gültige Zahl zu bekommen. Das sind \(A_n\) Möglichkeiten. An jede Kombination, die mit einer \(0\) endet kann man statt der \(0\) auch eine \(1\) oder eine \(2\) anhängen. Die Anzahl der Möglichkeiten mit \(0\) am Ende ist aber genau \(A_{n-1}\) (grün markiert). Also kommen nach zweimal \( A_{n-1}\) Möglichkeiten hinzu. Macht:$$A_{n+1} = A_n + 2A_{n-1}$$Die explizite Bildungsformel für \(A_n\) ist$$A_n = \frac13 (2^n - (-1)^n)$$Herleiten lässt sich das genauso wie die Moivre-Binet-Formel für die Fibonacci-Folge. Beweisen kann man das über vollständige Induktion .. das überlasse ich Dir.

Gruß Werner