Fibonacci sequence - prove by induction

Printable View

December 23rd 2008, 01:58 PM
Dzahdo

Fibonacci sequence - prove by induction

Can someone please help me, I really don't know to do this task. It says it's a Fibonacci sequence. Anyway it could be tommorrow on my exam.

$a_n = {1 \over \sqrt{5}} \times \left[ \left({1 + \sqrt{5} \over 2}\right)^n - \left({1 - \sqrt{5} \over 2}\right)^n \right]$

It should be proven by induction.... I'm stuck on third step when n = k + 1.. I don't know what to do...

Help me until tommorrow please....

Thanks in advance... (Bow)
December 23rd 2008, 03:54 PM
TwistedOne151

$a_{k-1}+a_k=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k-1}-\left(\frac{1-\sqrt5}{2}\right)^{k-1}\right]$ $+\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$\;=\frac{1}{\sqrt5}\left[\left[\left(\frac{1+\sqrt5}{2}\right)^{k-1}+\left(\frac{1+\sqrt5}{2}\right)^{k}\right]-\left[\left(\frac{1-\sqrt5}{2}\right)^{k-1}+\left(\frac{1-\sqrt5}{2}\right)^{k}\right]\right]$
$\;=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k-1}\left[1+\left(\frac{1+\sqrt5}{2}\right)\right]-\left(\frac{1-\sqrt5}{2}\right)^{k-1}\left[1+\left(\frac{1-\sqrt5}{2}\right)\right]\right]$ .

Now, $1+\left(\frac{1+\sqrt5}{2}\right)=\frac{3+\sqrt5}{ 2}$ , and $\left(\frac{1+\sqrt5}{2}\right)^2=\frac{1+2\sqrt5+ 5}{4}=\frac{3+\sqrt5}{2}$ .
Similarly,
$1+\left(\frac{1-\sqrt5}{2}\right)=\frac{3-\sqrt5}{2}$ , and $\left(\frac{1-\sqrt5}{2}\right)^2=\frac{1-2\sqrt5+5}{4}=\frac{3-\sqrt5}{2}$ .

Thus the above becomes:
$a_{k-1}+a_k=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k-1}\left(\frac{1+\sqrt5}{2}\right)^2-\left(\frac{1-\sqrt5}{2}\right)^{k-1}\left(\frac{1+\sqrt5}{2}\right)^2\right]$
$\;=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$a_{k-1}+a_k=a_{k+1}$ .

--Kevin C.
December 23rd 2008, 04:29 PM
Dzahdo

Thank you, man. You solved it :D

Only thing is that we're solving induction by these steps:

1° check is the statement True for n = 1
2° assume that the statement is also true for n = k
3° with help of step 2° try to prove that the statement is true for n = k+1

so, I don't want to be rude, this here helps me, but can you explain a bit why this on the beginning:

$a_{k-1}+a_k$

It's just that I don't know the order of this task you've done, and what should I add, which factors...

Thanks alot man.. You really solved my problems... (Clapping)
December 23rd 2008, 05:19 PM
TwistedOne151

Remember the definition of the Fibonacci sequence: That $F_{n+1}=F_n+F_{n-1}$ , with initial values $F_0=0$ , $F_1=1$ . This is a second-degree difference equation/recurrence relation. You need to prove that your non-recursive formula holds for both those initial values. Then assume that it holds for n=k and n=k-1, and show that the formula fits the recursion relation $F_{n+1}=F_n+F_{n-1}$ ; this last step is what I did.

--Kevin C.