# Proof by Induction - Recurrence Relation

• November 12th 2012, 08:41 PM
aprilrocks92
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
• November 12th 2012, 08:59 PM
MarkFL
Re: Proof by Induction - Recurrence Relation
Here's what you should be doing (or something similar)

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

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

Now, state the induction hypothesis $P_k$

$H(k)=k+1$

From the recursive definition, we may state:

$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 $P_k$.