recurrente betrekking

[Shadow]

Hay,
 

Recursieve betrekking 1165 keer bekeken

 
Ik heb een vraagje hierover - ik weet namelijk niet hoe ik voor deze twee gevallen (machtsheffing en Fibonaci) volledige inductie kan toepassen. Voor de rij van Fibonacci heb ik helemaal geen idee hoe de inductiestap zou moeten gaan, aangezien er naar mijn weten geen formule (naast die van d recurrente betrekking).
 
Bij machtsheffing ligt het anders, daar heb je aⁿ. Maar ook daar weet ik niet zeker hoe het inductiebewijs gaat, aangezien je zowel f(n) = aⁿ hebt als zijn recurrente vorm. Dit is puur gokken voor mij:
 
- f(0) = f(1) = 1
- Te bewijzen: f(n+1)= aⁿ⁺¹. Neem aan dat f(n)= aⁿ (ind. hypothese).* Dan geldt: f(n+1)= a·f(n)= a·aⁿ= aⁿ⁺¹
 
Ik weet het niet, ik denk dat ik een beetje de de draad kwijt ben.. Maar stel dat dit ongeveer klopt, wat zou dan de inductiehypothese van het bewijs voor de rij van Fibonacci zijn dan?
 
thx
 
* en ik denk dat je dan ook moet aannemen dat geldt f(n+1)=a·f(n)

[tempelier]

Laten we met machtsverheffen beginnen.
 
Neem aan dat de stelling waar is voor een zekere p en schrijf dit uit.

[Shadow]

Huh, waarom voor p? Je hebt toch al een n staan aan beide kanten van de betrekking - moet ik die nu vervangen door p?
 
f(p+1)= a·f(p)
 
f(p)= a^p
 
Maar op deze manier doe ik toch hetzelfde als wat ik al heb uitgeschreven?

[tempelier]

Uit wat er staat moet nu bewezen worden dat ook geldt:
 

\( f(p+1) = a^{p+1}\)

 
Pak hiervoor het linker lid aan.

[Shadow]

- Te bewijzen: f(n+1)= aⁿ⁺¹. Neem aan dat f(n)= aⁿ (ind. hypothese).* Dan geldt: f(n+1)= a·f(n)= a·aⁿ= aⁿ⁺¹

 
Ik heb toch al gedaan waar je nu naar vraagt?

[tempelier]

Wel dan is de stelling toch zo goed als bewezen:
Immers je hebt bewezen dat als het geldt voor p dan geldt het ook voor (p+1)
 
Als je even onderzoekt of hij ook geldt voor de begin waarde p=1 dan is de boel rond.
 
PS.
Je kunt beter niet de n gebruiken want dat is een lopende index wat verwarring kan geven dus pak een p zoals ik voorstelde.

[Demophilus]

- f(0) = f(1) = 1
- Te bewijzen: f(n+1)= aⁿ⁺¹. Neem aan dat f(n)= aⁿ (ind. hypothese).* Dan geldt: f(n+1)= a·f(n)= a·aⁿ= aⁿ⁺¹
 
Ik weet het niet, ik denk dat ik een beetje de de draad kwijt ben.. Maar stel dat dit ongeveer klopt, wat zou dan de inductiehypothese van het bewijs voor de rij van Fibonacci zijn dan?
 
thx
 
* en ik denk dat je dan ook moet aannemen dat geldt f(n+1)=a·f(n)

f(0)=1, ok maar dan is f(1)=af(0)=a. Het is trouwens ook helemaal niet nodig om dit te vermelden, de basisstap n=0 is genoeg hier.
Verder ziet het er goed uit hoor.
 
Voor Fibonacci, hangt het ervan af wat je wil bewijzen. Er bestaat (voor zover ik weet toch) geen gesloten uitdrukking voor de rij van fibonacci, dus deze kan je ook niet bewijzen.
Je kan wel bewijzen dat de Fibonacci rij uniek is. Begin dan als volgt neem aan dat

\(f_1: \mathbb{N} \to \mathbb{N}\)

en

\(f_2: \mathbb{N} \to \mathbb{N}\)

twee willekeurige Fibonacci rijen zijn. Dus

\(f_1(0)=f_1(1)=f_2(0)=f_2(1)=1\)

,  

\(f_1(n+2)=f_1(n+1)+f_1(n)\)

en

\(f_2(n+2)=f_2(n+1)+f_2(n)\)

. En bewijs nu (met inductie) dat

\( f_1=f_2\)

. Dan kan je concluderen dat de Fibonacci rij uniek is.
 
Ook nog een foutje:

Maar ook daar weet ik niet zeker hoe het inductiebewijs gaat, aangezien je zowel f(n) = aⁿ hebt als zijn recurrente vorm.

 
f(n)=aⁿ is geen recursieve definitie, in de definitie komt f zelf helemaal niet terug.

[Shadow]

Ik begrijp het bewijs voor machtsheffen nog steeds niet. Wat weet je nou wel en wat niet?
 
Je hebt:
f(n)= aⁿ (a in N⁺)
Hiervan ga je bewijzen dat de n voor elk natuurlijk getal kan staan.
 
En je hebt de recurrente betrekking:
f(n+1)= af(n)
En weet je hier nu of de n voor elk natuurlijk getal staat? Heb je per se de recurrente betrekking nodig om te bewijzen dat f(n)=aⁿ voor elk natuurlijk getal geldt?
 
Ik zie gewoon niet wat ze nou precies doen, waar ze nou wel en niet vanuit gaan, etc. En het helpt me niet dat mijn bewijs blijkbaar goed is, want ik zie er weinig [significante] structuur in. Het enige dat ik weet, is dat je bewijst dat f(n)=aⁿ voor elke n geldt, maar hoe die recurrente betrekking erin gebouwd wordt en wat daarbij wordt aangenomen en wat niet, dát zie ik niet.
 
Om mijn verwarring te illustreren: is de recurrente betrekking nou een definitie of niet? Is het al bewezen of moet het nog bewezen worden? Is dit bewijs wellicht ook het bewijs voor de geldigheid van de recurrente betrekking? Ik zie gewoon niet wat er gebeurt en ik weet dat het maar een klein, onnozel detail is dat is mis:P

[Safe]

Je hebt f(n+1)=af(n) met n={0,1,2, ... }, a een constante.
Wat kan je hiermee? 

[Demophilus]

Ik zie gewoon niet wat ze nou precies doen, waar ze nou wel en niet vanuit gaan, etc. En het helpt me niet dat mijn bewijs blijkbaar goed is, want ik zie er weinig [significante] structuur in. Het enige dat ik weet, is dat je bewijst dat f(n)=aⁿ voor elke n geldt, maar hoe die recurrente betrekking erin gebouwd wordt en wat daarbij wordt aangenomen en wat niet, dát zie ik niet.
 
Om mijn verwarring te illustreren: is de recurrente betrekking nou een definitie of niet? Is het al bewezen of moet het nog bewezen worden? Is dit bewijs wellicht ook het bewijs voor de geldigheid van de recurrente betrekking? Ik zie gewoon niet wat er gebeurt en ik weet dat het maar een klein, onnozel detail is dat is mis:P

Ja de recurrente betrekking is zeker een definitie. Wat je hier probeer the bewijzen is het volgende:

\( f(0)=1 \land f(n+1)=af(n) \Rightarrow f(n)=a^n \)

Uiteraard geldt hier ook de pijl in de andere richting.
Dus neem hier dit aan:

\( f(0)=a \land f(n+1)= af(n) \)

en probeer dan:

\(f(n)=a^n \)

te bewijzen.

[Safe]

Zie mijn vraag in post #9 ... 
Je stelt nl in post #1 dat f(0)=f(1)=1 en dat is niet juist ...

[Shadow]

Ja dat weet ik, dat had ik verkeerd opgeschreven.
 
Ik zie het gewoon niet als: f(n+1)= af(n) * <-> f(n)= a^{n **}
 
In mijn ogen spreekt het voor zich dat f(n)= aⁿ voor elke n geldt, ik zie niet in waarom dat bewezen moet worden.
 
Ze zeggen dat de f die aan * en ** voldoet, een functie is van N naar N. Maar een f die aan f(n)=aⁿ alleen al voldoet, is toch vanzelfsprekend een functie van N naar N? En als je de definitie f(n+1)= af(n) erbij doet, verandert dat toch niks?
 
Ik ga maar gewoon gerelateerde opdrachten proberen te maken, misschien wordt het me dan duidelijk.
 
En op je vraag in post #9: Ja, ik denk dat je f(n+1) kunt omschrijven naar een machtsheffing, waarmee je dan blijkbaar bewijst dat geldt f(n+1)=aⁿ⁺¹, maar ja, dat had ik ook kunnen zien zonder de recurrente betrekking, dus ik zie het nut er niet van in.
 
edit: oké wacht, dat zei ik verkeerd. Ze zeggen dat een functie die aan f die aan de recurrente betrekking voldoet een functie van N naar N is met f(n)= aⁿ. 
 
Laat maar, ik trek mijn vraag terug, ik moet waarschijnlijk gewoon meer lezen en hier meer vertrouwd mee raken.

[Safe]

En op je vraag in post #9: Ja, ik denk dat je f(n+1) kunt omschrijven naar een machtsheffing, waarmee je dan blijkbaar bewijst dat geldt f(n+1)=aⁿ⁺¹, maar ja, dat had ik ook kunnen zien zonder de recurrente betrekking, dus ik zie het nut er niet van in.

 
Je hebt twee mogelijkheden voor de functie f(n)=aⁿ en de recurrente betrekking f(n+1)=af(n), het essentiële punt hierin is dat de functie als variabele n met n={0,1,2,...} heeft, a constant en je moet aantonen dat de recurrente schrijfwijze wiskundig identiek is met de eerste. Maar daar hoort nog een voorwaarde bij, welke? 
Geef het bewijs volgens volledige inductie!
 
Heb je een idee waarom een recurrente schrijfwijze nuttig zou kunnen zijn?
Nog een vb: Welke functie (expliciet) behoort bij: f(n+1)=(n+1)f(n) met f(0)=1, hint: schrijf f(n) uit voor n=1,2,3 ...

[Shadow]

Ik weet niet over welke twee mogelijkheden je hebt?, bedoel je dat je zowel f(n)=aⁿ als f(n+1)=af(n) hebt (2 mog. dus)? Verder lijkt het me dat de voorwaarde die mist, de randvoorwaarde is.
 
Je vraagt me om het bewijs te leveren dat de twee schrijfwijzen identiek zijn, maar heb ik dat al niet gedaan dan? - of moet het op een andere manier?
 
Een reden waarom zo'n schrijfwijze nuttig kan zijn, is wellicht omdat je met zo'n definitie makkerlijk een inductiebewijs kunt geven (beide hebben te maken met de ordening van een verzameling). De functie die bij jouw voorbeeld hoort is de faculteitsfunctie.
 
Ik heb gekeken naar analoge voorbeelden, en het patroon dat ik zie is dat je begint met de recursieve definitie, waarbij je een aantal zaken aanneemt, zoals de randvoorwaarde en eventueel iets over constanten en dergelijke - en op basis van die gegevens bewijs je dat de expliciete functie klopt (= geldig is voor alle n).
 
Dus in mijn voorbeeld is gegeven:
f(n+1)= af(n)
f(0)=1
(a is een constante)
 
Te bewijzen:
f(n)=aⁿ (waarbij f een functie is van N naar N)
 
De inductiehypothese is dan f(n)=aⁿ, want je wilt dat wat rechts staat van de pijl in de recursieve definitie, omschrijven naar wat rechts van de pijl staat in de expliciete functie (maar dan voor n+1). Ik zie nu dat ik precies in woorden zeg wat Demophilus wiskundig had geformuleerd.
 
Ik weet alleen niet hoe ik kan aantonen dat de Fibonacci-reeksen 1 en 2 identiek zijn. Ik zie het wel - de randvoorwaarden zijn gelijk - maar ik weet niet hoe ik dit wiskundig kan uitdrukken. De basisstap spreekt voor zich, maar ik weet niet wat ik aan moet met de inductiestap.

[Demophilus]

Ik weet alleen niet hoe ik kan aantonen dat de Fibonacci-reeksen 1 en 2 identiek zijn. Ik zie het wel - de randvoorwaarden zijn gelijk - maar ik weet niet hoe ik dit wiskundig kan uitdrukken. De basisstap spreekt voor zich, maar ik weet niet wat ik aan moet met de inductiestap.

Wanneer zijn twee functies gelijk? Kun je dat wiskundig uitdrukken?