9 Weitere Formeln

9.1 F_2n = $\sum_{{i=0}}^{{n}}$$\binom {n}{i}$F_i

Wir verwenden die Eigenschaft aus Abschnitt 8, dann erhalten wir einerseits

$$\lambda^{{2n}}_{}$$ = F_2n$$\lambda$$ + F_2n-1

und andererseits unter Verwendung des Binomischen Satzes⁹

$$\lambda^{{2n}}_{}$$ = ($$\lambda^{{2}}_{}$$)ⁿ = ($$\lambda$$ +1)ⁿ = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$$$\lambda^{{i}}_{}$$ = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$(F_i$$\lambda$$ + F_i-1) = $$\left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right.$$$$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i$$\left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right)$$ ^. $$\lambda$$ + $$\left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right.$$$$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i-1$$\left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right)$$

Da aber für $\lambda^{{2n}}_{}$ keine andere Zerlegung als F_2n$\lambda$ + F_2n-1 existieren kann, muß folglich gelten:

F_2n = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i

und außerdem auch

F_2n-1 = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i-1

Dies ist übrigens auch leicht einzusehen, wenn man alternativ $\mu^{{2n}}_{}$ = F_2n$\mu$ + F_2n-1 sowie ($\mu^{{2}}_{}$)ⁿ = ($\mu$ +1)ⁿ = $\left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right.$$\sum_{{i=0}}^{{n}}$$\binom {n}{i}$F_i$\left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right)$ ^. $\mu$ + $\left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right.$$\sum_{{i=0}}^{{n}}$$\binom {n}{i}$F_i-1$\left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right)$ ausrechnet und die Terme in die Binetsche Formel einsetzt.

Abschließend für die Betrachtung des Terms $\lambda^{{2n}}_{}$ sei der Vollständigkeit halber noch auf eine dritte Umformungsvariante hingewiesen:

$$\lambda^{{2n}}_{}$$ = ($$\lambda^{{n}}_{}$$)² = (F_n$$\lambda$$ + F_n-1)² = F_n²$$\underbrace{{\lambda^{2}}}_{{\lambda+1}}^{}\,$$ +2F_n$$\lambda$$F_n-1 + F_2-1² = (F_n² +2F_nF_n-1)$$\lambda$$ + F_n² + F_n-1²

Daraus ergibt sich F_2n = F_n² +2F_nF_n-1 sowie F_2n-1 = F_n² + F_n-1². Addiert man zur ersteren Gleichung auf beiden Seiten F_n-1², so erhält man F_2n + F_n-1² = F_n² +2F_nF_n-1 + F_n-1² = (F_n + F_n-1)² = F_n+1², und dies ist äquivalent zu F_2n = F_n+1² - F_n-1² = ($\underbrace{{F_{n+1}+F_{n-1}}}_{{L_{n}}}^{}\,$) ^. ($\underbrace{{F_{n+1}-F_{n-1}}}_{{F_{n}}}^{}\,$), doch diese Formel kennen wir mit anderer Herleitung bereits aus Abschnitt 4.3.

9.2 F_{k ^. n} = $\sum_{{i=0}}^{{n}}$$\binom {n}{i}$F_i ^. F_k^{i .} F_k-1^n-i

Auch auf die Gefahr hin, nun vollkommen zu langweilen, wenden wir das obige Prinzip aus 9.1 erneut an, diesmal um eine Formel für F_{k ^. n} zu bestimmen:

$$\lambda^{{k\cdot n}}_{}$$ = ($$\lambda^{{k}}_{}$$)ⁿ = (F_k ^. $$\lambda$$ + F_k-1)ⁿ = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_k^{i .} $$\lambda^{{i}}_{}$$ ^. F_k-1^n-i = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_k^{i .} (F_i ^. $$\lambda$$ + F_i-1) ^. F_k-1^n-i

= $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_k^{i .} F_i ^. F_k-1^{n-i .} $$\lambda$$ + F_k^{i .} F_i-1 ^. F_k-1^n-i = $$\left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right.$$$$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i ^. F_k^{i .} F_k-1^n-i$$\left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right)$$ ^. $$\lambda$$ + $$\left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right.$$$$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i-1 ^. F_k^{i .} F_k-1^n-i$$\left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right)$$

Daraus folgt dann analog zu oben:

F_{k ^. n} = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i ^. F_k^{i .} F_k-1^n-i

sowie

F_{k ^. n-1} = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i-1 ^. F_k^{i .} F_k-1^n-i

Die beiden Formeln sind übrigens auch für k = 1 korrekt, wenn wir 0⁰ : = 1 verlangen, da in beiden Formeln der Teilfaktor F_k-1^n-i = F₀^n-i = 0^n-i dann alle Summanden bis auf den Term $\binom{n}{n}$F_n ^. F₁^{n .} F₀^n-n = F_n (bzw. für F_{k ^. n-1} bis auf den Term $\binom{n}{n}$F_n-1 ^. F₁^{n .} F₀^n-n = F_n-1) auf null setzt. (n sollte aber in allen Fällen eine positive natürliche Zahl sein.)

Als möglicherweise noch recht interessantes Beispiel der Anwendung obiger Formel können wir F_3n betrachten. Es ergibt sich zum einen

F_3n = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i ^. F₃^{i .} F₂^n-i = $$\sum_{{i=0}}^{{n}}$$$$\binom{n}{i}$$F_i ^. 2ⁱ

und da wir wegen der Kommutativität der Multiplikation auch noch k und n vertauschen dürfen, auch:

F_3n = F_{n ^. 3} = $$\sum_{{i=0}}^{{3}}$$$$\binom{3}{i}$$F_i ^. F_n^{i .} F_n-1^3-i = 0 + 3F₁ ^. F_n^{1 .} F_n-1² +3 ^. F₂ ^. F_n^{2 .} F_n-1¹ +1 ^. F₃ ^. F_n^{3 .} F_n-1⁰

= 3F_nF_n-1² +3F_n²F_n-1 +2F_n³ = F_n ^. (3F_n-1² +3F_nF_n-1 +2F_n²)

9.3 F_n-$\Delta$ ^. F_n+$\Delta$

F_n² - (- 1)^{n+$\Delta$ .} F_$\Delta$² = F_n-$\Delta$ ^. F_n+$\Delta$ = $${\frac{{F_{n}^{2}L_{\Delta}^{2}-F_{\Delta}^{2}L_{n}^{2}}}{{4\cdot(-1)^{\Delta}}}}$$

9.3.0.1 Beweis:

Wir verwenden die geschlossene Form. Somit ergibt sich einerseits

F_n² - (- 1)^{n+$\Delta$ .} F_$\Delta$² = ($${\frac{{\lambda^{n}-\mu^{n}}}{{\lambda-\mu}}}$$)² - (- 1)^{n+$\Delta$ .} ($${\frac{{\lambda^{\Delta}-\mu^{\Delta}}}{{\lambda-\mu}}}$$)²

= $${\frac{{(\lambda^{2n}-2(\lambda\mu)^{n}+\mu^{2n})-(-1)^{n+\Delta}... ...\lambda^{2\Delta}-2(\lambda\mu)^{\Delta}+\mu^{2\Delta})}}{{(\lambda-\mu)^{2}}}}$$ = *

( Hinweis: $\lambda$ ^. $\mu$ = ${\frac{{1+\sqrt{5}}}{{2}}}$ ^. ${\frac{{1-\sqrt{5}}}{{2}}}$ = ${\frac{{1^{2}-5}}{{2^{2}}}}$ = ${\frac{{-4}}{{4}}}$ = - 1 )

* = $${\frac{{(\lambda^{2n}-2\cdot(-1)^{n}+\mu^{2n})-(-1)^{n+\Delta}(\lambda^{2\Delta}-2\cdot(-1)^{\Delta}+\mu^{2\Delta})}}{{(\lambda-\mu)^{2}}}}$$

= $${\frac{{\lambda^{2n}+\mu^{2n}-2\cdot(-1)^{n}+2\cdot(-1)^{n+\Delta... ...\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$$

= $${\frac{{\lambda^{2n}+\mu^{2n}+2\cdot0-(-1)^{n+2\Delta}((\frac{\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$$ = $${\frac{{\lambda^{2n}+\mu^{2n}-(-1)^{n}((\frac{\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$$ = : h

und andererseits

F_n-$\Delta$ ^. F_n+$\Delta$ = $${\frac{{\lambda^{n-\Delta}-\mu^{n-\Delta}}}{{\lambda-\mu}}}$$ ^. $${\frac{{\lambda^{n+\Delta}-\mu^{n+\Delta}}}{{\lambda-\mu}}}$$ = $${\frac{{\lambda^{2n}-\lambda^{n-\Delta}\mu^{n+\Delta}-\lambda^{n+\Delta}\mu^{n-\Delta}+\mu^{2n}}}{{(\lambda-\mu)^{2}}}}$$

= $${\frac{{\lambda^{2n}+\mu^{2n}-(\lambda\mu)^{n}((\frac{\mu}{\lambda})^{\Delta}+(\frac{\lambda}{\mu})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$$ = $${\frac{{\lambda^{2n}+\mu^{2n}-(-1)^{n}((\frac{\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$$ = h

Da beide Terme gleich sind, ist der erste Teil der Formel korrekt. Für den letzten Teil ergibt sich mit 3.6.8 und 3.6.9:

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

$\square$

9.4 F_n-$\Delta$ ^. F_n-1+$\Delta$

Bevor wir die eigentliche Formel vorstellen und mit dem Induktionsbeweis beginnen, folgt zunächst ein kleiner Hilfssatz.

9.4.1 Lemma

F_n-1-$\Delta$F_n+$\Delta$ + F_n-$\Delta$F_n-1+$\Delta$ = 2F_nF_n-1 + (- 1)^n+$\Delta$F_$\Delta$²

Beweis

(i) aus ($\lambda^{{n}}_{}$)² = (F_n² +2F_nF_n-1)$\lambda$ + F_n² + F_n-1² folgt F_2n = F_n² +2F_nF_n-1

(ii) aus $\lambda^{{2n}}_{}$ = $\lambda^{{n-\Delta}}_{}$ ^. $\lambda^{{n+\Delta}}_{}$ folgt F_2n = F_n-$\Delta$F_n+$\Delta$ + F_n-$\Delta$F_n-1+$\Delta$ + F_n-1-$\Delta$F_n+$\Delta$

Aus (i) und (ii) in Verbindung mit Formel 9.3 folgt

F_n² +2F_nF_n-1 = F_n² - (- 1)^n+$\Delta$F_$\Delta$² + F_n-$\Delta$F_n-1+$\Delta$ + F_n-1-$\Delta$F_n+$\Delta$

und daraus folgt die obige Gleichung.

9.4.2 Formel und zugehöriger Induktionsbeweis

Nach dieser Vorarbeit kommen wir nun zu unserer Formel

F_nF_n-1 = F_n-$\Delta$F_n-1+$\Delta$ + (- 1)^n+$\Delta$F_$\Delta$F_$\Delta$-1

die wir per Induktion über $\Delta$ beweisen wollen.

Der Induktionsanker $\Delta$ = 0 ergibt F_nF_n-1 = F_nF_n-1 + (- 1)^{n .} 0 und ist daher erfüllt. Sei nun die Behauptung für $\Delta$ wahr. Zu zeigen bleibt die Korrektheit der Behauptung für $\Delta$ + 1:

$$\Delta \Delta \Delta \Delta \Delta$$

$$\Delta \Delta \Delta \underbrace{{F_{\Delta+1}}}_{{F_{\Delta}+F_{\Delta-1}}}^{}\, \Delta$$

$$\Delta \Delta \underbrace{{(-1)^{n+\Delta}F_{\Delta-1}F_{\Delta}}}_{{F_{n}F_{n-1}-F_{n-\Delta}F_{n-1+\Delta}\textnormal{ nach Induktionsannahme}}}^{}\, \Delta \Delta$$

$$\underbrace{{F_{n-1-\Delta}F_{n+\Delta}+F_{n-\Delta}F_{n-1+\Delta}}}_{{\textnormal{Lemma!}}}^{}\, \Delta \Delta$$

$$\Delta \Delta \Delta \Delta$$ = F_nF_n-1

q.e.d.

9.5 Nochmalige Betrachtung von Periodizität und Teilbarkeit

Erinnern wir uns einerseits noch einmal an die Binetsche Formel F_n = ${\frac{{\lambda^{n}-\mu^{n}}}{{\lambda-\mu}}}$ aus Abschnitt 6. Dabei wurde $\lambda$ : = ${\frac{{1+\sqrt{5}}}{{2}}}$ und $\mu$ : = ${\frac{{1-\sqrt{5}}}{{2}}}$ gesetzt. Erinnern wir uns andererseits daran, daß es für Periodizitätsbetrachtungen häufig sinnvoll ist, in Restklassen zu rechnen. - Nun können wir die berechtigte Frage stellen: Ist es möglich, die geschlossene Form innerhalb einer Restklassenbetrachtung zu verwenden?

Diese Frage führt uns unmittelbar zu dem Problem, ob der Ausdruck $\sqrt{{5}}$ in den Restklassen, die wir betrachten wollen, auf sinnvolle Weise definiert werden kann.

Für die nachfolgende Betrachtung benötigen wir Wissen aus der Zahlentheorie, das z.B. bei [FrIs92] nachgeschlagen werden kann. Zum einen benötigen wir den sogenannten kleinen Fermatschen Satz, der für Primzahlen p und teilerfremde Basen a die Folgerung a^p-1 $\equiv$ 1 ( mod p) aufstellt. Zum anderen benötigen wir einige zentrale Eigenschaften über quadratische Reste.

9.5.1 Die Fälle (${\frac{{5}}{{p}}}$) = 1

Betrachten wir Primzahlen p > 5 und die Primkörper $\mathbb {F}$_p, d.h. die Körper, die bei den Restklassenbetrachtungen modulo Primzahlen p entstehen. Die unter Abschnitt 6 hergeleitete geschlossene Form bleibt in solchen Primkörpern gültig, wenn 5 ein quadratischer Rest modulo p ist, mit Hilfe des Legendresymbols ausgedrückt also (${\frac{{5}}{{p}}}$) = 1 gilt; nur dann ist Kongruenz x² $\equiv$ 5 ( mod p) in $\mathbb {\mathbb{F}}$_p erfüllbar und wir können für unsere Betrachtung z.B. $\sqrt{{5}}$ als die »größere« und - $\sqrt{{5}}$ als die »kleinere« Lösung dieser Kongruenz definieren.

Für Primzahlen p mit (${\frac{{5}}{{p}}}$) = 1 gilt somit aufgrund des kleinen Fermatschen Satzes

F_p-1 = $${\frac{{\lambda^{p-1}-\mu^{p-1}}}{{\lambda-\mu}}}$$ $$\equiv$$ $${\frac{{1-1}}{{\sqrt{5}}}}$$ $$\equiv$$ 0 ( mod p)

sowie

F_p = $${\frac{{\lambda^{p}-\mu^{p}}}{{\lambda-\mu}}}$$ $$\equiv$$ $${\frac{{\lambda-\mu}}{{\lambda-\mu}}}$$ $$\equiv$$ $${\frac{{\sqrt{5}}}{{\sqrt{5}}}}$$ $$\equiv$$ 1 ( mod p)

Damit gilt (F_p-1, F_p) $\equiv$ (0, 1) $\equiv$ (F₀, F₁), mithin gilt die Periodizität F_{k ^. (p-1)+$\Delta$} $\equiv$ F_$\Delta$ ( mod p) für Primzahlen der obengenannten Form.

Insbesondere sind für diese Primzahlen die Fibonacciwerte F_p-1 sowie die Terme F_p-2 - 1, F_p - 1 und F_p+1 - 1 durch p teilbar.

Wegen des quadratischen Reziprozitätsgesetzes gilt für ungerade p

($${\frac{{p}}{{5}}}$$) = ($${\frac{{5}}{{p}}}$$) ^. (- 1)^{${\frac{{5-1}}{{2}}}$ . ${\frac{{p-1}}{{2}}}$} = ($${\frac{{5}}{{p}}}$$) ^. 1 = ($${\frac{{5}}{{p}}}$$)

Anstatt alle Fälle für (${\frac{{5}}{{p}}}$) = 1 zu untersuchen, können wir uns also auf die Fälle (${\frac{{p}}{{5}}}$) = 1 beschränken. Eine Restklassenbetrachtung auf $\mathbb {F}$₅ (vgl. Tabelle 9) zeigt uns, daß nur Zahlen der Form 5n, 5n + 1 und 5n + 4 (bzw. 5n - 1) quadratische Reste modulo 5 sind. Da Primzahlen größer als 5 weder durch 5 noch durch 2 teilbar sind, können wir folgern: Primzahlen mit der Eigenschaft (${\frac{{5}}{{p}}}$) = 1 und p > 5 haben die Form p = 10 ^. n±1. (Diese Form enthält diejenigen quadratischen Reste modulo 10, die zu 10 teilerfremd sind.)

Table 9: Quadratische Reste modulo 5 bzw. 10

Table 9: Quadratische Reste modulo 5 bzw. 10

x	0	1	2	3	4
x2 mod 5	0	1	4	4	1

Table 9: Quadratische Reste modulo 5 bzw. 10

x	0	1	2	3	4	5	6	7	8	9
x2 mod 10	0	1	4	9	6	5	6	9	4	1

9.5.1.1 Zusammenfassung dieser Ergebnisse

Für Primzahlen der Form p = 10 ^. n±1 sind die Terme F_p-2 - 1, F_p-1, F_p - 1 und F_p+1 - 1 durch p ohne Rest teilbar.

9.5.1.1.1 Beispiel: F₉₀₉ -1 $\equiv$ F₉₁₀ $\equiv$ F₉₁₁ -1 $\equiv$ F₉₁₂ -1 $\equiv$ 0 ( mod 911)

9.5.2 Die Fälle (${\frac{{5}}{{p}}}$) = - 1

Die nicht-quadratischen Reste modulo 10, die zu 10 teilerfremd sind, haben die Form 10 ^. n±3. Für Primzahlen dieser Form gilt: Die Periode P_p (für F_{k ^. Pp+$\Delta$} $\equiv$ F_$\Delta$ ( mod p)) ist ein Vielfaches von p + 1 und es gilt F_p+1 $\equiv$ 0 ( mod p).

9.5.2.1 Beweis:

Ich habe leider keinen Beweis gefunden, der ohne fortgeschrittene Konzepte aus der Zahlentheorie auskommt. Für die erforderlichen zahlentheoretischen Grundlagen sei daher auf [HaRi94], Appendix 4 (The Arithmetic of Quadratic Fields) verwiesen, ohne die der nachfolgende Beweis unverständlich sein dürfte.

Wir betrachten den Körper $\mathbb {Q}$($\sqrt{{5}}$) und setzen a : = 2 ^. $\lambda$ = 1 + $\sqrt{{5}}$, dann gilt $\bar{{a}}$ = 1 - $\sqrt{{5}}$ = 2 ^. $\mu$. Wegen a² -2a - 4 = (1² +2 ^. $\sqrt{{5}}$ +5) - (2 + 2 ^. $\sqrt{{5}}$) - 4 = 6 - 2 - 4 = 0 sind sowohl a als auch $\bar{{a}}$ Elemente dieses Körpers.

Mit der Erweiterung des kleinen Fermatschen Satzes auf solche Körper gilt a^p $\equiv$ $\bar{{a}}$ ( mod p) für (${\frac{{5}}{{p}}}$) = - 1. Somit folgt

F_p+1 = $${\frac{{\lambda^{p+1}-\mu^{p+1}}}{{\lambda-\mu}}}$$ = $${\frac{{(a^{p+1}-\bar{a}^{p+1})\cdot2^{-p-1}}}{{(a-\bar{a})\cdot2^{-1}}}}$$ = $${\frac{{a\cdot a^{p}-\bar{a}\cdot\bar{a}^{p}}}{{a-\bar{a}}}}$$ ^. 2^-p

$$\equiv$$ $${\frac{{a\bar{a}-\bar{a}a}}{{a-\bar{a}}}}$$ ^. 2^-1 = $${\frac{{a\bar{a}-a\bar{a}}}{{(a-\bar{a})\cdot2}}}$$ = $${\frac{{0}}{{(a-\bar{a})\cdot2}}}$$ = 0 ( mod p)

$\square$