Bewijzen deelbaarheid van Fibonacci

Integraalrekening, afgeleiden, rijen, convergentie & divergentie van reeksen, meervoudige integratie.
Plaats reactie
Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 07 nov 2014, 21:14

Hoi,
Ik heb een opgave waar ik echt vastloop en het gaat over de rij van Fibonacci.

De vraag is: bewijs dat dan en slechts dan , met als definitie van de deelbaarheid: wanneer met .

Ons hele hoofdstuk gaat over Inductie, dus ik neem aan dat dat hier de bedoeling is. Ik heb natuurlijk al wat zitten puzzelen.

Ik weet: dus met en
dus met

Nu bewijs ik eerst van rechts naar links en neem ik aan dat 3 deelt n. Nu klopt het voor l=1, want dan krijg je en 2 is deelbaar door 2, dus geldt dat

Maar normaal zou je kiezen: nu n+1, maar klopt het dat ik het geval l+1 moet kiezen hier? Want n+1 lijkt totaal niet logisch, want dan klopt het niet eens. En als ik l+1 kies krijg ik:... en dan geen idee. Zal nog wat met m'n inductieaanname moeten dat het klopt voor een zekere m.

Plus, ik moet het ook de andere kant nog op bewijzen en ik zie daar nog niet echt een begin. Ik neem dus aan dat , maar ik weet niet zo goed wat ik daar mee moet, want niet alle termen in de rij van Fibonacci zijn deelbaar door 2.

Waar gaat het mis in mijn denkstappen?

Het probleem ligt bij mij dat ik dus iets voor n gekregen heb, daar weer een variabele in krijg en echt niet meer weet welke variabele ik moet gebruiken voor mijn inductie. Plus dat ik niet zo super goed weet hoe ik het aan moet pakken

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

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door arie » 07 nov 2014, 23:40

Kan je dit bewijzen:

ALS




DAN IS:




Kan je hiervoor ook een goed basisgeval vinden?

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 08 nov 2014, 15:12

Ik begrijp niet zo goed wat je bedoelt, Arie. Kan je het misschien iets meer toelichten?
In ieder geval, bedankt voor het meedenken alvast.

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

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door arie » 08 nov 2014, 21:39

Als inductie-stap van het bewijs nemen we:
Elk drietal opeenvolgende Fibonacci-getallen dat (oneven, oneven, even) is,
wordt gevolgd door:
een drietal opeenvolgende Fibonacci-getallen dat (oneven, oneven, even) is.
Merk op dat
2 | Fn <=> Fn is even

Met andere woorden: als (oneven, oneven, even) geldt voor het k-de drietal, dan geldt dit ook voor het (k+1)-de drietal.

Ga voor dit deel van het bewijs uit van de definitie van Fibonacci getallen:
F[n] = F[n-1] + F[n-2]
Als je weet dat F[n-1] oneven is, en F[n-2] is ook oneven, dan moet F[n] even zijn (de som van 2 oneven getallen is even).
Doe dit ook voor F[n+1], F[n+2] en F[n+3].

Als je dit hebt, hebben we ook nog een geschikte basis (beginsituatie) nodig. Welke neem je?

Kom je hiermee verder?

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 09 nov 2014, 16:04

Hoi Arie,
Ja, ik denk dat ik hier wel wat mee verder komt. Ik vind het alleen lastig wanneer je dingen mag stellen en niet. Ja, het is zo dat het steeds oneven,oneven,even,oneven,oneven,even.... is, dat is duidelijk ook uit de rij van Fibonacci. Ik neem aan dat je het dan voor een geval controleert: (F[n]=f[n-1]+f[n-2] en dan moet gaan kijken naar n+1. Maar dit kan dus niet de inductiestap zijn, omdat het daarvoor niet klopt.
Dus dan zou je inductieaanname worden dat het klopt voor f[3n] en dan kijken naar f[3(n+1)].

Want f[3(n+1)]=f[3n+3]=f[3n+2]+f[3n+1]=f[3n+1]+f[3n]+f[3n]+f[3n-1]=f[3n]+f[3n-1]+f[3n]+f[3n]+f[3n-1]=3*f[3n]+2*f[3n-1]

Omdat f[3n] even is, en 2*f[3n-1] ook deelbaar is door twee, dus even is, geldt dat f[3(n-1)] ook even is en dus deelbaar is door 2.

Nu ik dit bewijs zo uitschrijf, merk ik inderdaad dat mijn moeilijkheid zit in de basisstap en inductieaanname.
Laatst gewijzigd door Ilona op 09 nov 2014, 16:34, 2 keer totaal gewijzigd.

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 09 nov 2014, 16:32

Oke, dit is het eerste deel van mijn bewijs dan wanneer de vraag is:


Bewijs 2|F[n] <=> 3|n


<= eerst deze kant op, want ik dat deze zo klopt (behalve dan misschien de manier van noteren)

Stel 3|n, dan geldt volgens de definitie van deelbaarheid dat 3k=n

Basisstap: k=1 geeft F[3]=F[2]+F[1]=1+1=2 en dit is deelbaar door 2, dus geldt 2|F3
Aanname: Als 3|n dan 2|F(3k) voor een zekere
Inductiestap: te bewijzen: als 3|n, dan 2|F[3(k+1)]

F[3(k+1)]=F[3k+3]=F[3k+2]+F[3k+1]=F[3k+1]+F[3k]+F[3k]+F[3k-1]=F[3k]+F[3k-1]+F[3k]+F[3k]+F[3k-1]=3*F[3k]+2*F[3k-1]
Omdat F[3k] even is, en 2*F[3k-1] ook deelbaar is door twee, dus even is, geldt dat 2*F[3(k-1)] ook even is en dus deelbaar is door 2.

Dus bewezen dat als 3|n => 2|Fn


=> stel 2|Fn, dan geldt volgens de definitie van deelbaarheid dat 2p=Fn voor .

En dan loop ik eventjes vast.

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

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door arie » 10 nov 2014, 17:05

3|n => 2|Fn
kan iets korter:
F[3k+3] = F[3k+2] + F[3k+1] = (F[3k+1] + F[3k]) + F[3k+1] = F[3k] + 2*F[3k+1]

2|Fn => 3|n
Hiervoor kan en mag je ook de logische contrapositie bewijzen:
(NIET 3|n) => (NIET 2|Fn)

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 10 nov 2014, 18:53

Ah, dat is 'm! Geweldig! DAar had ik nu weer niet aan gedacht, dus daar ga ik maar eens mee aan de slag dan om nu te bewijzen.

O en dat korter is inderdaad wel handig. Nu is het niet verkeerd, maar hoe minder hoe minder kans op fouten ;)

SafeX
Moderator
Moderator
Berichten: 14248
Lid geworden op: 29 dec 2005, 11:53

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door SafeX » 11 nov 2014, 10:19

Misschien helpt het ook om de rij op te stellen modulo 2 ...

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 12 nov 2014, 22:29

Ik had al gereageerd, maar die is blijkbaar niet doorgekomen. Ja, modulo 2 is inderdaad handig en heb ik er nu grotendeels al in verwerkt!

Het probleem ligt bij mij op dit moment: hoe verwoord ik netjes de inductiehypothese?

Omdat 3|n, zeg ik dat n=3k. Dan bewijs ik het dus voor k=1. Maar hoe kan ik netjes formuleren dat ik dat dus niet voor n=1 doe? Want dat zou 'normaal' zijn.

De inductiehypothese wordt dan: Stel dat de uitspraak waar is voor een zekere n waarvoor geldt n=3k en F[3k]=2p.

Dan komt de inductiestap: neem nu k+1

Maar hoe leg ik dan netjes uit dat het geen n+1 is?
Ik vind het zo verwarrend omdat het een k en een n is en officieel zou je voor de volgende n moeten bewijzen. Maar die volgende n is +3 want anders is het niet meer deelbaar door 3. Logisch nadenkend klopt het dus gewoon, maar ik wil het ook netjes doen, daar gaat dit hele vak om.

SafeX
Moderator
Moderator
Berichten: 14248
Lid geworden op: 29 dec 2005, 11:53

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door SafeX » 16 nov 2014, 11:57

Ilona schreef: Het probleem ligt bij mij op dit moment: hoe verwoord ik netjes de inductiehypothese?
Is het duidelijk dat fibonacci mod 2 voldoende is voor deze opgave ... , lukt het om dit met volledige inductie te bewijzen?

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 16 nov 2014, 21:37

Ja het is uiteindelijk helemaal gelukt. Wel een lange lap tekst (maar ik schrijf groot ;) ) maar het is op deze manier gelukt. Ook door te de andere kant op te bewijzen dat wanneer geldt dat niet 3|n dan ook niet 2|fn.

Heel erg blij met jullie hulp op deze manier.

SafeX
Moderator
Moderator
Berichten: 14248
Lid geworden op: 29 dec 2005, 11:53

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door SafeX » 16 nov 2014, 21:47

Maar nogmaals, als je de de eig bewijst voor fib mod 2 ben je toch klaar ...

Gebruikersavatar
Ilona
Gevorderde
Gevorderde
Berichten: 100
Lid geworden op: 13 sep 2013, 11:33

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door Ilona » 17 nov 2014, 18:41

Op die manier lukte het me nog niet echt eigenlijk. Maar ik heb het andere topic gevolgd hier over en het is me nu wel iets duidelijker, maar wel iets waar ik de komende tijd nog even naar wil zoeken hoe ik dat precies kan doen.

SafeX
Moderator
Moderator
Berichten: 14248
Lid geworden op: 29 dec 2005, 11:53

Re: Bewijzen deelbaarheid van Fibonacci

Bericht door SafeX » 17 nov 2014, 18:44

Ok, laat wat zien ...

Plaats reactie