# Fibonacci sequence - prove by induction

• Dec 23rd 2008, 02: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...

• Dec 23rd 2008, 04: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.
• Dec 23rd 2008, 05: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)
• Dec 23rd 2008, 06: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.