Generating functions to solve recurrence relation Use generating functions to solve the recurrence relation 
$$ a_{n} = 3a_{n−1} + 2 $$ 
with initial condition $a_{0} = 1$.
If I can bring it to $ a_{n}=k a_{n-1} $ I can solve it easily. Thank you
 A: Here is a start
$$ \sum_{n=0}^{\infty}a_{n+1}x^n = 3 \sum_{n=0}^{\infty} a_{n}x^n + 2\sum_{n=0}^{\infty} x^n. $$
Now, recall this 
$$  \sum_{n=0}^{\infty} x^n =\frac{1}{1-x}.$$
I think you can finish it now. Just follow the technique in this problem.
A: Suppose
$$
\begin{align}
f(x)
&=\sum_{n=0}^\infty a_nx^n\\
&=1+\sum_{n=1}^\infty(3a_{n-1}+2)x^n\\
&=1+x\sum_{n=0}^\infty(3a_n+2)x^n\\
&=1+3xf(x)+\frac{2x}{1-x}\\
(1-3x)f(x)&=\frac{1+x}{1-x}\\
f(x)&=\frac{1+x}{(1-x)(1-3x)}\\
&=\frac2{1-3x}-\frac1{1-x}\\
&=\sum_{n=0}^\infty(2\cdot3^n-1)x^n
\end{align}
$$
Equating coefficients yields
$$
a_n=2\cdot3^n-1
$$
A: $A_n = 2*3^{n} - 1 $.  This should do it
A: Let $h_n=a_n3^{-n}$. What is $h_n-h_{n-1}$? Now telescope. This gives that $$h_{n}-h_0=2\sum_{k=1}^n\frac{1}{3^k}$$

One can look at generating functions, but it proves much more tortuous. In general, a recurrence of the form $$x_{n+1}=ax_n+b$$ can be reduced by $y_n=x_n a^{-n}$ by $$y_{n+1}=y_n+\frac{b}{a^{n+1}}$$ and upon telescoping to $$y_{n+1}-y_0=b\sum_{k=0}^n \frac{1}{a^{k+1}}$$ that is $$x_{n+1}=b\sum_{k=0}^n a^{n-k}+a^{n+1}x_0$$
$$x_{n+1}=b\sum_{k=0}^n a^{k}+a^{n+1}x_0$$
A: You want to solve
$a_{n} = 3a_{n−1} + 2$
and you said that you could do it
if you could bring it to the form
$a_{n} = 3a_{n−1}$.
Here is one way to do that:
Let $a_n = b_n+c$,
where $c$ is a constant to be determined.
We want to choose $c$ so that
$b_n = 3 b_{n-1}$.
Substituting the expression for $a$,
$b_n+c = 3(b_{n-1}+c)+2
= 3 b_{n-1} + 3c+2
$,
or $b_n = 3 b_{n-1}+2c+2$.
To make $b_n = 3 b_{n-1}$,
we need $2c+2 = 0$, so $c = -1$.
Then $b_n = 3 b_{n-1}$,
so $b_n = 3^n b_0$.
Writing $b_n$ in terms of $a_n$,
$a_n-c = 3^n(a_0-c)$
or
$a_n = 3^n a_0 - 3^n c + c
= 3^n a_0-c(3^n-1)
= 3^n a_0 + 3^n - 1
$
(since $c = -1$).
This idea of modifying a recurrence 
so that it becomes easier to solve
is a very general problem solving technique.
It looks like this:


*

*You have a hard problem.

*Convert it to an easier problem.

*Solve the easier problem.

*Convert that solution to a solution of the hard problem.


Think of multiplying by using logs, for example.
In your case,
your problem was converted to
$b_n = 3 b_{n-1}$
and, when the solution to this was found,
the $b$'s were converted back to
the original $a$'s.
