Results 1 to 5 of 5

Thread: Recursion Proof

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Recursion Proof

    Can anyone help me with this proof?

    "Show that $\displaystyle f_{n+1}f_{n-1}-f^2_n=(-1)^n$ when $\displaystyle 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,410
    Thanks
    1
    Use induction and the recursion formula: $\displaystyle f_0 = 0, \ f_1 = 1, \ f_{n+1} = f_{n} + f_{n-1} \quad \forall n \geq 1$

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

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

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

    $\displaystyle f_{k+2}f_{k}-f^{\ 2}_{k+1}$
    $\displaystyle = \left(f_{k+1} + f_{k}\right)f_{k} - f_{k+1}^2 $
    $\displaystyle = f_{k+1}f_{k} + f_k^{\ 2} - f_{k+1}^{\ 2}$
    $\displaystyle = 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.

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

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

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

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

    Scratch:
    When using Fibonacci's Sequence we can use the relationships between $\displaystyle f_n, f_{n+1}, f_{n+2}$. But I think we're missing a fourth term, so I added $\displaystyle 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: $\displaystyle f_n=(f_{n+3})/(f_{(n+1})$ and $\displaystyle 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 $\displaystyle A = \begin{bmatrix} 1&1\\1&0 \end{bmatrix} $

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

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

    Therefore, $\displaystyle 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: Dec 13th 2009, 07:00 AM
  2. Replies: 2
    Last Post: Sep 29th 2009, 12:44 PM
  3. Root 2 recursion proof help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Aug 27th 2009, 02:31 AM
  4. Proof: Recursion Equality
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Feb 17th 2009, 09:09 AM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 16th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum