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