Results 1 to 4 of 4

Math Help - 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.

    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
    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.
    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:

    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 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.
    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: January 19th 2011, 03:41 PM
  3. Mathematical Induction for Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 2nd 2010, 01:01 AM
  4. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 10:22 AM
  5. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum