Rij van fibonnaci,expliciet voorschrift.

Dit forum is voor het voortgezetonderwijs (of 2de/3de graad ASO), als je in de bovenbouw zit. We gaan er vanuit dat je een Grafische Rekenmachine hebt.
fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 11:19

Ik was aan het rond zoeken naar dingen over de rij van fibonnaci, toen ik op dit bericht kwam:Fibonacci differentievergelijking.

Ik was natuurlijk zeer blij dit te vinden, maar ik kwam op 1 probleem terecht.

Hoe kan je het gebruik van de formule k*r^n (zie de eerste reactie van 'Arie' in mijn link) verklaren om de differentievergelijking te vinden, want als we op het eerste zicht zouden kijken, is het onmogelijk om dat die formule een juist getal kan leveren.
Ik begrijp het gebruik er wel van, maar ik kan niet verklaren waarom dit mag.

Hopelijk kan iemand mij hier uitleg bij verschaffen.

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 13:38

Er zijn een aantal manieren om die formule af te leiden, zie bijvoorbeeld http://ulcar.uml.edu/~iag/CS/Fibonacci.html waar ze genererende functies en karakteristieke polynomen gebruiken.
Dergelijke technieken zijn niet voor iedereen basiskennis, daarom hebben we de oplossing op dit forum intuitief afgeleid, uitgaande van de oplossing voor een eerste orde recurrente betrekking: a(n)=k*r^n, en die verder uitgewerkt. We hebben hierbij dus zeker GEEN harde wiskundige theorie aangenomen, en waren vooraf ook niet zeker van een correcte uitkomst.
Daarom hebben we daarna nog wel moeten bewijzen dat onze uiteindelijke formule inderdaad de juiste formule is.

Meer theorie achter de karakteristieke polynomen (voor Fibonacci is dit een tweede-orde lineaire homogene betrekking met constante coefficienten) kan je bv hier vinden:
http://en.wikipedia.org/wiki/Recurrence_relation,
daar staan ook een heleboel literatuurverwijzingen.
Als je van deze technieken uitgaat kom je uiteraard sneller tot je antwoord.

fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 13:52

Helaas geraak ik aan jouw links van polynomen niet uit, aangezien ik deze ook niet ken. Ik zit nu in het 5de (ASO), en dat hebben we (nog?) niet gezien.

Er is dus geen verdere verklaring mogelijk buiten het intuïtief gebruik van k*r^n?
'Daarna moeten we natuurlijk nog wel moeten...'
Bedoel je hiermee het bewijs van volledige inductie? Deze staat, dacht ik, ook nog niet in het andere topic, dus daar zal ik mijn best ook nog op moeten doen.

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 13:58

Die theorie is inderdaad allemaal nogal ingewikkeld, vandaar dat we ook voor onze oplossing gekozen hebben.

De correctheid van de oplossing hebben we aangetoond met volledige inductie.
Het is heel goed dat je dit eerst zelf probeert aan te tonen.
Ik heb dit daar overigens wel uitgewerkt (op "01 Dec 2010, 16:09", pagina 2 van dat topic).

fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 14:17

Al je hulp is hoogst geapprecieerd, maar helaas blijft toch nog mijn oorspronkelijke vraag bestaan.
Is er een betere verklaring voor het gebruik van k*r^n dan intuïtief gebruik?

Op een andere link zeiden ze dat deze wel vaker werd gebruikt bij een vermoeden, maar dus weer intuïtief:
"Dit is een methode die in de wiskunde wel vaker wordt gebruikt: aan de hand van een
vermoeden proberen we een oplossing voor een probleem te vinden. Als we vervolgens
een oplossing gevonden hebben, moeten we natuurlijk nog wel bewijzen dat deze
oplossing juist is, met andere woorden: we moeten ons vermoeden bewijzen. "

van link: http://www.phys.tue.nl/TULO/guldensnede/rijen6.html

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 14:38

Hebben je al eens gewerkt met het produkt van een matrix en een vector?

Bijvoorbeeld: kan je de uitkomst van



bepalen?

fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 14:54

ja, maar het zit ver
=
5
8
??

Even een vraagje terzijde: hoe doe jij die formules zo, dat is misschien ook handiger voor jou als ook ik dat zo doe. Met Word?

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 15:58

Formules kan je hier eenvoudig invoeren via de knop "Equation Editor" rechts boven het invoerveld.
Het werkt via LaTeX, symboollijsten kan je terugvinden bv op http://omega.albany.edu:8008/Symbols.html
alle tekst die je tussen [ tex] en [ /tex] haken zet (zonder de spatie na [ ) wordt als formule weergegeven.
Bijvoorbeeld \sqrt{\alpha}:

[ Formule] en [ /Formule] werken vergelijkbaar.
Zie ook subforum TeX hulp op onze forumindex.

Maar nu Fibonacci:
Je uitkomst is goed.
Nu heb je de matrix F zoals hierboven:



Als je deze vermenigvuldigt met vector v:



krijg je:



Zie je het patroon?
Noem fib(n) het n-de Fibonacci getal.
Als x=fib(n) en y=fib(n+1), wat is dan x+y in de resultaatvector?

fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 16:14

het 3de fibonnaci-getal: fib(n+2)



en het getal fib(n)+fib(n+1) is dan het volgende fibonnaci-getal

'Zie je het patroon': je bedoelt je vermenigvuldiging van matrices? Ja dan.

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 16:42

Correct.
We hebben:



ofwel:



Maar we hebben ook:



ofwel:



ofwel:



En we hebben in het algemeen:



We kunnen nu, uitgaande van fib(0) en fib(1) voor elke n de waarde van fib(n) (en fib(n+1)) bepalen via bovenstaande formule.
We willen echter een formule voor fib(n) zonder die matrix.
Dit kunnen we bereiken via enkele bijzondere vectoren v1 en v2 (de Eigenvectoren) die beide NIET de nulvector zijn, en die beide ook een waarde (= reeel getal) labda hebben: labda1 resp. labda2 (de Eigenwaarden), zodanig dat:



ofwel (vermenigvuldig rechts met de eenheidsmatrix):









En voor dit stelsel bestaan alleen oplossingen v die niet de nulvector zijn als de determinant van de laatste 2x2 matrix nul is.
Kan je bepalen voor welke waarden van labda dit geldt?

fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 17:01

wij noemden deze niet labda, maar landa, maar dat terzijde, aangezien het niet echt uitmaakt.
Dus nu moet ik de determinant bepalen van dat getal.
als ik met niet vergis, is de determinant van een 2x2-matrix:
matrix:
A B
C D

a*d-b*c

mijn labda is nu even een x, simpelder te typen, want die codes lukken niet zo goed bij mij:
x²-x-1=0

X1=(1+√5)/2
X2=(1-√5)/2

De waarde van de gulden snede dus, wat ook niet verwonderlijk is.

EDIT: even nog dit vraagje terzijde:
Je zegt: fib(1) en fib(0) als je vector (als ik me niet vergis?). Bedoel je daarmee dus de waarde 1 en waarde 0? Dus dat je als volgende, volgens de matrix dus, fib(2), waarde 2 dus, fib(3)->3 en dan fib(5)?

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 18:36

Mbt je edit:
fib(0)=0
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
etc.

We lossen nu v op uit het stelsel:



ofwel:



waarbij:



Omdat het stelsel afhankelijk is (anders had het slechts 1 oplossing) kunnen we volstaan met 1 van de 2 vergelijkingen, neem bv:


We kijken nu naar de 2 eigenwaarden die je gevonden had:
[1]
voor geldt:
stel v2 = rho, dan is










dus



rho mogen we vrij kiezen, neem bv rho=1 en je hebt als eerste eigenvector e1 = v behorend bij deze lambda:




[2]
voor de tweede eigenwaarde kom ik vergelijkbaar uit op:



reken dit zelf s.v.p. even na.



We hebben nu eigenvector e1 horend bij lambda1 en eigenvector e2 horend bij lambda2 gevonden.
Als voorlaatste stap moeten we nu



uitdrukken in e1 en e2.

Kan je de waarden a en b vinden, zodanig dat


fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 07 mei 2011, 20:52

Ik kom bij je tweede eigenwaarde hetzelfde uit.
Maar ik vroeg me af, en waarschijnlijk omdat ik mijn matrices niet meer helemaal kan, hoe jij die matrix in volgende bekomt:


Vanwaar die 1 van de matrix?
EDIT: laat ook maar, die is van de rho, maar waarom mogen wij die dan kiezen?

Tenslotte kom ik voor a en b:
a= (1+√5)/(2√5)
b= (-1+√5)/(2√5)
maar als deze niet kloppen is dat waarschijnlijk omdat ik de eerste stap van de berekening fout heb.
Maar de a en b kloppen wel denk ik

arie
Moderator
Moderator
Berichten: 3920
Lid geworden op: 09 mei 2008, 09:19

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door arie » 07 mei 2011, 22:14

We hadden het stelsel


ofwel:



Deze 2 vergelijkingen zijn afhankelijk.
Een ander voorbeeld zou zijn:
2x + y = 0
6x + 3y = 0
ook hier kunnen we 1 van de 2 vergelijkingen nemen, bv
2x + y = 0
stel y=rho, dan is x=-rho/2
Alle oplossingen van dit stelsel hebben dan de vorm

met rho vrij te kiezen: voor elke waarde van rho is de oplossing geldig.
Wij zochten een oplossing die niet de nulvector is, dus elke rho behalve rho=0 kunnen we vrij kiezen.


Ik kom uit op dezelfde waarden voor a en b:
a= (1+√5)/(2√5) = (5+√5)/10
b= (-1+√5)/(2√5) = (5-√5)/10

We hebben nu:





We gaan nu terug naar het begin:



en substitueren





Gebruik nu :



Waarbij we alleen naar de bovenste coordinaat hoeven te kijken:



en herleid:



En dit is de formule die we zochten, nu afgeleid via de matrixrekening = lineaire algebra.
(lambda1 en lambda2 had je al eerder uitgerekend hierboven: jouw X1 en X2).

Merk op dat we de karakteristieke vergelijking via deze weg nu echt hebben afgeleid (bij de bepaling van de eigenwaarden van matrix F), en niet intuitief hebben bepaald, zoals in de vorige topic (via k*r^n).
Je moet voor deze afleiding alleen wel wat van lineaire algebra af weten.

fibonnaci
Nieuw lid
Nieuw lid
Berichten: 12
Lid geworden op: 07 mei 2011, 11:12

Re: Rij van fibonnaci,expliciet voorschrift.

Bericht door fibonnaci » 08 mei 2011, 09:14

Wow, dank je!

Met lineaire algebra bedoel je met matrices enzo kunnen rekenen?

Kan je me nog uitleggen waarom dit ookalweer geld:


waarschijnlijk weet ik dit wel,aangezien ik matrices al ken, maar het is al een tijdje geleden dat ik dat nog heb gedaan. Ik weet dat je de labda en eenheidsmatrix nodig hebt om de eigenwaarden te bereken, is dat gewoon wat je eigenlijk de eerste keer deed?
Waarvoor staat die vi ? Want deze wordt een v, dus waarvoor staat de i? iets met de eenheidsmatrix?

En: onze eerste matrix is toch opgebouwd uit de fibonacci getallen (want ik moet natuurlijk alles kunnen verklaren)
A^n=


met fib(0)=0 en fib (1)= 1 en dus geldt dat voor iedere n 1 ?


Ik ga hem eens uitschrijven en dan weer posten,hopelijk wil je hem dan nog eens bekijken, of ik kan hem altijd eens via een privé-bericht doorsturen.=)
En deze heb ik ook nog gevonden: iemand die vanaf de lambda via de euclidische deling (d*q+r) verder gaat. Moet je maar eens bekijken als je geïnteresseerd bent: http://www.uhasselt.be/documents/uhasse ... RijenA.pdf

Dank je!

Plaats reactie