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!

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