Help me to solve this recurrence relation for a closed form: $a_n = 3a_{n-1}+2n+4$ and $a_1 = 4$ I've tried my best to solve this recurrence relation into a closed form formula for generality  but I couldn't. So, is there someone to help me to solve this recurrence relation into a closed form solution. Can any one can help me?
$a_n = 3a_{n-1}+2n+4$
$a_1 = 4$
 A: A hint:
The "Master Theorem", as it is called in these circles, tells you that the solution is  of the form
$$a_n=a\cdot 3^n + b\> n+c$$
with coefficients $a$, $b$, $c$ to be determined.
A: Consider the homogeneous recurrence relation $a_n=3a_{n-1}$. The characteristic equation is $x-3=0$ and so $x=3$ is the characteristic root. Thus the general solution is $a_n=a3^n$ where $a$ is a constant. Let $a_n=bn+c$ where $b$ and $c$ are constants. We chose a linear equation because $b_n=2n+4$, so this is a proper guess. Substituting this guess into our original recurrence relation gives us $bn+c=3(b(n-1)+c)+2n+4$ which implies that $bn+c=(3b+2)n+(-3b+3c+4)$. Equating the coefficients of these polynomials we obtain $b=-1$ and $c={-7\over 2}$. Thus the particular solution is $a_n=-n-{7\over 2}$. Combining the general solution and the particular solution we see that $a_n=a3^n-n-{7\over 2}$. Since $a_1=4$ we can use this fact to obtain $a_0=-{2\over 3}$ from the original recurrence relation. From this we can see that $a={17\over 6}$ and it follows that $a_n={17\over 6}3^n-n-{7\over 2}={1\over 2}(17\cdot3^{n-1}-2n-7)$. We can check that $a_n$ satisfies $a_1=4$ and the original recurrence relation, which it does. Thus $a_n={1\over 2}(17\cdot3^{n-1}-2n-7)$.
