Fibonacci

Einige Berechnungsmethoden (1. Teil)

Mittels der Zahlenfolge a1,a2,a2,... bilden wir die Summe: (a1-a2) + (a2-a3) + (a3-a4) + ... + (an-1-an). Diese Summe ist leicht zu vereinfachen, denn fast alle Glieder (ausser das erste und das letzte) verschwinden. Der Ausdruck ist also gleich a1 - an. Eine Summe wie diese, wo die Glieder gleichsam ineinanderschieben, wird eine (Zieh)harmonikasumme oder eine Teleskopsumme genannt.


Betrachte mal ein Beispiel wo die Teleskopeigenschaft gut verschleiert ist:
Berechne die Summe 1/(1x2) + 1/(2x3) + 1/(3x4) + ... + 1/((n-1)xn).
Nun is unsere Aufgabe diese Summe in eine Teleskopsumme umzubilden.
Bemerke dass 1/(1x2) = 1/1 - 1/2 und 1/(2x3) = 1/2 - 1/3 und im allgemeinen 1/((r-1)xr) = 1/(r-1) - 1/r.
Wir ersetzen nun Glied für Glied jedes Glied durch eine Differenz. Das ergibt:
(1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + ... + (1/(n-1) - 1/n).
Nun fallen die meisten Glieder gegen einander weg. Das Endresultat ist 1 - 1/n.

Betrachte jetzt die Summe: 1/(F₁F₃) + 1/(F₂F₄) + 1/(F₃F₅) + ... + 1/(F_n-1F_n+1).
Es ist leicht nachzuweisen dass für k>1 gilt: 1/(F_k-1F_k+1) = 1/(F_k-1F_k) - 1/(F_kF_k+1). Also
1/(F₁F₃) + 1/(F₂F₄) + 1/(F₃F₅) + ... + 1/(F_n-1F_n+1) =
(1/(F₁F₂) - 1/(F₂F₃)) + (1/(F₂F₃) - 1/(F₃F₄)) + ... + (1/(F_n-1F_n) - 1/(F_nF_n+1)) = 1 - 1/(F_nF_n+1)



Ein anderes Beispiel: Berechne 1 + 3 + 5 + 7 + ... + (2n+1). Auch jetzt ist es möglich eine Teleskopsumme zu finden, obwohl man das auf den ersten Blick nicht erwarten würde. Man muss also jedes Glied durch eine Differenz ersetzen. Nun ist 2k+1 = - k2 + (k+1)2, also 1 + 3 + 5 + 7 + ... + (2n+1) = (-02 + 12) + (-12 + 22) + (-22 + 32) + ... + (-n2 + (n+1)2) = (n+1)2. Das größte Problem dabei ist stets, um jedes Glied auf irgendeine Weise als eine Differenz zu schreiben. Auch in Aufgaben wobei Fibonaccizahlen auftreten können wir oft die Teleskopeigenschaft verwenden.



Berechne die Addition F₁ + F₂ + F₃ + ... + F_n
Nun ist es nicht schwer jedes Glied als eine Differenz zu schreiben, denn F_n-1 + F_n = F_n+1 oder F_n = -F_n-1 + F_n+1.
F₁ + F₂ + F₃ + ... + F_n = (-F₀ + F₂) + (-F₁ + F₃) + (-F₂ + F₄) + (-F₃ + F₅) + ... + (-F_n-1 + F_n+1)
Der Reihe nach sehen wir Paare mit geraden und Paare mit ungeraden Indexen. Wir betrachten nun einzeln die Glieder mit geraden Indexen und die Glieder mit ungeraden Indexen. Dann stellen wir fest dass nur noch 4 Glieder übrigbleiben, nämlich das erste, das dritte, das letzte und das drittletzte Glied. Also, der Ausdruck ist gleich -F₀-F₁+F_n+1+F_n und das ist gleich -1 + F_n+2.
Wir hatten anstatt des Ausdrucks F_n = -F_n-1 + F_n+1 auch die mehr auf der Hand liegende Differenz F_n = F_n+1 - F_n-1 wählen können. Das macht für die Auskuft nichts aus, aber damit wird es viel schwieriger die entgegengesetzten Glieder zu finden.

Noch ein Beispiel. Berechne F₁² + F₂² + F₃² + ... + F_n².
Wir nutzen abermals die Formel F_k = -F_k-1 + F_k+1
F_k² = F_k*(-F_k-1 + F_k+1) = -F_k-1F_k + F_kF_k+1, und so:
F₁² + F₂² + F₃² + ... + F_n² =
(-F₀F₁ + F₁F₂) + (-F₁F₂ + F₂F₃) + (-F₂F₃ + F₃F₄) + ... (-F_n-1F_n + F_nF_n+1) = F_nF_n+1.

Ein letztes Rechenexempel. Berechne F₁F₂ + F₂F₃ + F₃F₄ + ... + F_2nF_2n+1.
Bemerke dass das letzte Glied nicht F_nF_n+1 ist, sondern F_2nF_2n+1. Die Anzahl Glieder ist offenbar gerade. Das ist so gemacht, weil wir nun nicht jedes einzelne Glied durch eine Differenz ersetzen, sondern Gliederpaare. Es ist netter wenn ich dies dem Leser überlasse. Wie kann man F_k-1F_k + F_kF_k+1 als eine Differenz von Quadraten schreiben?

Wir haben Ausdrücke für Summen von Potenzen von Fibonaccizahlen gefunden, nämlich für
g_1,n = F₁ + F₂ + F₃ + ... + F_n und
g_2,n = F₁² + F₂² + F₃² + ... + F_n²
Es wird schwierig die Harmonika-Strategie für höheren Potenzen an zu wenden wie
g_3,n = F₁³ + F₂³ + F₃³ + ... + F_n³