Proof by induction

  • Thread starter mathrocks
  • Start date
  • #1
106
0
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.
 

Answers and Replies

  • #2
695
0
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:
  • #3
106
0
Muzza said:
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.

But my teacher has told us that in this specific problem there are more than one base case needed.
 
  • #4
2,209
1
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.
 
  • #5
53
0
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).
 
  • #6
106
0
whozum said:
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.

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.
 
  • #7
2,209
1
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.
 

Related Threads on Proof by induction

  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
8
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
4
Views
3K
Replies
2
Views
7K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
3K
Replies
4
Views
2K
Top