Fibonacci-Aufgaben

14.06.2009, 17:46

gast²

Fibonacci-Aufgaben

Ich grüße euch!
Ich habe hier drei Aufgaben über Fibonacci-Zahlen vor mir liegen und finde gerade keinen Ansatz.
Zeigen Sie:

Aufgabe 1
$\begin{eqnarray*} F_{n}^{2} - F_{n+1}F_{n-1} = (-1)^n \end{eqnarray*}$

Aufgabe 2
$\begin{eqnarray*} \sum_{i=1}^n~F_{i} = F_{n+2} - 1 \end{eqnarray*}$

Aufgabe 3
$\begin{eqnarray*} F_{n-1}^{2} + F_{n}^{2} = F_{2n} \end{eqnarray*}$ sowie $\begin{eqnarray*} F_{n-1}F_{n} + F_{n}F_{n+1} = F_{2n + 1} \end{eqnarray*}$

Die Aufgaben 1 und 2 konnte ich mittels Induktion bereits lösen, bei der dritten Aufgabe weiß ich leider nicht, wie ich mit den Indizes umzugehen habe. Vermutlich muss ich mit der Additionsformel arbeiten, leider weiß ich nicht genau wie.
Nun hoffe ich, dass mir hier eventuell jemand einen kleinen Denkanstoß geben könnte, wäre super.
LG
gast²

14.06.2009, 18:00

Auf diesen Beitrag antworten »

Üblicherweise betrachtet man die Fibonacci-Folge mit dem Start $\begin{eqnarray*} F_0=0,F_1=1 \end{eqnarray*}$ .

Wenn ich mir in der Hinsicht dein $\begin{eqnarray*} F_{n-1}F_{n} + F_{n}F_{n+1} = F_{2n + 1} \end{eqnarray*}$ für n=2 anschaue, dann stimmt das nicht. Durch etwas Rätselraten komme ich dann darauf, dass bei dir der Index etwas verschoben ist, d.h., dass bei dir $\begin{eqnarray*} F_0=1,F_1=1 \end{eqnarray*}$ ist. Allerdings wäre dann das hier falsch:

Zitat:

Original von gast²
Aufgabe 2
$\begin{eqnarray*} \sum_{i=1}^n~F_{i} = F_{n+2} - 1 \end{eqnarray*}$

es müsste dann $\begin{eqnarray*} \sum_{i=0}^n~F_{i} = F_{n+2} - 1 \end{eqnarray*}$ lauten.

Also was denn nun?

14.06.2009, 18:05

gast²

Auf diesen Beitrag antworten »

Oha, das tut mir leid.
Es gilt bei Aufgabe 2 natürlich
$\begin{eqnarray*} \sum_{i=0}^n~F_{i} = F_{n+2} - 1 \end{eqnarray*}$

und tatsächlich soll gelten

$\begin{eqnarray*} F_{0} = F_{1} = 1 \end{eqnarray*}$

sicherlich keine unwichtige Angabe, daher nochmal Entschuldigung für das Vergessen.

14.06.2009, 18:09

Auf diesen Beitrag antworten »

Am besten weist du gleich

$\begin{eqnarray*} F_{m+n} = F_mF_n + F_{m-1}F_{n-1} \end{eqnarray*}$ für alle $\begin{eqnarray*} m\geq 1,n\geq 1 \end{eqnarray*}$

nach, dann fallen deine gesuchten Eigenschaften als Spezialfall ab.

Dieser Nachweis funktioniert ganz gut durch Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ bei festem $\begin{eqnarray*} m \end{eqnarray*}$ .

14.06.2009, 18:48

gast²

Auf diesen Beitrag antworten »

Nun, also das hab ich bisher:

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

Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ , $\begin{eqnarray*} m \end{eqnarray*}$ fest

IA: $\begin{eqnarray*} n = 1 \end{eqnarray*}$

$\begin{eqnarray*} F_{m + 1} = F_{m}F_{1} + F_{m-1}F_{0} = F_{m} + F_{m-1} \end{eqnarray*}$ , stimmt also

IS: $\begin{eqnarray*} {n \to n+1} \end{eqnarray*}$

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

$\begin{eqnarray*} = F_{m}(F_{n} + F_{n-1} + F_{n}(F_{m+1} - F_{m}) \end{eqnarray*}$

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

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

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

So, jetzt erkenn ich wenigstens den Spezialfall für $\begin{eqnarray*} n = m \end{eqnarray*}$ , allerdings komm ich bei meiner Induktion grad nicht weiter, ohne mich ständig im Kreis zu drehen. Ich kann ja jetzt auch schlecht sagen, dass die Behauptung jetzt schon gilt, wenn ich $\begin{eqnarray*} m = n \end{eqnarray*}$ setze, obwohl die Induktion nocht nicht zu Ende ist, oder kann ich doch?

14.06.2009, 18:54

Auf diesen Beitrag antworten »

Ich hatte auch eher an einen Induktionsschritt $\begin{eqnarray*} (n-1),n\to (n+1) \end{eqnarray*}$ gedacht

$\begin{eqnarray*} F_{m+n+1} = F_{m+n} + F_{m+n-1} \stackrel{IV}{=} F_{m}F_{n} + F_{m-1}F_{n-1} + F_{m}F_{n-1} + F_{m-1}F_{n-2} = \cdots \end{eqnarray*}$

Dazu solltest du den Induktionsanfang aber noch um n=2 erweitern, sonst läuft die Sache nicht korrekt an.

14.06.2009, 19:18

gast²

Auf diesen Beitrag antworten »

ich bin mir leider nicht ganz sicher, was du mit dem Induktionsschritt $\begin{eqnarray*} (n - 1), n \to (n + 1) \end{eqnarray*}$ meinst, sorry.

Zudem hilft mir $\begin{eqnarray*} n = 2 \end{eqnarray*}$ gerade auch nicht weiter, vielleicht hab ich aber auch einen Denkfehler. Ich komme da zu folgendem:

$\begin{eqnarray*} n = 2 \end{eqnarray*}$

$\begin{eqnarray*} F_{m + 2} = F_{m}F_{2} + F_{m - 1}F_{1} = 2F_{m} +F_{m - 1} \end{eqnarray*}$

und nun weiß ich nicht, was ich damit machen kann.

14.06.2009, 19:28

Auf diesen Beitrag antworten »

Zitat:

Original von gast²
ich bin mir leider nicht ganz sicher, was du mit dem Induktionsschritt $\begin{eqnarray*} (n - 1), n \to (n + 1) \end{eqnarray*}$ meinst, sorry.

Das soll nur soviel heißen, dass ich im Nachweis für $\begin{eqnarray*} n+1 \end{eqnarray*}$ die Satzaussage nicht nur für $\begin{eqnarray*} n \end{eqnarray*}$ , sondern auch für $\begin{eqnarray*} n-1 \end{eqnarray*}$ nutzen will.

Zitat:

Original von gast²
$\begin{eqnarray*} F_{m + 2} = F_{m}F_{2} + F_{m - 1}F_{1} = 2F_{m} +F_{m - 1} \end{eqnarray*}$

und nun weiß ich nicht, was ich damit machen kann.

Du sollst es einfach nachweisen, was wegen

$\begin{eqnarray*} F_{m + 2} = F_{m+1} + F_m = (F_m+F_{m-1})+ F_m = 2F_{m} +F_{m - 1} \end{eqnarray*}$

auch schnell erledigt ist.

14.06.2009, 20:01

gast²

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Du sollst es einfach nachweisen, was wegen

$\begin{eqnarray*} F_{m + 2} = F_{m+1} + F_m = (F_m+F_{m-1})+ F_m = 2F_{m} +F_{m - 1} \end{eqnarray*}$

auch schnell erledigt ist.

Oh man, da hatte ich mal wieder das sprichwörtliche Brett vorm Kopf...

Nun bin ich also zu folgendem Ergebnis gekommen:

$\begin{eqnarray*} F_{m+n+1} = F_{m + n} + F_{m+ (n- 1)} = F_{m }F_{n} + F_{m -1}F_{n-1} + F_{m}F_{n-1} + F_{m -1}F_{n- 2} \end{eqnarray*}$

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

$\begin{eqnarray*} = F_{m}F_{n} + F_{m-1}(F_{n+1} - F_{n}) + F_{m}(F_{n+1} - F_{n}) + F_{m-1}(F_{n} - (F_{n+1} - F_{n})) \end{eqnarray*}$

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

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

was zu beweisen war. Damit ist also die Aussage

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

bewiesen und für den Spezialfall $\begin{eqnarray*} m = n \end{eqnarray*}$ auch meine dritte Aufgabe gezeigt, sofern keine Fehler mehr vorhanden sind.

Dann herzlichsten Dank für deine Hilfe und deine Geduld, hat mir wirklich sehr weitergeholfen!

LG
gast²

14.06.2009, 20:05

Auf diesen Beitrag antworten »

Ja, so geht's - obwohl man die Umformungen schon deutlich geraffter vornehmen kann:

$\begin{eqnarray*} F_{m}F_{n} + F_{m -1}F_{n-1} + F_{m}F_{n-1} + F_{m -1}F_{n- 2} = F_{m}(F_{n}+F_{n-1}) + F_{m -1}(F_{n-1}+F_{n- 2}) = F_{m}F_{n+1} + F_{m -1}F_{n} \end{eqnarray*}$

14.06.2009, 20:21

gast²

Auf diesen Beitrag antworten »

Das spart allerdings etwas Schreibarbeit, ist auch übersichtlicher Big Laugh

Also nochmals vielen Dank und einen angenehmen Sonntag-Abend wünsche ich!

Neue Frage »

Antworten »

Fibonacci-Aufgaben

Verwandte Themen