Thread: Proof by Induction - Recurrence Relation

PROBLEM

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,...

My WORK
- 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)
= k+k+1+1
= 2k + 2

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 .