Nonhomogeneous Recurrence Relations 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. 
 A: 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. 
A: You could reduce the problem to an easy differential equation. Consider the exponential generating function
$$y=f(x)=\sum_{n=0}^\infty\frac{h_nx^n}{n!}.$$
The derivative is
$$y'=\sum_{n=1}^\infty\frac{nh_nx^{n-1}}{n!}=\sum_{n=1}^\infty\frac{h_nx^{n-1}}{(n-1)!}=\sum_{n=0}^\infty\frac{h_{n+1}x^n}{n!},$$
so the recurrence
$$h_{n+1}=3h_n-2$$
turns into the first-order linear differential equation
$$y'=3y-2e^x$$
and the initial value $h_o=1$ becomes $y(0)=1$. The solution of this initial value problem is
$$y=e^x=\sum_{n=0}^\infty\frac{1x^n}{n!}$$
so $h_n=1$.
A: 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$.
A: For yet another approach, we can use generating functions. Let
$$H(s) = \sum_{n=0}^\infty h_ns^n. $$
Multiplying both sides of the recurrence by $s^n$ and summing for $n\geqslant 1$, the LHS is
$$\sum_{n=1}^\infty h_ns_n = H(s) - 1 $$
and the RHS is
$$\sum_{n=1}^\infty (3h_{n-1}-2)h^n = 3s\sum_{n=0}^\infty h_ns^n - 2s\sum_{n=0}^\infty s^n = 3sH(s) - \frac{2s}{1-s}. $$
Hence 
$$H(s)-1 = 3sH(s) - \frac{2s}{1-s} $$
and
$$H(s)(1-3s) = 1 - \frac{2s}{1-s} = \frac{1-3s}{1-s}. $$
Dividing by $1-3s$ we see that
$$H(s) = \frac1{1-s}=\sum_{n=0}^\infty s^n, $$
so that $h_n=1$ for all $n$.
