Jeg vil da prøve meg på et bevis for at den første stemmer. Strategien er som følger:
- Vi finner en lukket formel for Fibonaccisekvensen
- Vi bruker denne til å bevise den ønskede egenskapen.
Det kan kanskje virke som en langtekkelig prosess, og jeg er sikker på at det finnes andre, kortere løsninger - men kanskje finnes det en del interessante konsepter i denne løsningen som med hell kan brukes i andre sammenhenger?
Det første steget løser seg ved hjelp av genererende funksjoner. (Takk,
Herbert Wilf! Generatingfunctionology må være en av de mest fantastiske mattebøkene jeg har sett noensinne.)
La oss bli enige om at [tex]f_i[/tex] er Fibonaccitallene slik at [tex]f_1 = f_2 = 1[/tex], og den vanlige rekursjonen stemmer. La [tex]F(x)[/tex] være den eksponentielle genererende funksjonen til Fibonaccisekvensen. Dette vil si at sekvensen [tex] \left{ f_i \right}_{i \geq 1}[/tex] er enkodet i
[tex]F(x) = \sum _{n = 1} ^\infty \frac{f_n}{n!}x^n[/tex]
Det følger direkte at [tex]\left{ f_{i+1} \right}_{i \geq 1}[/tex] er enkodet i [tex]F^\prime (x)[/tex] og [tex]\left{ f_{i+2} \right}_{i \geq 1}[/tex] i [tex]f^{\prime \prime} (x)[/tex]
Fra den rekursive definisjonen av Fibonaccitallene
[tex]f_{n+2} = f{n+1} + f_n[/tex]
Får vi da en differensiallikning for den genererende funksjonen:
[tex]\frac{\rm{d}^2 F(x)}{\rm{d}x^2} = \frac{\rm{d}F(x)}{\rm{d}x} + F(x)[/tex]
Løsning av differensiallikningen gir
[tex]c_1 e^{\phi x} + c_2 e^{\varphi x}[/tex] for noen konstanter [tex]c_1, \ c_2[/tex], og der
[tex]\phi = \frac{1}{2}(1 + \sqrt 5) \\ \varphi = \frac{1}{2}(1-\sqrt 5)[/tex] (Det gyldne snitt!)
Ved bruk av at [tex]F(0) = 0, \ F ^\prime (0) = 1[/tex], finner vi at [tex]c_1 = \frac{1}{ \sqrt 5}, \ c_2 = - \frac{1}{\sqrt 5}[/tex]
Dette gir at [tex]F(x) = \frac{1}{\sqrt 5} \left( e^{\phi x} - e^{\varphi x} \right)[/tex]. Her kan vi lese rett ut fra potensrekken at - og nå gjør vi litt plass til et fantastisk resultat:
[tex] \red f_n = \frac{1}{\sqrt{5}} \left( \phi^n - \varphi^n \right)[/tex]
Vi har altså en lukket form for Fibonaccisekvensen, uttrykt ved det gyldne snitt!
Okey, over til saken. Det er nå klart og tydelig at:
[tex]f_{2n} = \frac{1}{\sqrt 5} (\phi^{2n} - \varphi^{2n})[/tex]
Vi benytter oss så av at [tex] \phi^2 = \phi + 1[/tex] og [tex]\varphi^2 = \varphi + 1[/tex]
Dette gir oss at
[tex]f_{2n} = \frac{1}{\sqrt 5} \left[ (\phi + 1)^n - (\varphi+1)^{n} \right][/tex]
Parentesene kan ekspanderes ved binomialteoremet:
[tex]f_{2n} = \frac{1}{\sqrt 5} \left[ ( {n \choose 0} + {n \choose 1}\phi + \dots + {n \choose n}\phi^n ) - ({n \choose 0} + {n \choose 1}\varphi + \dots + {n \choose n}\varphi^n ) \right][/tex]
Og herfra ser vi resultatet følger direkte!
[tex]f_{2n} = {n \choose 1}f_1+ {n \choose 2}f_2 + \dots + {n \choose n}f_n[/tex]