Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by induction

  1. Mar 22, 2005 #1
    The following question has been giving me problems because I'm stuck trying to find what the base cases would be.

    Let m be a given positive integer with m>=2(So m remains constant throughout the problem) Let fn be the sequence of fibonacci numbers. Prove that for every integer n>=1, fm+n=(fm * fn+1) + (fm-1 * fn).

    I'm not sure how I go about finding the base cases to start the proof. I know I'm suppose to set something equal to >=1 but I'm not sure what.
  2. jcsd
  3. Mar 22, 2005 #2
    If you want to do induction on n, the base case involve setting n = 1 and proving that f(m + 1) = f(m) * f(2) + f(m - 1) * f(1) (for m >= 2). That statement is obviously true (see the definition of the Fibonacci sequence).

    I think this problem requires strong induction too, btw.
    Last edited: Mar 22, 2005
  4. Mar 22, 2005 #3
    But my teacher has told us that in this specific problem there are more than one base case needed.
  5. Mar 22, 2005 #4
    For induction you need two bases. Do it for n=1 and n=2 , and from there you should be able to state that induction proves the idea.
  6. Mar 22, 2005 #5
    I think this problem requires a sort of nested induction and that's what your teacher was hinting at.
    First you have to prove the fn statement for m=2 (using induction),
    then you have to prove the m+1 case of the fn statement (using induction again).
  7. Mar 22, 2005 #6
    But where did you come up with the base cases needing to be n=1 and n=2. My teacher tried to explain a mathematical way of figuring out the base cases to use but I couldn't follow it.
  8. Mar 22, 2005 #7
    The basic principle of induction is:
    If a function is true for a base 'n' and true for the base 'n+1' , then it will be true for all n.

    So if you can prove that your idea is true for a number 'n', and a number 'n+1' then you have proven that it will be true for any number larger than n. Conventionally you start at n=0 or n=1, it follows from the laws of continuity that induction holds.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook