Results 1 to 4 of 4

Math Help - Fibonacci Number Proof

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Fibonacci Number Proof

    Prove that

    	f_{2n+1} = f_{n+1}^2 + f_n^2

    for all positive integers.

    I assume the solution involves induction, but I'm having trouble with this... Any pointers would be greatly appreciated. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2
    Quote Originally Posted by VinceW View Post
    Prove that

    	f_{2n+1} = f_{n+1}^2 + f_n^2

    for all positive integers.

    I assume the solution involves induction, but I'm having trouble with this... Any pointers would be greatly appreciated. Thanks
    Yes, this involves induction.
    For n = 1, we have "2 = 1 + 1".
    For n >= 1, let's identify what we are trying to prove... i.e.


    	f_{2(n+1) + 1} = f_{(n+1) + 1}^2 + f_{(n+1)}^2

    Now use the definition of the Fibonacci sequence, and see what comes up (should/might involve some distribution)...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by VinceW View Post
    Prove that

    	f_{2n+1} = f_{n+1}^2 + f_n^2

    for all positive integers.


    I assume the solution involves induction, but I'm having trouble with this... Any pointers would be greatly appreciated. Thanks

    I suppose induction can be used here, but if you know the relation \displaystyle{f_n=\frac{\phi^n-\xi^n}{\sqrt{5}}\,,\,\,\phi:=\frac{1+\sqrt{5}}{2} \, ,\,\xi:=\frac{1-\sqrt{5}}{2}} , then the solution

    is straighforward, though you need to play algebraically quite a while with the resulting expressions.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    Proof, without induction (?)
    Define
    F= \left(\begin{array}{cc}1 & 1 \\ 1 & 0 \\\end{array}\right)


    so
     F^n=\left(\begin{array}{cc}F(n+1) & F(n) \\F(n) & F(n-1) \\ \end{array}\right).
    (by induction)

    General case
    F(n+p)=F(p)F(n+1)+F(p-1)F(n).



    Proof
    we have the matrix identity  F^n F^p =F^{n+p}
    so
     \left(\begin{array}{cc} F(n+1) & F(n) \\F(n) & F(n-1) \\\end{array}\right)\left(\begin{array}{cc}F(p+1) & F(p) \\F(p) & F(p-1) \\\end{array}\right)= \left(\begin{array}{cc}F(n+p+1) & F(n+p) \\F(n+p) &F(n+p-1) \\\end{array}\right)


    by multiplication of the matrices
    F(n+p)=F(n+1)F(p)+F(n)F(p-1).

    take p =n+1

    so

    F(2n+1)=F(n+1)^2+F(n)^2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 28th 2010, 12:05 AM
  2. Fibonacci number Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2009, 03:09 PM
  3. Fibonacci Number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2008, 02:04 PM
  4. Fibonacci number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 6th 2008, 08:59 PM
  5. Fibonacci number proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 16th 2008, 12:35 PM

/mathhelpforum @mathhelpforum