Proof by Induction - Recurrence Relation
Define a recurrence relation H(n) by the rules
H(0) = 1, H(1)=1, H(2) = 3, and
H(n) = H(n-1) + H(n-3) -H(n-2) + 2 for n >= 3.
Prove by induction that H(n) = n+1 for all n = 0,1,2,...
- Base case:
P(0) asserts that 0+1 = 1. This is true, and thus the base case is completed.
- Inductive step:
Assume P(k): 1+2+...+k = k+1
P(k) is therefore our inductive hypothesis.
Now, we must prove that if P(k) holds, then P(k+1) must also hold. Hence, we add (k+1) on both sides of the equality.
/* This is where I get lost. Any help is much appreciated */
1+2+...+k+(k+1) = [1+2+...+k]+1 + (k+1)
= (k+1) + (k+1)
= 2k + 2
Re: Proof by Induction - Recurrence Relation
Here's what you should be doing (or something similar)
The base case is given, since .
I think you mean to give in your definition.
Now, state the induction hypothesis
From the recursive definition, we may state:
Now, how can you rewrite the right side using the induction hypothesis? Once you do this, then add it to .