1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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?


    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


    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


    User Avatar
    2017 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted