Nonhomogeneous Recurrence Relations

Question

Solve the nonhomogeneous recurrence relation

$$h_{n}=3h_{n-1}-2$$
$$n\geq 1$$ $$h_{0}=1$$

I have been told to approach this type of problem using two steps. First, solve the corresponding homogeneous relation and then find one particular solution.

1) corresponding homogeneous relation $$h_{n}=3h_{n-1}$$
x-2=0 x=2 $$h_{n}=c2^{n}$$

2)find a particular case This is where I'm struggling- How do I find this particular case- I'm assuming I need to use my initial value in this step.

Answer 1

Here is an approach. We have

$$ h_{n}=3h_{n-1}-2 $$ $$ h_{n+1}=3h_{n}-2. $$

The later eq. follows from the first by shifting the index. Subtracting the two equations gives the homogeneous recurrence relation

$$ h_{n+1}-4h_n+3h_{n-1}=0. $$

Now, I think you can solve the later equation. In case you want to go the other way by finding a particular solution, see here.

Answer 2

Consider the homogeneous recurrence relation $h_n-3h_{n-1}=0$. The characteristic polynomial is $x-3=0$, so $x=3$ is our characteristic root. The homogeneous solution is $h_{n_1}=a3^n$ where $a$ is a constant. Now, for our particular solution we make the guess $h_{n_2}=b$ where $b$ is a constant. We chose a constant because our recurrence relation has the constant term $-2$, so the proper guess is a constant. Substituting our guess we see that $b=3b-2$, and this gives us $b=1$. So the particular solution is $h_{n_2}=1$. Combining our homogeneous solution and our particular solution we see that $h_n=h_{n_1}+h_{n_2}=a3^n+1$. Since we are given that $h_0=1$ we can use this to find $a=0$. Thus $h_n=1$ is the solution to the recurrence relation and we can check this by substituting $h_n=1$ into the recurrence relation.

This problem may seem strange. However, $h_n=1$ is the solution. If you wanted you could find multiple values of $h_n$ for $n=1,2,3,...$. That is $h_0=1$, $h_1=1$, $h_2=1$,.... It looks as if $h_n=1$ is the solution, but we must prove this. So we proceed with Mathematical Induction. Assume that $h_k=1$ for some arbitrary positive integer $k$. We must prove that $h_{k+1}=3h_k-2=1$. Consider $3h_k-2$, by our induction hypothesis $h_k=1$. So $3(1)-2=1$ and so $h_{k+1}=3h_k-2=1$. Thus by the Principle of Mathematical Induction $h_n=3h_{n-1}-2=1$ for all $n\geq0$.