Fibonacci Folge

05.11.2017, 14:28

Numerus

Fibonacci Folge

Hallo zusammen, ich soll einen Induktionsbeweis führen. Die Aufgabe lautet:

Die Fibonacci Zahlen sind definiertz durch folgende Bedingung: $\begin{eqnarray*} f_1=f_2=1 \end{eqnarray*}$ und $\begin{eqnarray*} f_{n+2}=f_{n+1}+f_n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$

Zeige für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ :

a) $\begin{eqnarray*} f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)\right)^n-\left(\left(\frac{1-\sqrt{5}}{2}\right)\right)^n \end{eqnarray*}$

I.A.: $\begin{eqnarray*} n=2 \end{eqnarray*}$ gilt:

$\begin{eqnarray*} f_2=f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)\right)^2-\left(\left(\frac{1-\sqrt{5}}{2}\right)\right)^2 \end{eqnarray*}$

$\begin{eqnarray*} f_2=1 \end{eqnarray*}$

Damit passt der I.A.

I.V.: Für ein $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ gilt $\begin{eqnarray*} f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)\right)^n-\left(\left(\frac{1-\sqrt{5}}{2}\right)\right)^n \end{eqnarray*}$

I.S. $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$

$\begin{eqnarray*} f_{n+1}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)\right)^{n+1}-\left(\left(\frac{1-\sqrt{5}}{2}\right)\right)^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} f_{n+1}=\left(\left(f_n\left(\frac{1+\sqrt{5}}{2}\right)-f_n\left(\frac{1-\sqrt{5}}{2}\right)\right)\right) \end{eqnarray*}$

$\begin{eqnarray*} f_{n+1}=\frac{f_n}{\sqrt{5}} \end{eqnarray*}$

Irgendwie weiß ich noch nicht so genau ob das passt. Kann jemand helfen?

Viele Grüße

05.11.2017, 15:03

Mathema

Auf diesen Beitrag antworten »

Hallo,

das stimmt leider überhaupt nicht. Zudem hast du anscheinend schon die Aufgabenstellung falsch aufgeschrieben. Verbessere das bitte. Dann wird hier eine Induktion $\begin{eqnarray*} n,n+1\leadsto n+2 \end{eqnarray*}$ geführt. Da kannst du also nicht nur ein Wert prüfen im IA. Um Schreibarbeit zu sparen würde ich dann mal folgende Substitution empfehlen:

$\begin{eqnarray*} x:=\frac{1+\sqrt{5}}{2} \end{eqnarray*}$

$\begin{eqnarray*} y:=\frac{1-\sqrt{5}}{2} \end{eqnarray*}$

Überarbeite also deinen IA und zeige dann im IS:

$\begin{eqnarray*} f_{n+1}+f_n=\frac{1}{\sqrt{5}}\left(x^{n+1}-y^{n+1}\right)+\frac{1}{\sqrt{5}}\left(x^{n}-y^{n}\right)=...=f_{n+2} \end{eqnarray*}$

Viel Erfolg!

12.11.2017, 13:04

Numerus

Auf diesen Beitrag antworten »

Hallo, die Aufgabenstellung lautet konkret:
Die Fibonacci Zahlen $\begin{eqnarray*} f_n \end{eqnarray*}$ sind durch folgende Bedingung definiert: $\begin{eqnarray*} f_1=f_2=1 ,~ f_{n+2}=f_{n+1}+f_n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$
Zeige: Für alle $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ bzw $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ gilt:

$\begin{eqnarray*} f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)\right)^n-\left(\left(\frac{1-\sqrt{5}}{2}\right)\right)^n \end{eqnarray*}$

Warum kann ich den IA nicht mit $\begin{eqnarray*} n=2 \end{eqnarray*}$ machen?

Viele Grüße

12.11.2017, 13:17

Numerus

Auf diesen Beitrag antworten »

Ich sehe noch nicht so ganz wo ich die IV einbringen soll. Ich kann mithilfe der Potenzgesetze den Ausdruck zwar umschreiben aber das bringt mich doch nicht wirklich weiter ...

$\begin{eqnarray*} f_{n+1}+f_n=\frac{1}{\sqrt{5}}\left(x^{n+1}-y^{n+1}\right)+\frac{1}{\sqrt{5}}\left(x^{n}-y^{n}\right)=x^n(\frac{1}{\sqrt{5}}+x)-y^n(\frac{1}{\sqrt{5}}+y) \end{eqnarray*}$

12.11.2017, 16:20

Mathema

Auf diesen Beitrag antworten »

Zitat:

Original von Numerus
$\begin{eqnarray*} f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)\right)^n-\left(\left(\frac{1-\sqrt{5}}{2}\right)\right)^n \end{eqnarray*}$

Nein - so steht es sicherlich nicht in der Aufgabe. unglücklich

Zitat:

Original von Numerus
Warum kann ich den IA nicht mit $\begin{eqnarray*} n=2 \end{eqnarray*}$ machen?

Das habe ich doch geschrieben. Wir nutzen doch im IS die Rekursionsgleichung $\begin{eqnarray*} f_{n+2}=f_{n+1}+f_n \end{eqnarray*}$ . Für $\begin{eqnarray*} n=2 \end{eqnarray*}$ steht da also $\begin{eqnarray*} f_{4}=f_{3}+f_2 \end{eqnarray*}$ . Das deine Formel für $\begin{eqnarray*} f_2 \end{eqnarray*}$ stimmt hast du nachgewiesen, aber über $\begin{eqnarray*} f_3 \end{eqnarray*}$ wissen wir leider überhaupt nichts, das existiert in unserer Welt überhaupt noch nicht. Wie wollen wir dann auf $\begin{eqnarray*} f_4 \end{eqnarray*}$ schließen?

Zitat:

$\begin{eqnarray*} f_{n+1}+f_n=\frac{1}{\sqrt{5}}\left(x^{n+1}-y^{n+1}\right)+\frac{1}{\sqrt{5}}\left(x^{n}-y^{n}\right)=x^n(\frac{1}{\sqrt{5}}+x)-y^n(\frac{1}{\sqrt{5}}+y) \end{eqnarray*}$

Das stimmt nicht. Wie sollte denn nun $\begin{eqnarray*} f_{n+2} \end{eqnarray*}$ aussehen überhaupt?

12.11.2017, 16:43

Numerus

Auf diesen Beitrag antworten »

Ich habe nochmal nachgeschaut. So steht es dort:
$\begin{eqnarray*} f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) \end{eqnarray*}$

Wie führe ich denn nun den IA? Kannst du dort mal etwas konkreter werden?

Im IS würde ich mal sagen das $\begin{eqnarray*} f_{n+2}=\frac{1}{\sqrt{5}}(x^{n+2}-y^{n+2}) \end{eqnarray*}$ aussehen muss.

Viele Grüße

12.11.2017, 17:20

Mathema

Auf diesen Beitrag antworten »

Du musst im IA noch den Fall $\begin{eqnarray*} n=1 \end{eqnarray*}$ prüfen. Wenn also $\begin{eqnarray*} f_1=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^1-\left(\frac{1-\sqrt{5}}{2}\right)^1\right)\stackrel{?}{=}1 \end{eqnarray*}$ gilt und $\begin{eqnarray*} f_2=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^2\right)=1 \end{eqnarray*}$ (das hast du ja nachgewiesen), dann dürfen wir also nun die Rekursionsgleichung benutzen und führen eine Induktion $\begin{eqnarray*} n,n+1\leadsto n+2 \end{eqnarray*}$ .

Zitat:

Im IS würde ich mal sagen das $\begin{eqnarray*} f_{n+2}=\frac{1}{\sqrt{5}}(x^{n+2}-y^{n+2}) \end{eqnarray*}$ aussehen muss.

Das bauen wir gleich mal ein:

$\begin{eqnarray*} f_{n+1}+f_n=\frac{1}{\sqrt{5}}\left(x^{n+1}-y^{n+1}\right)+\frac{1}{\sqrt{5}}\left(x^{n}-y^{n}\right)=...=\frac{1}{\sqrt{5}}(x^{n+2}-y^{n+2})=f_{n+2} \end{eqnarray*}$

Nun mach mal weiter. Was könnten wir zunächst einmal gut machen?

12.11.2017, 17:58

Numerus

Auf diesen Beitrag antworten »

Im IA gilt auch f_1=1 das habe ich gerade nochmal nachgerechnet.

Im IS kann man den Vorfaktor erstmal ausklammern.

$\begin{eqnarray*} f_{n+1}+f_n=\frac{1}{\sqrt{5}}\left(x^{n+1}-y^{n+1}\right)+\frac{1}{\sqrt{5}}\left(x^{n}-y^{n}\right)=\frac{1}{\sqrt{5}}(x^{n+1}-y^{n+1}+x^n+y^n) \end{eqnarray*}$
$\begin{eqnarray*} =\frac{1}{\sqrt{5}}(x^{n}x-y^{n}y+x^n+y^n)=\frac{1}{\sqrt{5}}(x^{n+2}-y^{n+2})=f_{n+2} \end{eqnarray*}$

Jetzt auch noch ausklammern. Das habe ich allerdings auch schon vorgeschlagen. Irgendwo muss ja die IV eingebracht werden ...

Viele Grüße

edit Mathema: Zeilenumbruch eingefügt

12.11.2017, 18:18

Mathema

Auf diesen Beitrag antworten »

Die hast du doch schon eingebracht:

$\begin{eqnarray*} f_{n+1}+f_n\stackrel{IV}{=}\frac{1}{\sqrt{5}}\left(x^{n+1}-y^{n+1}\right)+\frac{1}{\sqrt{5}}\left(x^{n}-y^{n}\right)=\frac{1}{\sqrt{5}}(x^{n+1}-y^{n+1}+x^n \textcolor{red}{-}y^n) \end{eqnarray*}$

Das rote Vorzeichen war bei dir verkehrt.

Zitat:

Jetzt auch noch ausklammern.

Jap, dann steht da also:

$\begin{eqnarray*} =\frac{1}{\sqrt{5}}(x^{n}x-y^{n}y+x^n-y^n)=\frac{1}{\sqrt{5}}(x^n(x+1)-y^n(y+1))\stackrel{?}{=}\frac{1}{\sqrt{5}}(x^{n+2}-y^{n+2})=f_{n+2} \end{eqnarray*}$

Für die mit dem Fragezeichen gekennzeichnet Gleichheit muss also gelten:

$\begin{eqnarray*} x^2=x+1 \end{eqnarray*}$ und $\begin{eqnarray*} y^2=y+1 \end{eqnarray*}$

Das müsstest du nun noch mal nachrechnen. Stimmt es, wäre die Induktion geschlossen.

12.11.2017, 18:44

Numerus

Auf diesen Beitrag antworten »

Super, jetzt sollte ich es hinbekommen. Vielen Dank für deine Hilfe. Falls noch eine Frage auftauchen sollte, melde mich mich nochmal.

Viele Grüße

12.11.2017, 18:45

Mathema

Auf diesen Beitrag antworten »

Das kannst du gerne machen! Ansonsten wünsche ich dir einen schönen Abend.

Wink

Neue Frage »

Antworten »

Fibonacci Folge

Verwandte Themen