3 Summen von Folgenwerten

Wir betrachten nun den Fall f_n+k + f_n-k für k : = 2^j und n $\geq$ k.

3.1 k=2

f_n+2 + f_n-2 = (f_n+1 + f_n) + f_n-2 = ((f_n + f_n-1) + f_n) + f_n-2 = 2f_n + (f_n-1 + f_n-2) = 3f_n

3.2 k=4

f_n+4 + f_n-4 = f_n+4 + f_n-4 +2f_n -2f_n = f_n+2+2 + f_n+2-2 + f_n-2+2 + f_n-2-2 -2f_n

hier haben wir eine »Nullsumme« ergänzt, um nun den Fall k=2 anzuwenden!

= 3f_n+2 +3f_n-2 -2f_n = 3(f_n+2 + f_n-2) - 2f_n

und erneute Anwendung ergibt

= 3(3f_n) - 2f_n = 7f_n

3.3 k = 2^j

Wir definieren nun die Koeffizienten c₂ : = 3 , c₄ : = 7. Doch wie sehen die Koeffizienten für höhere Zweierpotenzen aus? - Nun, diese lassen sich induktiv bestimmen:

f_n+2^j+1 + f_n-2^j+1 = f_n+2^j+1 + f_n-2^j+1 +2f_n -2f_n

= f_n+2^j+2^j + f_n + f_n + f_n-2^j-2^j -2f_n

= (f_n+2^j+2^j + f_n+2^j-2^j) + (f_n-2^j+2^j + f_n-2^j-2^j) - 2f_n

= c2j . fn+2j + c2j . fn-2j -2fn

(mit c_2^j sei bereits bekannter Koeffizient)

= c2j . (fn+2j + fn-2j) - 2fn

= c2j . (c2j . fn) - 2fn

= (c2j2 -2) . fn

(hier steht der nunmehr ermittelte Koeffizient)

= c_2^j+1f_n

Wir halten also fest:

• fn+2j + fn-2j = c2j . fn für j $\geq$ 1
• c2 : = 3 sowie c2j : = c2j-12 - 2 für j > 1

3.4 Umstellungen

Stellt man das vorige Ergebnis um, so erhalten wir f_n = c_2^jf_n-2^j - f_{n-2 ^. 2^j} = c_2^jf_n-2^j - f_n-2^j+1; hiermit lassen sich rekursiv bereits die Folgenwerte von Zweierpotenzen effizient ermitteln.

Für andere Werte als Zweierpotenzen mag es angebracht sein, den Term erneut aufzulösen, um das Auftreten negativer Indices zu vermeiden. Zur Vereinfachung der Schreibweise wählen wir für ein gegebenes n ein eindeutig bestimmtes k mit der Eigenschaft ${\frac{{n}}{{8}}}$ < k : = 2^j $\leq$ ${\frac{{n}}{{4}}}$. Dann gilt:

f_n = c_kf_n-k - f_n-2k = c_k ^. (c_kf_n-k-k - f_n-k-2k) - f_n-2k

= c_k ^. (c_kf_n-2k - f_n-3k) - f_n-2k

= (c_k² -1)f_n-2k - c_kf_n-3k

3.5 k=1

Bisher haben wir den Wert k = 1 bei den obigen Betrachtungen ausgeklammert. Er scheint auch zunächst nicht sonderlich hilfreich zu sein. Bei der Berechnung von f_n können wir ja vorzeitig abbrechen und mit der »normalen« Rekursion f_n : = f_n-1 + f_n-2 fortfahren, lange bevor der Fall k = 1 relevant werden würde.

3.5.1 k = 1 im allgemeinen

Trotzdem sei der Fall der Vollständigkeit halber erwähnt:

f_n+1 + f_n-1 = (f_n + f_n-1) + f_n-1 = f_n +2f_n-1

3.5.2 k = 1 im besonderen: die Lucasfolge

Eine im Augenblick noch nicht direkt anwendbare, aber interessante Eigenschaft tritt zutage, wenn wir die Fibonaccifolge betrachten: F_n+1 + F_n-1 = L_n. Sie haben richtig gelesen, dies ergibt die Lucasfolge!³ Und diese Behauptung gilt es zu beweisen. Das geschieht in zwei Schritten:

Zunächst betrachten wir, ob die Startwerte übereinstimmen:

L₀ = 2, F₀₊₁ + F_0-1 = F₁ + F_-1 = 1 + 1 = 2

L₁ = 1, F₁₊₁ + F_1-1 = F₂ + F₀ = 1 + 0 = 1

Die Startwerte stimmen also überein. Der Wert von F_-1 kann nämlich folgerichtig anhand der Rekursionsgleichung F_n = F_n-1 + F_n-2 für n = 1 ermittelt werden: F₁ = F₀ + F_-1, also F_-1 = F₁ - F₀ = 1 - 0 = 1.

Im zweiten Schritt sollte noch gezeigt werden, daß die Folge F_n+1 + F_n-1 auch tatsächlich der Rekursionsgleichung L_n = L_n-1 + L_n-2 genügt:

L_n = L_n-1 + L_n-2 = (F_n-1+1 + F_n-1-1) + (F_n-2+1 + F_n-2-1)

= F_n + F_n-2 + F_n-1 + F_n-3 = (F_n + F_n-1) + (F_n-2 + F_n-3) = F_n+1 + F_n-1

q.e.d.

3.5.3 wundersame Koeffizienten

Wenn wir die Koeffizienten aus 3.3 betrachten und ihnen die zugehörigen Lucasfolgenwerte gegenüberstellen, so kommen wir auf die Vermutung, daß diese für j $\geq$ 1 gleich sind.

c_2¹ = c₂ = 3 sowie L_2¹ = L₂ = L₁ + L₀ = 1 + 2 = 3

c_2² = c₄ = 7 sowie L_2² = L₄ = L₃ + L₂ = L₂ + L₁ + L₂ = 3 + 1 + 3 = 7

Unter Anwendung von der Gleichung aus 3.4 bestätigt sich diese Vermutung:

Mit c2j+1 : = c2j2 - 2 für j $\geq$ 1 einerseits, und L2j+1 = c2jL2j+1-2j - L2j+1-2 . 2j = c2jL2j - L0 = c2jL2j - 2 anderseits folgt mit der Induktionsannahme L2j = c2j auch L2j+1 = c2jL2j -2 = c2jc2j -2 = c2j2 -2 = c2j+1 für alle folgenden Zweierpotenzen.

Wir halten also fest:

L2j+1 = c2j+1 = L2j2 - 2 für j $\geq$ 1

3.6 k verallgemeinert

Lösen wir uns jetzt von den Zweierpotenzen, so daß k nun beliebige Werte annehmen kann. Betrachten wir zunächst zwei weitere Beispiele, wobei wir das Vorzeichen variieren.

3.6.1 k = 1

f_n+1 - f_n-1 = (f_n + f_n-1) - f_n-1 = f_n

3.6.2 k = 3

f_n+3 - f_n-3 = f_n+2 + f_n+1 - f_n-3 = 2f_n+1 + f_n - f_n-3

= 3f_n +2f_n-1 - f_n-3 = 3f_n + f_n-1 + f_n-2 + f_n-3 - f_n-3 = 4f_n

3.6.3 eine allgemeine Formel

Wenn man die Koeffizienten mit den Werten der Lucasfolge vergleicht, kommt man nach einigem hin- und her vielleicht auf die Idee: L_k ist für gerade k bei der Summe und für ungerade k bei der Differenz der zugehörige Koeffizient.

Mithin vermutet man: f_n+k + (- 1)^kf_n-k = L_k ^. f_n

Diese Vermutung gilt es nun zu beweisen. Dies geschieht per Induktion über k.⁴

k = 0: f_n+0 +1 ^. f_n-0 = 2f_n = L₀ ^. f_n (wahr)

k = 1: f_n+1 + (- 1) ^. f_n-1 = f_n + f_n-1 - f_n-1 = 1 ^. f_n = L₁ ^. f_n (wahr)

k + 1:

Induktionsannahme: Für k> 0 sei sowohl für k - 1 als auch für k die Behauptung erfüllt. Zu zeigen bleibt, daß sie dann auch für k + 1 erfüllt ist, und somit induktiv aufsteigend für alle k + i durch den beliebig oft wiederholbaren Übergang von k auf k + 1 (vollständiges Induktionsprinzip).

L_k+1 ^. f_n = (L_k + L_k-1) ^. f_n = L_k ^. f_n + L_k-1 ^. f_n

= (f_n+k + (- 1)^{k .} f_n-k) + (f_n+(k-1) + (- 1)^{k-1 .} f_n-(k-1))

(nach Induktionsannahme)

= f_n+k + f_n+(k-1) + (- 1)^kf_n-k + (- 1)^k-1f_n-(k-1)

= f_n+(k+1) + (- 1)^kf_n-k + (- 1)^k-1(f_n-k + f_n-(k+1))

= f_n+(k+1) + (- 1)^kf_n-k + (- 1)^k-1f_n-k + (- 1)^k-1f_n-(k+1)

= f_n+(k+1) + (- 1)^k-1f_n-(k+1)

= f_n+(k+1) + (- 1)^k+1f_n-(k+1)

q.e.d.

3.6.4 negative Indices erneut betrachtet

Für n = 0 erhalten wir mit obigem Satz

f_k + (- 1)^{k .} f_-k = L_k ^. f₀

$$\Longleftrightarrow$$ f_-k = (L_k ^. f₀ - f_k) ^. (- 1)^k

3.6.5 Spezialisierung für L_n+k

Die Anwendung des obigen Satzes auf f : = L ergibt L_n+k + (- 1)^{k .} L_n-k = L_n ^. L_k, somit ergibt sich L_n+k = L_nL_k - (- 1)^kL_n-k.

3.6.6 Spezialisierung für L_2n

Setzen wir nun noch k : = n, so erhalten wir L_n+n = L_n ^. L_n - (- 1)^kL_n-n = L_n² - (- 1)ⁿL₀, also L_2n = L_n² - (- 1)^{n .} 2. Dies ist eine Verallgemeinerung des in 3.5.3 ermittelten Resultats.

3.6.7 L_3n

Wir wenden zunächst 3.6.5 für L_2n+n und später 3.6.6 an:

L_3n = L_2n+n = L_2nL_n - (- 1)^{n .} L_2n-n = L_2nL_n - (- 1)ⁿL_n

= (L_2n - (- 1)ⁿ)L_n = (L_n² - (- 1)^{n .} 3) ^. L_n

3.6.8 F_n+k

Die nachfolgende Herleitung ist typisch für die Mathematik. Natürlich hätten wir die Formel auch vom Himmel fallen lassen und anschließend beweisen können. Aber durch einen gezielt gewählten Umweg stößt man häufig auf die gewünschte Abkürzung. So findet das Schiff den Weg in die Flasche:

Wir betrachten f : = F sowie die Fälle f_n+k und f_k+n und erhalten hieraus F_n+k = L_kF_n - (- 1)^kF_n-k sowie F_k+n = L_nF_k - (- 1)ⁿF_k-n.

Summation ergibt:

2 ^. F_n+k = F_n+k + F_k+n = L_kF_n + L_nF_k - (- 1)^kF_n-k - (- 1)ⁿF_k-n

Unter Berücksichtigung der Eigenschaft F_k-n = F_-(n-k) = (- 1)^(n-k)+1F_n-k erhalten wir

(- 1)^kF_n-k + (- 1)ⁿF_k-n = (- 1)^kF_n-k + (- 1)ⁿ(- 1)^n-k+1F_n-k = F_n-k ^. ((- 1)^k + (- 1)^2n-k+1)

= F_n-k ^. ((- 1)^k + (- 1)^1-k) = F_n-k ^. 0 = 0

Also

F_n+k = $${\frac{{F_{n}L_{k}+F_{k}L_{n}}}{{2}}}$$

3.6.8.1 Spezialfall n = k

Diesen Fall betrachten wir später noch einmal, trotzdem springt er uns hier schon ins Auge:

F_2n = F_n+n = $${\frac{{F_{n}L_{n}+F_{n}L_{n}}}{{2}}}$$ = F_nL_n

3.6.9 F_n-k

Mit 3.6.3 erhalten wir F_n-k = (- 1)^{k .} (L_kF_n - F_n+k). Also

F_n-k = (- 1)^{k .} (L_kF_n - $${\frac{{F_{n}L_{k}+F_{k}L_{n}}}{{2}}}$$) = $${\frac{{2L_{k}F_{n}-F_{n}L_{k}-F_{k}L_{n}}}{{2\cdot(-1)^{k}}}}$$ = $${\frac{{F_{n}L_{k}-F_{k}L_{n}}}{{2\cdot(-1)^{k}}}}$$

(Alternativ hätten wir auch F_n-k = F_n+(-k) = ${\frac{{F_{n}L_{-k}+F_{-k}L_{n}}}{{2}}}$ mit anschließender Anwendung von 2.3.1 sowie 2.3.2 ausrechnen können.)

3.7 Resümee

Manchmal fallen Formeln vom Himmel und sind dann zu beweisen. Dann steht man zunächst ohne jede Idee da und staunt (oder ärgert sich). Wenn man sich jedoch die Zeit nimmt, die fallenden Regentropfen zu betrachten, die schließlich als Schneeflocken auf die Erde fallen und den Boden mit einem weißen Mantel überdecken, dann bekommt man eine Ahnung davon, daß auch diese wunderbare Schönheit »nur« eine andere Form des Wassers ist...