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: Fib proof by induction

  1. Apr 15, 2010 #1
    1. The problem statement, all variables and given/known data
    Hi may i know how 2 start with this proof by induction of fibonacci .
    For n >= 1
    [tex]
    \sum_{i = 1} ^ n fib^2(n) = fib(n) * fib(n + 1)}
    [/tex]


    2. Relevant equations



    3. The attempt at a solution
    First step - Basic step i sub 1 to the equation.
    Then i get
    fib(1)^2 = fib(1) * fib(2)
    1^2 = 1*1
    1 = 1 (proof)

    Second step i need to sub n - 1 into the equation. But i stuck at this step, anyone can guide me along how to continue ? Maybe can give me some link or tutorial on the induction. Because i still quite blur at how the proof by induction work. I google about the topic, but the examples still too hard for me to understand.
    Thanks in advance.
     
    Last edited: Apr 15, 2010
  2. jcsd
  3. Apr 15, 2010 #2

    Mark44

    Staff: Mentor

    It helps to use a different variable, say k.

    Your next step is to assume that the statement is true for n = k. IOW, assume that the following is true.

    [tex]
    \sum_{i = 1} ^ k fib^2(k) = fib(k) * fib(k + 1)
    [/tex]

    Finally, show that the statement is true for n = k + 1, using the previous assumption (the induction hypothesis).
    [tex]
    \sum_{i = 1} ^{k + 1} fib^2(k + 1) = fib(k + 1) * fib(k + 2)
    [/tex]
     
  4. Apr 15, 2010 #3
    Haha. Thanks for the help, i try to figure out. Do u have any tutorial or simple example link for me to start researching on ? Because i cant find a simple version of induction online. Whenever i do a search, it just return me tons of words.
     
  5. Apr 15, 2010 #4

    Mark44

    Staff: Mentor

    On wikipedia.org search for "mathematical induction"
     
  6. Apr 15, 2010 #5
    Thanks for the help
     
  7. Apr 16, 2010 #6
    Hi, after some thoughts. i not sure whether i got the logic right anot. Please point to me if there any error

    [tex]\sum_{i = 1} ^ n fib^2(n) = fib(n) * fib(n + 1)}[/tex]

    After basic step - which i sub 1 into the equation, mention b4 at the above post
    Then i get
    fib(1)^2 = fib(1) * fib(2)
    1^2 = 1*1
    1 = 1 (proof)

    Induction step
    I use k - 1 instead of k because of my lecturer preference. No error with it right ?
    [tex]\sum_{i = 1} ^{k - 1} fib^2(k - 1) = fib(k - 1) * fib(k)[/tex]

    mine Logic is
    fib(k - 1) x fib(k) + (fib(k) x fib(k - 1) - fib(k - 1) x fib(k)) = fib(k) x fib(k + 1)

    I add the different between fib(k) and fib(k - 1) to fib(k - 1).
    But how i going to extend the above sentence. i can to a fibonacci equation on those k and k + 1. As they are not number. Anyone can give me some lights to continue ?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook