Fibonaccizahlen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:43 Mi 16.11.2011 | | Autor: | clemenum |
| Aufgabe | Man zeige die Gültigkeit folgender Fibonacci-Idendität:
[mm] $\sum_{k=0}^{n} F_kF_{n-k} [/mm] = [mm] \sum_ {k=0}^n [/mm] (k+1) [mm] \cdot F_{k+1} \cdot (-2)^{n-k} [/mm] $ |
Es tut mir leid, aber bei diesem Beispiel habe ich nichtmal eine Idee!
Ich bitte euch um einen guten Hinweis. Es wurde leider lediglich eingeführt, was Fibonacci-Zahlen sind (es wurde die explizite und die rekursive Bildungsvorschrift angegeben bzw. hergeleitet, sonst nichts), daher meine Ahnungslosigkeit.
Hilft hier mir eine bekannte Methode weiter oder muss ich hier eine (neue?) entwicklen und wenn ja, könntet ihr mir einen weiterführenden Hinweis geben!
Ich wäre euch jedenfalls sehr dankbar, liebe Mathematikergemeinde! 
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:43 Do 17.11.2011 | | Autor: | Fulla |
Hallo clemenum,
> Man zeige die Gültigkeit folgender Fibonacci-Idendität:
> [mm]\sum_{k=0}^{n} F_kF_{n-k} = \sum_ {k=0}^n (k+1) \cdot F_{k+1} \cdot (-2)^{n-k}[/mm]
das schreit zwar nach vollständiger Induktion, aber die Gleichung stimmt so nicht.... (ich gehe mal davon aus, dass [mm]F_0=1[/mm], [mm]F_1=1[/mm], [mm]F_n=F_{n-1}+F_{n-2}[/mm])
Z.B. für [mm]n=1[/mm] steht da
[mm]F_0F_1+F_1F_0=F_1(-2)+2F_2\quad\Leftrightarrow[/mm]
[mm]1+1=-2+2\quad\Leftrightarrow[/mm]
[mm]2=0[/mm]
Vielleicht schreibst du mal, wie die [mm]F_i[/mm] definiert sind...
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:58 Do 17.11.2011 | | Autor: | clemenum |
Natürlich sind mit den [mm] $F_i$ [/mm] - wie ja bereits angedeutet - die Fibonacci-Zahlen gemeint, also die Zahlen mit [mm] $F_0 [/mm] = 1, [mm] F_1 [/mm] = 1$ und [mm] $F_{n+1} [/mm] = [mm] F_{n-1} [/mm] + [mm] F_n [/mm] $ .
Findet mit dieser Information nun einer von euch einen wertvollen Hinweis zu dieser Aufgabe?
P.S.: Durch Ausprobieren kommt (mir) sehrwohl etwas richtiges heraus^^ Es ist nur eine ziemlich komplizierte Summe, wo man schon beim Einsetzen leicht Fehler macht...
|
|
|
| |
|
Hallo clemenum,
ich denke wie Fulla, dass man dies am besten mit Induktion angeht.
Schaun wir mal:
> Man zeige die Gültigkeit folgender Fibonacci-Idendität:
> [mm]\sum_{k=0}^{n} F_kF_{n-k} = \sum_ {k=0}^n (k+1) \cdot F_{k+1} \cdot (-2)^{n-k}[/mm]
>
> Es tut mir leid, aber bei diesem Beispiel habe ich nichtmal
> eine Idee!
>
> Ich bitte euch um einen guten Hinweis. Es wurde leider
> lediglich eingeführt, was Fibonacci-Zahlen sind (es wurde
> die explizite und die rekursive Bildungsvorschrift
> angegeben bzw. hergeleitet, sonst nichts), daher meine
> Ahnungslosigkeit.
>
> Hilft hier mir eine bekannte Methode weiter oder muss ich
> hier eine (neue?) entwicklen und wenn ja, könntet ihr mir
> einen weiterführenden Hinweis geben!
Für n=0: [mm] F_0F_0=1*F_1*(-2)^0\quad\gdw\quad [/mm] 1=1 ![[ok]](/images/smileys/ok.gif "[ok]")
Sicherheitshalber auch für n=1: [mm] F_0F_1+F_1F_0=1F_1*(-2)+2*F_2*(-2)^0\quad\gdw\quad 1+1=-2+2*\blue{2} [/mm]
So, nun Induktionsvoraussetzung: Formel stimmt für ein n.
Wie leitet man nun die Formel für n+1 aus der für n her?
Ich fange mal mit der rechten Seite an:
[mm] \summe_{k=0}^{n+1}(k+1)F_{k+1}*(-2)^{n+1-k}=(n+2)F_{n+2}-2\summe_{k=0}^{n}(k+1)F_{k+1}*(-2)^{n-k}
[/mm]
Ok so? Hier steht jetzt erst das "höchste" Summationsglied, und alle andern sind zusammengefasst, werden allerdings in der Summe bis (n+1) im Vergleich zu der bis n mit (-2) multipliziert; die habe ich vor die Summe gezogen.
Die linke Seite wird etwas schwieriger.
[mm] \summe_{k=0}^{n+1}F_kF_{n+1-k}=F_{n+1}F_0+F_nF_1+\summe_{k=0}^{n-1}F_k(F_{n-k}+F_{n-k-1})=F_{n+2}+\left(\summe_{k=0}^{n}F_kF_{n-k}\right)-F_nF_0+\left(\summe_{k=0}^{n-1}F_kF_{n-1-k}\right)=
[/mm]
[mm] =F_{n+1}+\left(\summe_{k=0}^{n}F_kF_{n-k}\right)+\left(\summe_{k=0}^{n-1}F_kF_{n-1-k}\right)=\cdots
[/mm]
So. Die beiden Summen, die jetzt da stehen, sollten Dir bekannt vorkommen. So ist man jetzt auf dem besten Weg einer Rekursion, bzw. einer zweistufigen Induktion. Man muss also voraussetzen, dass die Formel für n-1 und n gilt, und dann zeigen, dass sie auch für n+1 gilt. Glücklicherweise haben wir für n=0 und n=1 ja schon überprüft, dass sie gilt, das ist also kein Hindernis.
Das nächste Stück Weiterarbeit überlasse ich Dir. Sehr weit ist es jetzt nicht mehr.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:34 Do 17.11.2011 | | Autor: | Fulla |
Hallo reverent und clemenum,
sorry für die Verwirrung, ich hab mich beim Einsetzen vertan.
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:42 Do 17.11.2011 | | Autor: | reverend |
Hallo Fulla,
da stehst Du doch drüber. Wem das (angeblich) nicht passiert, der sollte besser keine Mathematik treiben. Kleinkram, und vor allem: leicht korrigierbar.
Ich erspare mir gerade mal, Beispiele meiner eigenen Fehler zu suchen. Innerhalb der letzten Woche dürften es allein in diesem Forum mindestens zehn gewesen sein. Wenige davon habe ich selbst bemerkt. Das ist doch das gute an der Öffentlichkeit des Forums - durch die gegenseitige Überprüfung können wir Richtigkeit und damit auch Qualität sichern.
Herzliche Grüße
reverend
|
|
|
| |
|
Hallo! Ich hatte die letzten paar Tage für diese aufgabe keine Zeit, daher reagiere ich erst jetzt.
Ich habe so weitergemacht:
$... = [mm] F_{n+1} [/mm] + [mm] \sum_{k=0}^{n-1}(k+1)F_{k+1}(-2)^{n-1-k} [/mm] + [mm] \sum_{k=0}^{n}(k+1)F_{k+1}(-2)^{n-k} [/mm] = [mm] 2\cdot\sum_{k=0}^{n-1}(k+1)F_{k+1}(-2)^{n-1-k} +(n+2)F_{n+1} [/mm] $
Das sieht aber leider nur annähernd nach Induktionsbehauptung aus! :-(
Ich habe öfters nachgerechnet, ich scheine keinen Fehler gemacht zu haben? Habe ich etwa einen logischen Fehler gemacht?
Jedenfalls, herzlichen Dank für die bisherige Hilfe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Fr 25.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
