Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Math Help - Proof by induction

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    290

    Proof by induction

    I need to proove by induction that for the Fibonacci sequence

    (Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

    Fn being a Fibonacci number

    Is there anyone capable of doing this or know where on the internet I can find it. I have spent over 1 hrs trying to find something, without success.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Natasha1
    I need to proove by induction that for the fibonacci sequence

    (Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

    Is there anyone capable of doing this or know where on the internet I can find it. I have spent over 1 hrs trying to find something, without success.
    Something is wrong because n=1
    F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    Quote Originally Posted by ThePerfectHacker
    Something is wrong because n=1
    F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0
    This formula shows that for even Fib numbers you get -1 and odd ones you get +1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Natasha1
    This formula shows that for even Fib numbers you get -1 and odd ones you get +1
    But the formula is clearly wrong.
    Unless you want to say, that starting with some value for n it is correct, for example, n>1. I believe I have seen this identity somewhere and will search through my book if I can find it. Then possibly posts their proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    What I am trying to say is:

    1, 1, 2, 3, 5, 8, 13.....


    if you do take f1*f3 - f2^2 you get 1
    for the next in the series f2 you get f2*f4 - f3^2 you get -1

    What I'm saying is that you keep having 1, -1, 1, -1 for ever.... and i need to proove that. Can't find it on the net?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    (Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1
    Presumably should be read as (F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}. I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    Quote Originally Posted by rgep
    Presumably should be read as (F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}. I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.
    rgep you are spot on!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Okay,
    F(n)^2-F(n+1)F(n-1)= F(n)(F(n-1)+F(n-2))-F(n+1)F(n-1)*
    =F(n)F(n-1)+F(n)F(n-2)-F(n+1)F(n-1)
    =(F(n)-F(n+1))F(n-1)+F(n)F(n+2)
    =(-1)(F(n-1)^2-F(n)F(n-2))*
    *)Used the fibonacci recrusion formula,

    Thus,
    F(n)^2-F(n+1)F(n-1)= (-1)(F(n-1)^2-F(n)F(n-2))
    Note, the subscripts decrease by one with a negative in front.
    Thus,
    (-1)(F(n-1)^2-F(n)F(n-2))= (-1)^2(F(n-2)^2-F(n-1)F(n-3))
    Thus,
    F(n)^2-F(n+1)F(n-1)= (-1)^2(F(n-2)^2-F(n-1)F(n-3))
    Countinuing this n-2 times we have,
    F(n)^2-F(n+1)F(n-1)= (-1)^{n-2}(F(2)^2-F(3)F(1))= (-1)^{n-2}(-1)=(-1)^{n-1}

    Q.E.D.
    Last edited by ThePerfectHacker; May 26th 2006 at 11:15 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    Quote Originally Posted by ThePerfectHacker
    Okay,
    F(n)^2-F(n+1)F(n-1)= F(n)(F(n-1)+F(n-2))-F(n+1)F(n-1)*
    =F(n)F(n-1)+F(n)F(n-2)-F(n+1)F(n-1)
    =(F(n)-F(n+1))F(n-1)+F(n)F(n+2)
    =(-1)(F(n-1)^2-F(n)F(n-2))*
    *)Used the fibonacci recrusion formula,

    Thus,
    F(n)^2-F(n+1)F(n-1)= (-1)(F(n-1)^2-F(n)F(n-2))
    Note, the subscripts decrease by one with a negative in front.
    Thus,
    (-1)(F(n-1)^2-F(n)F(n-2))= (-1)^2(F(n-2)^2-F(n-1)F(n-3))
    Thus,
    F(n)^2-F(n+1)F(n-1)= (-1)^2(F(n-2)^2-F(n-1)F(n-3))
    Countinuing this n-2 times we have,
    F(n)^2-F(n+1)F(n-1)= (-1)^{n-2}(F(2)^2-F(3)F(1))= (-1)^{n-2}(-1)=(-1)^{n-1}

    Q.E.D.
    Here's a virtual kiss x :-). By the way the recursive formula is fn = fn-1 + fn-2, for n = 2, 3, 4, ... where f0 =1, f1 = 1, no?. Which would make this invalid as f0 = 0, f1 = 1, so that f2 = 1
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Natasha1
    Here's a virtual kiss x :-). By the way the recursive formula is fn = fn-1 + fn-2, for n = 2, 3, 4, ... where f0 =1, f1 = 1, no?. Which would make this invalid as f0 = 0, f1 = 1, so that f2 = 1
    f0 is not used here,
    f1=1
    f2=1
    f3=2
    ....
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    is this an induction proof?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Natasha1
    is this an induction proof?
    Not really.
    --
    You can turn it into an induction proof.

    Since there is a k\geq 2 such as,
    F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}
    Then proof it hold for k+1. But the expression,
    F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1)) as explained in my other proof. But,
    F(k)^2-F(k+1)(k-1)=(-1)^{k-1}
    Thus,
    F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k
    Thus, it hold true for k+1 and the proof is complete.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,830
    Thanks
    123
    Quote Originally Posted by ThePerfectHacker
    Something is wrong because n=1
    F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0
    Hello,

    F(1)F(3)-(F(2))^2=\underbrace{2-1=2}_\csub{\mbox{That looks a little bit funny to me}}...

    and that's exactly (-1)^{1+1} as it is given with the formula.

    Greetings

    EB
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by earboth
    Hello,

    F(1)F(3)-(F(2))^2=\underbrace{2-1=2}_\csub{\mbox{That looks a little bit funny to me}}...

    and that's exactly (-1)^{1+1} as it is given with the formula.

    Greetings

    EB
    I guess I never will win the Fields Medal.

    That is why I never get 100 on tests.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    Could someone please add the extra couple of lines for me, I'm a little stuck, Thanks!

    Step 1: For n = 1, we have


    (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1


    Hence the equation holds for n = 1

    Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

    (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}

    Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

    (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}

    So we have:

    (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}
    (F_k \cdot F_{k+2}) - (F_{k+1})^2 + k+1= (-1)^{k+1} + k+1
    Could someone write what goes here please?
    .
    .
    (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}

    Hence the equation holds true for n = k + 1
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum