Fibonnaci Zahlen

Aufrufe: 76     Aktiv: 13.06.2021 um 21:12

1
Hallo, ich bräuchte Hilfe bei folgendem Beweis :)

Sei n Element der positiven Natürlichen Zahlen.
Ein (0,1)-Tupel \((x_{1},...,x_{n})\) mit \(x_{i}\) Element von {0,1} heißt (1,1)-vermeidend, wenn für alle i=1,...,n-1 gilt: \(x_{i} * x_{i+1}\) = 0. Zeigen Sie, dass es für n Element der positiven Natürlichen Zahlen genau F(n+1) verschiedene solche Tupel gibt.
Diese Frage melden
gefragt

Student, Punkte: 34

 
Kommentar schreiben
1 Antwort
1
Das geht am besten per Induktion. Für $n=1$ und $n=2$ stimmt es, es gibt $F(2)=2$ bzw. $F(3)=3$ solcher Tupel. Angenommen, die Aussage gelte nun für alle natürlichen Zahlen bis zu $n$. Wie viele passende Tupel der Länge $n+1$ gibt es dann? Für jedes Tupel der Länge $n$, dass auf $1$ endet, gibt es $1$ Tupel der Länge $n+1$, wir können nämlich nur eine $0$ dranhängen. Für jedes Tupel der Länge $n$, dass auf $0$ endet, gibt es $2$ Tupel der Länge $n+1$, denn wir können entweder eine $0$ oder eine $1$ dranhängen. Sei $f(n)$ die Anzahl der passenden Tupel der Länge $n$, dann haben wir gerade die Formel $$f(n+1)=\text{(n-Tupel, die auf 1 enden)}+2\cdot\text{(n-Tupel, die auf 0 enden)}=f(n)+\text{(n-Tupel, die auf 0 enden)}$$ hergeleitet. Ich behaupte jetzt, dass weiter $\text{(n-Tupel, die auf 0 enden)}=f(n-1)$ gilt. Versuch dir mal selber zu überlegen, warum. Damit haben wir die Rekursionsgleichung $f(n+1)=f(n)+f(n-1)$ hergeleitet, aber das ist genau die Rekursionsgleichung der Fibonacci-Zahlen, also sind wir fertig.
Diese Antwort melden
geantwortet

Punkte: 11.1K

 

Viepen vielen dank!   ─   cano 13.06.2021 um 21:12

Kommentar schreiben