Finding an explicit formula for the following exponential generating function

Question

So I have the following formula for the coefficient of the recursion and I am trying to find an explicit formula for $a_n$ the nth coefficient:

$$ a_n = (n+1)a_{n-1} + 3^n $$ $$ a_0 = 1; \space\space\space n\geq1 $$

Here's what I have done so far (I may be incorrect in some intermediate steps, I am not sure):

expand the $(n+1)$ term so that we have $ a_n = na_{n-1} + a_{n-1}+ 3^n $, multiply all sides by $ \frac{x^n}{n!}$ and sum over $ n $ giving the following:

$$\sum_{n \geq1}{a_n\frac{x^n}{n!}} = \sum_{n \geq1}n a_{n-1}\frac{x^n}{n!} + \sum_{n \geq1} a_{n-1}\frac{x^n}{n!} + \sum_{n \geq1}3^n\frac{x^n}{n!} $$

Let's call the exponential generating function $\sum_{n \geq0}{a_n\frac{x^n}{n!}} = G(X)$ $$ \therefore G(x) = xG(x) + xe^x + 3^ne^x - 3^n +1 $$

and this simplifies to: $$ G(x) = \frac{x}{1-x}e^x + \frac{3^n}{1-x}e^x + \frac{3^n}{1-x} + \frac{1}{1-x}$$

I am quite stuck here, for the first term on the RHS I have: $\sum_{i = 0}^{n-1} \frac{n!}{i!}$ for the second term I have $3^n\sum_{i = 0}^{n-1} \frac{n!}{i!} $ for the third term I have $3^n \sum_{n\geq0} x^n$ and for the final term I have $\sum_{n\geq0} x^n$ (so taking the coefficients of the x terms we get:

$$a_n = \sum_{i = 0}^{n-1} \frac{n!}{i!} + 3^n\sum_{i = 0}^{n-1} \frac{n!}{i!} + 3^n + 1$$

which gives the wrong answer... can anyone help me out see where I went wrong?

Thank you!

edit: I realize there is a post asking the same question which uses integration/differentiation; I am trying to do this without the use of calculus.

Answer 1

You've got the limits wrong. That's why I always insist in no subtraction in indices.

Write:

$\begin{align*} a_{n + 1} &= (n + 2) a_n + 3 \cdot 3^n \\ \sum_{n \ge 0} a_{n + 1} \frac{z^n}{n!} &= \sum_{n \ge 0} (n + 2) a_n \frac{z^n}{n!} + 3 \sum_{n \ge 0} 3^n \cdot \frac{z}{n!} \\ &= z \sum_{n \ge 1} a_n \frac{z^{n - 1}}{(n - 1)!} + 2 \sum_{n \ge 0} a_n \frac{z^n}{n!} + 3 e^{3 z} \\ G'(z) &= z G'(z) + 2 G(z) + 3 e^{3 z} \end{align*}$

From the initial value $a_0 = 1$ you get the initial value $G(0) = 1$. The solution is:

$\begin{align*} G(z) &= \frac{(3 z - 6) e^z + 5}{(1 - z)^2} \end{align*}$

The fun of extracting coefficients I leave to the gentle reader.