Results 1 to 5 of 5

Math Help - Recursion Proof

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Recursion Proof

    Can anyone help me with this proof?

    "Show that f_{n+1}f_{n-1}-f^2_n=(-1)^n when n is a positive integer."
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Use induction and the recursion formula: f_0 = 0, \ f_1 = 1, \ f_{n+1} = f_{n} + f_{n-1} \quad \forall n \geq 1

    Let P_n be the statement that f_{n+1}f_{n-1}-f^{\ 2}_n=(-1)^n, for all positive integer n.

    Base case: P_1 says that f_2f_0 - f_1^{\ 2} = (-1)^1 which is true.

    Inductive step: Assume P_k to be true, that is, f_{k+1}f_{k-1}-f^{\ 2}_k=(-1)^k for some positive k. It remains to show that P_{k+1} is also true, that is, f_{k+2}f_{k}-f^{\ 2}_{k+1}=(-1)^{k+1}.

    f_{k+2}f_{k}-f^{\ 2}_{k+1}
    = \left(f_{k+1} + f_{k}\right)f_{k} - f_{k+1}^2
    = f_{k+1}f_{k} + f_k^{\ 2} - f_{k+1}^{\ 2}
    = f_{k+1} \left( {\color{red}f_{k} - f_{k+1}}\right) + f_{k}^{\ 2} ........... What is the red equal to? Recall the recursive definition and everything should work out.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    8
    Alright, I've been trying to prove this through induction and using the Fibonacci Sequence.

    f_{n+1}f_{n-1}-f^2_n=(-1)^n when n is a positive integer.

    Assume this is true for n, and prove this for n=n+1 by Induction Hypothesis

    Basis: f_{2}f_{0}-f^2_1=(-1)^1
    Fibonacci Sequence: F(0)=0 F(1)=1 for F(n+1)=F(n)+F(n-1)
    Therefore, this is trivially true.

    f_{n+1+1}f_{n+1-1}f^2_{n+1}=(-1)^{n+1}
    f_{n+2}f_n-f^2_{n+1}=(-1)(-1)^n

    Scratch:
    When using Fibonacci's Sequence we can use the relationships between f_n, f_{n+1}, f_{n+2}. But I think we're missing a fourth term, so I added f_{n+3}.

    I tried to multiply the first terms to get the third and manipulate it by the Fibonacci's numbers and write one in terms of the other. But I ended up with some fractional expressions such as: f_n=(f_{n+3})/(f_{(n+1}) and f_{n+1}=(f_{n+3})/(f_{n+2})

    I'm not sure how close I am to solving it or if there is an easier way. Could anyone finish this for me or work it out differently? Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Define the matrix A = \begin{bmatrix} 1&1\\1&0 \end{bmatrix}

    We can show A^n = \begin{bmatrix} f_{n+1}&f_n \\ f_n&f_{n-1} \end{bmatrix}

    It follows \det A^n = (\det A)^n

    Therefore, f_{n+1}f_{n-1} - f_n^2 = (-1)^n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    See here

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recursion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 13th 2009, 08:00 AM
  2. Replies: 2
    Last Post: September 29th 2009, 01:44 PM
  3. Root 2 recursion proof help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 27th 2009, 03:31 AM
  4. Proof: Recursion Equality
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 17th 2009, 10:09 AM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2008, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum