Pagina 1 van 1

Expliciet voorschrift rij v. Fibonacci algebraïsch oplossen met volledige inductie

Geplaatst: 10 nov 2020, 13:11
door Fibonacci
Hallo

Ik wil graag het expliciete voorschrift van de rij van Fibonacci, f(x)=((1+〖√5)〗^x-(1-〖√5)〗^x)/(2^x •√5), bewijzen met behulp van volledige inductie. Nu heb ik op deze website een manier gevonden met matrices ( viewtopic.php?f=24&t=4617&hilit=fibonacci+expliciet ), maar ik zou het graag indien mogelijk algebraïsch oplossen.
Kan iemand mij hierbij helpen?
Alvast bedankt!

Re: Expliciet voorschrift rij v. Fibonacci algebraïsch oplossen met volledige inductie

Geplaatst: 11 nov 2020, 12:13
door arie
Te bewijzen via volledige inductie:
\(f(n)=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n\sqrt{5}}\)

Basis:
\(f(0)=\frac{(1+\sqrt{5})^0-(1-\sqrt{5})^0}{2^0\sqrt{5}}=\frac{1-1}{\sqrt{5}}=0\)
\(f(1)=\frac{(1+\sqrt{5})^1-(1-\sqrt{5})^1}{2^1\sqrt{5}}=\frac{1+\sqrt{5}-1+\sqrt{5}}{2\sqrt{5}}=1\)
Dus de formule geldt voor n=0 en n=1.
Deze stap heb je waarschijnlijk zelf ook al gevonden.

Inductie:
We moeten nu aantonen:
"als de formule geldt voor (n-1) en (n-2), dan geldt deze ook voor n"
Volgens de definitie van de rij van Fibonacci is
\(f(n) = f(n-1) + f(n-2)\)

Volgens de inductiehypothese geldt dan:
\(f(n)=\frac{(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}}{2^{n-1}\sqrt{5}} + \frac{(1+\sqrt{5})^{n-2}-(1-\sqrt{5})^{n-2}}{2^{n-2}\sqrt{5}}\)

We willen de breuken optellen, maak beide noemers gelijk:
\(f(n)=\frac{2\cdot[(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}]}{2\cdot 2^{n-1}\sqrt{5}} + \frac{4\cdot [(1+\sqrt{5})^{n-2}-(1-\sqrt{5})^{n-2}]}{4\cdot 2^{n-2}\sqrt{5}}\)

\(=\frac{2\cdot[(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}]}{2^n\sqrt{5}} + \frac{4\cdot [(1+\sqrt{5})^{n-2}-(1-\sqrt{5})^{n-2}]}{2^n\sqrt{5}}\)

\(=\frac{2\cdot[(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}]+4\cdot [(1+\sqrt{5})^{n-2}-(1-\sqrt{5})^{n-2}]}{2^n\sqrt{5}}\)

Nu moeten we aantonen dat deze breuk gelijk is aan

\(\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n\sqrt{5}}\)

De noemers zijn al gelijk, dus we moeten alleen nog aantonen dat ook de tellers gelijk zijn:

\(2\cdot [(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}]+4\cdot [(1+\sqrt{5})^{n-2}-(1-\sqrt{5})^{n-2}] = (1+\sqrt{5})^n-(1-\sqrt{5})^n\)

Lukt je dit?

Re: Expliciet voorschrift rij v. Fibonacci algebraïsch oplossen met volledige inductie

Geplaatst: 17 mar 2023, 21:39
door marthenys
hallo
Ik moet voor school een onderzoek doen naar de rij van Fibonacci en zou dit ook graag algebraïsch bewijzen. Maar ik geraak niet verder.
Zou iemand misschien het laatste deel van de reactie van Arie ook verder kunnen oplossen?

Alvast super bedankt!

Re: Expliciet voorschrift rij v. Fibonacci algebraïsch oplossen met volledige inductie

Geplaatst: 18 mar 2023, 09:06
door arie
We moeten aantonen dat
\(2\cdot [(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}]+4\cdot [(1+\sqrt{5})^{n-2}-(1-\sqrt{5})^{n-2}] = (1+\sqrt{5})^n-(1-\sqrt{5})^n\)
ofwel dat
\(2\cdot (1+\sqrt{5})^{n-1}- 2\cdot (1-\sqrt{5})^{n-1}+4\cdot (1+\sqrt{5})^{n-2}- 4 \cdot(1-\sqrt{5})^{n-2} = (1+\sqrt{5})^n-(1-\sqrt{5})^n\)

Splits deze laatste vergelijking in 2 delen op basis van het grondtal (dus \( (1+\sqrt{5})\) tegenover \((1-\sqrt{5})\)):
vergelijking [1] :
\(2\cdot (1+\sqrt{5})^{n-1}+4\cdot (1+\sqrt{5})^{n-2} = (1+\sqrt{5})^n\)
vergelijking [2]:
\(-2\cdot (1-\sqrt{5})^{n-1}-4\cdot (1-\sqrt{5})^{n-2} = -(1-\sqrt{5})^n\)
Als we kunnen aantonen dat allebei deze vergelijkingen gelden, dan geldt ook onze oorspronkelijke vergelijking.

Vergelijking [1]:
We tonen eerst aan dat linker en rechter lid van vergelijking [1] gelijk zijn:
\(2\cdot (1+\sqrt{5})^{n-1}+4\cdot (1+\sqrt{5})^{n-2} \overset{?}{=} (1+\sqrt{5})^n\)
isoleer uit elke term een factor \((1+\sqrt{5})^{n-2}\):
\(2\cdot (1+\sqrt{5}) \cdot (1+\sqrt{5})^{n-2}+4\cdot (1+\sqrt{5})^{n-2} \overset{?}{=} (1+\sqrt{5})^2\cdot (1+\sqrt{5})^{n-2}\)
deel links en rechts door deze factor \((1+\sqrt{5})^{n-2}\):
\(2\cdot (1+\sqrt{5}) +4 \overset{?}{=} (1+\sqrt{5})^2\)

Lukt het je om dit laatste aan te tonen (dus dat links en rechts gelijk zijn)?

Lukt het je vervolgens ook om vergelijking [2] aan te tonen?

Re: Expliciet voorschrift rij v. Fibonacci algebraïsch oplossen met volledige inductie

Geplaatst: 18 mar 2023, 10:18
door marthenys
Ja, echt super bedankt!