Induktion über fib(h) = (Φ^h - (1-Φ)^h) / 2Φ -1

Question

Beweisen Sie die folgende Aussage, wobei Φ = (1+√5) / 2 ist.

Bewiesen ist bis jetzt, dass gilt:

Φ² = Φ +1

sowie 

(1-Φ)² = 2-Φ.

Mit vollständiger Induktion soll bewiesen werden, dass gilt:

fib(h) = (Φ^h - (1-Φ)^h) / 2Φ -1

Die Induktionsanfänge mit h=0 und h=1 sind trivial, nur weiß ich nicht so wirklich wie ich bei h -> h+1 vorgehen soll.

fib(h+1) = (Φ^h+1 - (1-Φ)^h+1) / 2Φ -1

Als Hinweis wurde mitgegeben, dass die obigen Ergebnisse als Lemmata genutzt werden können.

Liebe Grüße aus dem sonnigen Kaiserslautern &

 

P.S.: Gibt Kuchen als Belohnung ;-)

Answer 1

Hi,

Ich gehe davon aus das Du die Fibonaci Folge meinst.

Setze zur Abkürzung \( \Psi=1-\Phi \) dann gilt wegen der Induktionsvoraussetzung

$$ f_n+f_{n-1}=\frac{\Phi^{n}-\Psi^{n}}{2\Phi-1}+\frac{\Phi^{n-1}-\Psi^{n-1}}{2\Phi-1}= $$

$$ \frac{1}{2\Phi-1} \left[ \Phi^n \left( 1+\frac{1}{\Phi} \right)-\Psi^n \left( 1+\frac{1}{\Psi} \right) \right] $$

Bewiesen habt ihr ja schon das gilt \( \Phi^2=\Phi+1 \) also \( \Phi=1+\frac{1}{\Phi} \) und \( \Psi^2=2-\Phi=\Psi+1 \) also auch hier \( \Psi=1+\frac{1}{\Psi} \)

Daraus folgt

$$ f_n+f_{n-1}=\frac{1}{2\Phi-1} \left[ \Phi^{n+1}-\Psi^{n+1}  \right]=f_{n+1} $$

 

siehe auch https://de.wikipedia.org/wiki/Fibonacci-Folge