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

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.
