Results 1 to 4 of 4

Thread: Fibonacci sequence - prove by induction

  1. #1
    Newbie
    Joined
    Apr 2006
    Posts
    3

    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.

    $\displaystyle 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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276
    $\displaystyle 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]$ $\displaystyle +\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
    $\displaystyle \;=\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]$
    $\displaystyle \;=\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, $\displaystyle 1+\left(\frac{1+\sqrt5}{2}\right)=\frac{3+\sqrt5}{ 2}$, and $\displaystyle \left(\frac{1+\sqrt5}{2}\right)^2=\frac{1+2\sqrt5+ 5}{4}=\frac{3+\sqrt5}{2}$.
    Similarly,
    $\displaystyle 1+\left(\frac{1-\sqrt5}{2}\right)=\frac{3-\sqrt5}{2}$, and $\displaystyle \left(\frac{1-\sqrt5}{2}\right)^2=\frac{1-2\sqrt5+5}{4}=\frac{3-\sqrt5}{2}$.

    Thus the above becomes:
    $\displaystyle 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]$
    $\displaystyle \;=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
    $\displaystyle a_{k-1}+a_k=a_{k+1}$.

    --Kevin C.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2006
    Posts
    3
    Thank you, man. You solved it

    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:

    $\displaystyle 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...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276
    Remember the definition of the Fibonacci sequence: That $\displaystyle F_{n+1}=F_n+F_{n-1}$, with initial values $\displaystyle F_0=0$, $\displaystyle 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 $\displaystyle F_{n+1}=F_n+F_{n-1}$; this last step is what I did.

    --Kevin C.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: May 4th 2011, 02:02 PM
  2. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 19th 2011, 03:41 PM
  3. Mathematical Induction for Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 2nd 2010, 01:01 AM
  4. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Oct 1st 2010, 10:22 AM
  5. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 14th 2009, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum