1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving a properties of fibonacci numbers

  1. May 10, 2013 #1
    Let p[n] be the following property of Fibonacci numbers:
    p[n]: f[itex]_{n+1}[/itex] * f[itex]_{n-1}[/itex] - (f[itex]_{n}[/itex])[itex]^{2}[/itex] = (-1)[itex]^{n}[/itex]. Prove p[n] by induction.

    This is the proof I wrote. i used regular induction. Is weak induction sufficient to prove it or do I need to prove this by strong induction?

    proof:

    BASE STEP: p[1]: f[itex]_{2}[/itex] * f[itex]_{0}[/itex] - (f[itex]_{1}[/itex])[itex]^{2}[/itex] = (1 * 0) - 1 = -1

    and (-1)[itex]^{1}[/itex] = -1

    INDUCTIVE STEP:

    assume P[k]: f[itex]_{k+1}[/itex] * f[itex]_{k-1}[/itex] - (f[itex]_{k}[/itex])[itex]^{2}[/itex] = (-1)[itex]^{k}[/itex]

    show p[k+1]: f[itex]_{k+2}[/itex] * f[itex]_{k}[/itex] - (f[itex]_{k+1}[/itex])[itex]^{2}[/itex] = (-1)[itex]^{k+1}[/itex]






    We know f[itex]_{k+2}[/itex] = f[itex]_{k+1}[/itex] + f[itex]_{k}[/itex]

    p[K+1]: f[itex]_{k+2}[/itex] * f[itex]_{k}[/itex] - (f[itex]_{k+1}[/itex])[itex]^{2}[/itex] = (-1)[itex]^{k+1}[/itex]

    substitute f[itex]_{k+2}[/itex] = f[itex]_{k+1}[/itex] + f[itex]_{k}[/itex] into p[k+1]

    p[k+1]: (f[itex]_{k+1}[/itex] + f[itex]_{k}[/itex]) * f[itex]_{k}[/itex] - (f[itex]_{k+1}[/itex])[itex]^{2}[/itex] = (-1)[itex]^{k+1}[/itex]

    = f[itex]_{k}[/itex] * f[itex]_{k+1}[/itex] + (f[itex]_{k}[/itex])[itex]^{2}[/itex] - (f[itex]_{k+1}[/itex])[itex]^{2}[/itex]

    We know p[k]: f[itex]_{k+1}[/itex] * f[itex]_{k-1}[/itex] - (f[itex]_{k}[/itex])[itex]^{2}[/itex] = (-1)[itex]^{k}[/itex]

    We can rewrite p[k] as: (f[itex]_{k}[/itex])[itex]^{2}[/itex] = f[itex]_{k+1}[/itex] * f[itex]_{k-1}[/itex] - (-1)[itex]^{k}[/itex]

    We substitue (f[itex]_{k}[/itex])[itex]^{2}[/itex] from p[k] into the (f[itex]_{k}[/itex])[itex]^{2}[/itex] in p[k+1]


    = f[itex]_{k+1}[/itex] + f[itex]_{k}[/itex] + f[itex]_{k+1}[/itex] * f[itex]_{k-1}[/itex] - (-1)[itex]^{k}[/itex] - f[itex]_{k+1}[/itex][itex]^{2}[/itex])

    = f[itex]_{k+1}[/itex] (f[itex]_{k+1}[/itex] + f[itex]_{k}[/itex]) (-1)[itex]^{k}[/itex] - f[itex]_{k+1}[/itex][itex]^{2}[/itex])

    = (f[itex]_{k+1}[/itex])[itex]^{2}[/itex]) - (-1)[itex]^{k}[/itex] - (f[itex]_{k+1}[/itex])[itex]^{2}[/itex])

    = - ((-1)[itex]^{k}[/itex])

    = (-1)[itex]^{k+1}[/itex]


    Does this proof strong enough or would I have to do this by strong induction? If by strong induction, how do I got about proving it?
     
  2. jcsd
  3. May 10, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Every valid proof with weak induction is a valid proof with strong induction, too (and this is the first time I saw specific words for them). Your proof uses valid steps only, therefore it is valid. There is no need to do more.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving a properties of fibonacci numbers
  1. Fibonacci Numbers (Replies: 0)

  2. Fibonacci numbers (Replies: 1)

Loading...