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 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 very elementary approach that does not require generating functions or knowledge of the general form of the solution is to ‘unwrap’ the recurrence. (Note that this is feasible only with first-order recurrences.) If we set $a_0=-\frac23$, the recurrence yields the correct value of $a_1$; doing this makes the subsequent calculations a little simpler, so I will.
$$\begin{align*} a_n&=3a_{n-1}+2n+4\\ &=3\big(3a_{n-2}+2(n-1)+4\big)+2n+4\\ &=3^2a_{n-2}+3\cdot2(n-1)+2n+4(3+1)\\ &=3^2\big(3a_{n-3}+2(n-2)+4\big)+3\cdot2(n-1)+2n+4(3+1)\\ &=3^3a_{n-3}+3^2\cdot2(n-2)+3\cdot2(n-1)+2n+4(3^2+3+1)\\ &\;\vdots\\ &=3^ka_{n-k}+\sum_{i=0}^{k-1}3^i\cdot2(n-i)+4\sum_{i=0}^{k-1}3^i\tag{1}\\ &\;\vdots\\ &=3^na_0+2\sum_{i=0}^{n-1}3^i(n-i)+4\sum_{i=0}^{n-1}3^i\\ &=-2\cdot 3^{n-1}+(2n+4)\sum_{i=0}^{n-1}3^i-2\sum_{i=0}^{n-1}3^ii\\ &=-2\cdot 3^{n-1}+(2n+4)\frac{3^n-1}{3-1}-2\sum_{i=1}^{n-1}3^ii\tag{2}\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-2\sum_{i=1}^{n-1}3^i\sum_{j=1}^i1\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-2\sum_{i=1}^{n-1}\sum_{j=1}^i3^i\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-2\sum_{j=1}^{n-1}\sum_{i=j}^{n-1}3^i\tag{3}\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-2\sum_{j=1}^{n-1}\frac{3^n-3^j}{3-1}\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-\sum_{j=1}^{n-1}\left(3^n-3^j\right)\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-\sum_{j=1}^{n-1}3^n+\sum_{j=1}^{n-1}3^j\\ &=-2\cdot 3^{n-1}+(n+2)(3^n-1)-(n-1)3^n+\frac{3^n-3}{3-1}\\ &=-2\cdot 3^{n-1}+3\cdot3^n-n-2+\frac12\cdot 3^n-\frac32\\ &=\frac{17}6\cdot3^n-n-\frac72\\ &=\frac{17}2\cdot3^{n-1}-n-\frac72\\ &=\frac12\left(17\cdot3^{n-1}-2n-7\right)\;. \end{align*}$$
Step $(1)$ is the point at which I decided that I’d seen enough to recognize the pattern. The long-winded calculation after $(2)$ can be avoided if you already know a closed form for sums of the form $\sum_{k=1}^mka^k$; there is an easy way using a little calculus to derive such a closed form from the closed form for the sum of a finite geometric series. I chose to take an alternative approach that uses no calculus but does require that you be able to reverse the order of summation in a double summation, as I’ve done at $(3)$.
The step at $(1)$ is a non-rigorous bit of pattern-spotting, so properly speaking the final result, $$a_n=\frac12\left(17\cdot3^{n-1}-2n-7\right)\;,$$ is just a conjecture at this point, albeit a very solid one, and one should conclude by proving that it’s correct. This entails verifying that it yields the correct value of $a_1$ and satisfies the recurrence used to define the sequence.
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)$.
