Results 1 to 6 of 6

Math Help - Fibonacci problem, proof by induction?

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    SD
    Posts
    3

    Question Fibonacci problem, proof by induction?

    Given:
    alpha = (1+ sqrt5)/2 and beta = (1-sqrt5)/2
    alpha^2 = 1 + alpha and beta^2 = 1+ beta

    Use induction to prove that for all integers n >= 1 we have
    alpha^n = f(n-1)+ f(n)*(alpha) and beta^n = f(n-1)+ f(n)*(beta)

    I've did my base case and plug in k+1 to n but I can't get them equal to each other. Please help, I've been playing with these numbers for hours.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Fibonacci problem, proof by induction?

    Having demonstrated the base case P_1 is true, then state the induction hypothesis P_k

    \alpha^k=F_{k-1}+F_{k}\alpha

    Multiply through by \alpha:

    \alpha^{k+1}=F_{k-1}\alpha+F_{k}\alpha^2

    \alpha^{k+1}=F_{k-1}\alpha+F_{k}(1+\alpha)

    \alpha^{k+1}=(F_{k}+F_{k-1})\alpha+F_{k}

    Now, since F_{n+1}=F_{n}+F_{n-1}, can you continue?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    SD
    Posts
    3

    Re: Fibonacci problem, proof by induction?

    so alpha^(k+1) = (alpha)*f(k+1) + f(k)
    sorry, I still don't know how is this a proof alpha^n = f(n-1)+ f(n)*(alpha)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Fibonacci problem, proof by induction?

    We may write this result as:

    \alpha^{k+1}=F_{(k+1)-1}+F_{k+1}\alpha

    You see, we have arrived at P_{k+1} which we derived from P_k, completing the proof by induction.

    Observe that this is the same as the induction hypothesis, except k is replaced with k+1. This means it is true for all n\in\mathbb{N}.

    Have you learned the analogy of climbing a ladder or falling dominoes to mathematical induction?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2012
    From
    SD
    Posts
    3

    Re: Fibonacci problem, proof by induction?

    oh okay, thanks. This problem is just very different to the kind of Fibonacci problem I've been doing. But they're just the same in the end. Thanks again : )
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Fibonacci problem, proof by induction?

    Glad to help, and welcome to the forum!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 04:41 PM
  2. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 11:22 AM
  3. Fibonacci number Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2009, 04:09 PM
  4. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 08:38 AM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 27th 2008, 11:19 AM

Search Tags


/mathhelpforum @mathhelpforum