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

Re: Proof by Induction - Recurrence Relation

Here's what you should be doing (or something similar)

The base case $\displaystyle P_0$ is given, since $\displaystyle H(0)=0+1=1$.

I think you mean to give $\displaystyle H(1)=2$ in your definition.

Now, state the induction hypothesis $\displaystyle P_k$

$\displaystyle H(k)=k+1$

From the recursive definition, we may state:

$\displaystyle H(k+1)-H(k)=H(k-2)-K(k-1)+2$

Now, how can you rewrite the right side using the induction hypothesis? Once you do this, then add it to $\displaystyle P_k$.