La [tex]f_0=f_1=1,\ f_{n+2}=f_{n+1}+f_n[/tex] være Fibonaccitalla.
Vis eller motbevis at
[tex]\sum_{k=0}^n {n\choose k} f_k = f_{2n}[/tex]
og
[tex]\sum_{k=0}^n (-1)^n {n\choose k} f_k = f_{n-2}[/tex]
for n>1.
Binomialkoeffisienter og Fibonacci
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Jeg er alt for trøtt til å gå inn i problemet nå etter en slitsom dag. Men jeg kan bekrefte at
[tex]\sum_{k=0}^{10} {10\choose k} f_k = 10946[/tex]
og at
[tex]f_{20}=10946 [/tex]
Problemet er intressant da det ligner en del på det jeg sliter med for tiden. Du satte meg definitivt på en idè. Jeg skal se nærmere på det når jeg får tid.
[tex]\sum_{k=0}^{10} {10\choose k} f_k = 10946[/tex]
og at
[tex]f_{20}=10946 [/tex]
Problemet er intressant da det ligner en del på det jeg sliter med for tiden. Du satte meg definitivt på en idè. Jeg skal se nærmere på det når jeg får tid.
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]
- 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]
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Elegant!
Forskyvninga av Fibonaccitalla var ikke helt vellykka, jeg ville ha det til å matche bedre med indekser, men burde nok latt være.
Bok tilgjengelig på nett + fri printerkvote = uheldig kombinasjon; jeg skal ta en titt på den seinere. Fint å demonstrere teknikken, men du er sikkert klar over at den røde formelen også kan finnes utelukkende ved differensligninga som mange sikkert vil finne enklere.
Forskyvninga av Fibonaccitalla var ikke helt vellykka, jeg ville ha det til å matche bedre med indekser, men burde nok latt være.
Bok tilgjengelig på nett + fri printerkvote = uheldig kombinasjon; jeg skal ta en titt på den seinere. Fint å demonstrere teknikken, men du er sikkert klar over at den røde formelen også kan finnes utelukkende ved differensligninga som mange sikkert vil finne enklere.
Det har du nok helt rett i, men jeg har ikke kommet meg til å få studert differenslikninger ennå, så genererende funksjoner har blitt min "leatherman" til rekursjoner og slikt
Utledningen av den røde formelen over finnes forresten også på side 40 i gf-ology
Utledningen av den røde formelen over finnes forresten også på side 40 i gf-ology