Solve this recurrence relation : $a_n$ = $a_{n-1}+ n^2 \times 3^n$

Question

Given that $a_1 = 1$, solve this inhomogeous recurrence relation.

Answer 1

Let $A(z) = \sum_{n=1}^\infty a_nz^n$ be generating function of the sequence $\{a_n\}$. Multiplying both sides of the recurrence by $z_n$ and summing over $n=2$ to $\infty$ yields $$ \sum_{n=2}^\infty a_nz^n = \sum_{n=2}^\infty a_{n-1}z^n + \sum_{n=2}^\infty n^2 3^n z^n. $$ After some algebra, we arrive at $$ A(z) - 1 = zA(z) +\frac{9 z^2 (9 (z-1) z+4)}{(1-3z)^3}. $$ Solving for $A(z)$: $$ A(z) = \frac{81 z^4-108 z^3+63 z^2-9 z+1}{(1-z) (1-3z)^3}. $$ Partial fraction decomposition yields $$ A(z) = 3-\frac72\left(\frac1{1-z}\right)+\frac 3{(1-3z)^3}+\frac 6{(1-3z)^2}+\frac 92\left(\frac1{1-3z}\right). $$ Expanding these as series, we have $$ A(z) = 3 - \sum_{n=0}^\infty\frac72 z^n + \sum_{n=0}^\infty \frac{1}{2} (n+1) (n+2)3^{n+1} z^n+ \sum_{n=0}^\infty 2\cdot 3^{n+1}(n+1)z^n + \sum_{n=0}^\infty \frac13 3^{n+2}z^n. $$ Discarding the constant coefficients (since $\{a_n\}$ was defined to start at $n=1$), we have \begin{align} A(z) &= \sum_{n=1}^\infty \frac{1}{2} \left(3^{n+1} n^2-3^{n+1} n+3^{n+1}-7\right)z^n\\ &=\sum_{n=1}^\infty \left(\frac{3^{n+1}}2(n^2-n+1)-\frac72 \right)z^n. \end{align} It follows that $$ a_n = \frac{3^{n+1}}2(n^2-n+1)-\frac72,\quad n\geqslant 1. $$