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: 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