Beweis an der Fibonaccifolge

01.05.2007, 20:21

mYthos

Beweis an der Fibonaccifolge

Hallo!

Eine Schülerin sitzt gerade neben mir und sie präsentiert mir eine mir bis dato unbekannte Beziehung, die zwischen drei aufeinanderfolgenden Gliedern einer Fibonaccifolge bestehen soll:

$\begin{eqnarray*} f_{n+1}^2 + f_{n+2}^2 = f_{2n+3} \end{eqnarray*}$

Die Fibonaccifolge sei rekursiv folgendermaßen definiert:

$\begin{eqnarray*} f_n = f_{n-1} + f_{n-2} \end{eqnarray*}$

Den Beweis wollen wir mittels vollständiger Induktion führen. Unsere bisherigen Versuche führten nicht zum gewünschten Ergebnis.

Die Frage ist nun, ob diese Formel überhaupt richtig ist (mit einigen Werten für n wurde sie allerdings überprüft und für richtig befunden) und - was weit schwieriger erscheint - ob der Beweis überhaupt mit vollständiger Induktion durchführbar ist.

Wer weiß Rat?

Gr
mYthos+

01.05.2007, 20:27

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis an der Fibonaccifolge
Vielleicht seien noch die Anfangswerte erwähnt.

$\begin{eqnarray*} f_0=0,f_1=1 \end{eqnarray*}$

Damit ergibt sich (Quelle Wikipedia)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1.597, 2.584, 4.181, 6.765, 10.946, 17.711, 28.657, 46.368, 75.025, 121.393, 196.418, 317.811, 514.229, 832.040, 1.346.269, 2.178.309, ...

Bis wohin habt ihr den manuell "probiert"?

01.05.2007, 20:41

kiste

Auf diesen Beitrag antworten »

Ob die Behauptung richtig ist lässt sich ja überprüfen in dem die explizite Darstellung einsetzt oder?

$\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*}$

01.05.2007, 20:41

mYthos

Auf diesen Beitrag antworten »

@tigerbine
Na ja, bis 2000000 sicher nicht Big Laugh

, aber in der Formel scheint kein Widerspruch zu stecken. Vielleicht hast du mich missverstanden. Uns geht es eigentlich eher darum, ob und wie der Beweis mittels vollständiger Induktion durchführbar ist.

@kiste

Danke! Wir werden das mal verifizieren ...

Allerdings sollten wir den Beweis ausgehend von der rekursiven Darstellung durchführen.

mY+

01.05.2007, 20:47

therisen

Auf diesen Beitrag antworten »

Hallo,

ich kann bestätigen, dass die Formel richtig ist (mit der expliziten Darstellung).

Gruß, therisen

01.05.2007, 21:17

Guest123

Auf diesen Beitrag antworten »

Hallo,

das Problem lässt sich am einfachsten über die Additionsformel für Fibonacci-Zahlen beweisen:
$\begin{eqnarray*} f_{n+m} = f_{n}\cdot f_{m-1} + f_{n+1}\cdot f_{m} \end{eqnarray*}$
Diese lässt sich relativ leicht mittels voll. Induktion zeigen.

Daraus folgt für m = n+1:
$\begin{eqnarray*} f_{2n+1} = f_{n}^2 + f_{n+1}^2 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow f_{2n+3} = f_{n+1}^2 + f_{n+2}^2 \end{eqnarray*}$

01.05.2007, 22:50

Auf diesen Beitrag antworten »

Zur Eigenschaft

$\begin{eqnarray*} a_{n+m} = a_{n}a_{m-1} + a_{n+1}a_{m} \end{eqnarray*}$

ist übrigens anzumerken, dass sie für sämtliche rekursiven Folgen

$\begin{eqnarray*} a_0=0,\; a_1=1,\; a_n=\lambda a_{n-1} + a_{n-2} \end{eqnarray*}$

gilt, also nicht nur $\begin{eqnarray*} \lambda=1 \end{eqnarray*}$ (Fibonacci). Wink

01.05.2007, 22:55

mYthos

Auf diesen Beitrag antworten »

Vielen Dank für die bisherigen zahlreichen Antworten.
Ich halte mich derzeit in Deutschland auf und habe daher nicht oft Zugang zum Internet.
Das Problem wurde mir von Mareike., die sich ebenfalls heute hier registriert hat, gestellt, und ich kann dies im Moment nicht weiter verfolgen. Gegebenenfalls wird sich Mareike. noch in diesem Thread dazu äußern.
Die Aufgabe hat sich nunmehr auf den Beweis der von Guest123 angegebenen Additionsformel verlagert. Das bereitet uns deswegen wiederum Schwierigkeiten, weil es nunmehr zwei Indizes (m,n) gibt und normalerweise solche Induktionsbeweise immer nur mit einem Index geführt werden. Also muss man einen Index festhalten, klarerweise. Es wird aber dennoch nicht leichter (vielleicht liegt's an meiner momentanen Urlaubsstimmung oder so), aber wir müssen uns das noch ansehen.

Bis denn und Gruß
mYthos+

01.05.2007, 23:02

Auf diesen Beitrag antworten »

Du kannst den Induktionsbeweis über $\begin{eqnarray*} n \end{eqnarray*}$ führen und $\begin{eqnarray*} m \end{eqnarray*}$ dabei fest lassen! Induktionsanfang $\begin{eqnarray*} n=0 \end{eqnarray*}$ und $\begin{eqnarray*} n=1 \end{eqnarray*}$ , Induktionsschluss $\begin{eqnarray*} (<n) \to n \end{eqnarray*}$ dann erst für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ .

Oder umgekehrt (also $\begin{eqnarray*} m\leftrightarrow n \end{eqnarray*}$ ) - aber das ist ja klar, bei der Symmetrie der Gleichung.

01.05.2007, 23:12

mYthos

Auf diesen Beitrag antworten »

@Arthur
Ohh, vielen Dank, klar, siehe mein Edit..

mY+

02.05.2007, 10:14

Mareike.

Auf diesen Beitrag antworten »

Hallo!

Ich bin die schon angesprochene Schülerin und ich kann bestätigen, dass wir den Beweis nun erfolgreich durchgeführt haben smile

Es ging, indem wir statt dem n, das m festgehalten haben.
Die genaueren Beweisüberlegungen wird mYthos demnächst noch erläutern..

Ich wollte mich auch noch für die guten Hilfen hier im Forum bedanken! Freude

Mareike.

02.05.2007, 10:34

Auf diesen Beitrag antworten »

Zitat:

Original von Mareike.
Es ging, indem wir statt dem n, das m festgehalten haben.

Wie ich schon sagte: Das ist rum wie num. Augenzwinkern

02.05.2007, 16:27

mathepaps

Auf diesen Beitrag antworten »

Fibonacci
Hallo Mareike,
da wird dein Mathelehrer aber staunen......!!
Freude

08.05.2007, 13:32

mYthos

Auf diesen Beitrag antworten »

Nun wieder zu Hause, reiche ich noch zum allgemeinen Interesse (und das deines Mathelehrers Big Laugh

) die Behandlung der Additionsformel nach. Aus dieser

$\begin{eqnarray*} f_{n+m}= f_n \cdot f_{m-1} + f_{n+1} \cdot f_m \end{eqnarray*}$

folgt dann - wie schon erwähnt - unmittelbar (mit m = n + 1)

$\begin{eqnarray*} f_{2n+1}=f_n^2 + f_{n+1}^2 \end{eqnarray*}$ bzw.

$\begin{eqnarray*} f_{2n+3}=f_{n+1}^2 + f_{n+2}^2 \end{eqnarray*}$

_____________________________________________

In

$\begin{eqnarray*} f_{n+m}= f_n \cdot f_{m-1} + f_{n+1} \cdot f_m \end{eqnarray*}$

halten wir n fest und führen den Beweis über m -> m + 1 (@Arthur, freilich geht's auch andersrum ...).

I.A.:
m = 1

$\begin{eqnarray*} f_{n+1}= f_n \cdot f_{0} + f_{n+1} \cdot f_1 \end{eqnarray*}$ ... [ $\begin{eqnarray*} f_0 = 0, f_1 = 1 \end{eqnarray*}$ ]

$\begin{eqnarray*} f_{n+1} = f_{n+1} \end{eqnarray*}$ .. wahre Aussage

oder
m = 2

$\begin{eqnarray*} f_{n+2}= f_n \cdot f_{1} + f_{n+1} \cdot f_2 \end{eqnarray*}$ ... [ $\begin{eqnarray*} f_1 = 1, f_2 = 1 \end{eqnarray*}$ ]

$\begin{eqnarray*} f_{n+2} = f_n + f_{n+1} \end{eqnarray*}$ .. lt. Rekursionsformel

$\begin{eqnarray*} f_n + f_{n+1} = f_n \cdot 1 + f_{n+1} \cdot 1 \end{eqnarray*}$ .. w. Auss.

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

I.V. (Ind. Voraussetzung od. Ind. Annahme):
Formel ist richtig für m, daraus folgt, richtig für m + 1 .. m -> m + 1

$\begin{eqnarray*} f_{n+m+1}= f_n \cdot f_{m} + f_{n+1} \cdot f_{m+1} \end{eqnarray*}$

Setze die linke Seite $\begin{eqnarray*} f_{n+m+1} = f_{n+m} + f_{n+m-1} \end{eqnarray*}$ .. lt. Rekursionsformel

$\begin{eqnarray*} f_{n+m} + f_{n+m-1} = f_n \cdot f_{m} + f_{n+1} \cdot f_{m+1} \end{eqnarray*}$

Auf beide Summanden der linken Seite wenden wir nun die I.V. an:

$\begin{eqnarray*} f_n \cdot f_{m-1} + f_{n+1} \cdot f_{m} + f_{n-1} \cdot f_{m-1} + f_{n} \cdot f_{m} = f_n \cdot f_{m} + f_{n+1} \cdot f_{m+1} \end{eqnarray*}$

Reduzieren von $\begin{eqnarray*} f_{n} \cdot f_{m} \end{eqnarray*}$ , Ersetzen von $\begin{eqnarray*} f_{m+1} = f_m + f_{m-1} \end{eqnarray*}$ und Multiplizieren

$\begin{eqnarray*} \rightarrow f_n \cdot f_{m-1} + f_{n+1} \cdot f_{m} + f_{n-1} \cdot f_{m-1} = f_{n+1} \cdot f_{m-1} \end{eqnarray*}$

Reduzieren von $\begin{eqnarray*} f_{n+1} \cdot f_{m} \end{eqnarray*}$ , Ersetzen von $\begin{eqnarray*} f_{n+1} = f_n + f_{n-1} \end{eqnarray*}$ und Multiplizieren

$\begin{eqnarray*} \rightarrow f_n \cdot f_{m-1} + f_{n-1} \cdot f_{m-1} = f_{n} \cdot f_{m-1} + f_{n-1} \cdot f_{m-1} \end{eqnarray*}$

-> wahre Aussage, was zu zeigen war

mY+

08.05.2007, 15:32

Auf diesen Beitrag antworten »

Interessant ist auch, dass die eben nachgewiesene Aussage sogar für alle ganzzahligen $\begin{eqnarray*} m,n \end{eqnarray*}$ gilt, sofern man die Fibonacci-Folge auch für negative Indizes in konformer Weise definiert, d.h., über

$\begin{eqnarray*} f_n := f_{n+2}-f_{n+1} \end{eqnarray*}$ für $\begin{eqnarray*} n=-1,-2,\ldots \end{eqnarray*}$

Dann kann man leicht $\begin{eqnarray*} f_{-n} = (-1)^{n-1}f_n \end{eqnarray*}$ nachweisen, und die vorliegende Aussage liefert z.B. für $\begin{eqnarray*} m=-n+1 \end{eqnarray*}$ :

$\begin{eqnarray*} f_1 = f_n\cdot f_{-n} + f_{n+1}\cdot f_{-n+1} \end{eqnarray*}$

bzw. eingesetzt

$\begin{eqnarray*} (-1)^n = f_{n+1}\cdot f_{n-1}-f_n^2 \end{eqnarray*}$ ,

gültig für alle ganzzahligen $\begin{eqnarray*} n \end{eqnarray*}$ . Das kann man auch anders zeigen, sicher, aber es passt eben auch in dieses Schema, sofern man den Indexbereich auf ganz $\begin{eqnarray*} \mathbb{Z} \end{eqnarray*}$ ausdehnt. Wink

Neue Frage »

Antworten »

Beweis an der Fibonaccifolge

Verwandte Themen