<s>[INST] Exponential generating function to find recurrence formula $a_n$ Given $a_0 = 1$ and $a_n = (n + 1)a_{n - 1} + 3^n$ for $n \geq 1$, find formula for $a_n$. 
First remind the definition of power series $F(x) = \sum_{n \geq 0}f_n \frac{x^n}{n!}$
and exponential generating function $G(x) = \sum_{n \geq 0}\frac{x^n}{n!} = e^x$ 
Note we have to use exponential generating function to solve this question. So let $f(x) = \sum_{n \geq 0}a_n\frac{x^n}{n!}$, multiplying both sides of  $a_n = (n + 1)a_{n - 1} + 3^n$ by $\frac{x^n}{n!}$ and sum over all $n \geq 1$. We get, $$\sum_{n \geq 1}a_n\frac{x^n}{n!} = \sum_{n \geq 1}(n + 1)a_{n - 1}\frac{x^n}{n!} + \sum_{n \geq 1}3^n\frac{x^n}{n!}$$
$$\sum_{n \geq 1}a_n\frac{x^n}{n!} = \sum_{n \geq 1}na_{n - 1}\frac{x^n}{n!} + \sum_{n \geq 1}a_{n - 1}\frac{x^n}{n!} + \sum_{n \geq 0}\frac{(3x)^{n}}{n!} - 1$$
$$\underbrace{\sum_{n \geq 0}a_n\frac{x^n}{n!}}_{f(x)} - 1 = x\underbrace{\sum_{n \geq 1}a_{n - 1}\frac{x^{n-1}}{(n-1)!}}_{f(x)} + \underbrace{\sum_{n \geq 1}a_{n - 1}\frac{x^{n}}{(n)!}}_{\int{f(x)} = F(x) + C} + e^{3x} - 1$$
$$F'(x) - 1 = xF'(x) + F(x) + e^{3x} - 1   + C$$
$$F'(x)(1 - x) - F(x) = e^{3x} + C$$
I think I'm essentially stuck here, I'm trying my best to manipulate each term so that we can express each term in terms of $f(x)$. But I can't go further from here because it doesn't like look this form can lead us to the solution. 
Any feedback or suggestion? 
 [/INST] Given:
$$a_{n+1} = (n+2) \, a_{n} + 3^{n+1} \quad \text{with} \quad a_{0}=1$$
and
$$f(t) = \sum_{n=0}^{\infty} a_{n} \, \frac{t^n}{n!}$$
then the exponential generating functions is obtained as follows.
\begin{align}
\sum_{n=0}^{\infty} a_{n+1} \, \frac{t^n}{n!} &= \sum_{n=0}^{\infty} (n+2) \, a_{n} \, \frac{t^n}{n!} + 3 \, \sum_{n=0}^{\infty} \frac{(3 t)^n}{n!} \\
\sum_{n=0}^{\infty} (n+1) \, a_{n+1} \, \frac{t^n}{(n+1)!} &= \sum_{n=0}^{\infty} (n+1) \, a_{n} \, \frac{t^n}{n!} + f(t) + 3 \, e^{3 t} \\
\frac{d}{dt} \, \sum_{n=1}^{\infty} a_{n} \, \frac{t^n}{n!} &= \frac{d}{dt} \, \sum_{n=0}^{\infty} a_{n} \, \frac{t^{n+1}}{n!} + f(t) + 3 \, e^{3 t} \\
\frac{d}{dt} (f(t) - 1) &= \frac{d}{dt} \, (t \, f(t)) + f(t) + 3 \, e^{3 t} \\ 
(1 - t) \, f' - 2 \, f &= 3 \, e^{3 t} \\
(1 - t)^2 \, f' - 2 \, (1-t) \, f &= 3 \, (1-t) \, e^{3 t} \\
\frac{d}{dt} \, ( (1-t)^2 \, f) &= 3 \, (1-t) \, e^{3 t} \\
(1-t)^2 \, f(t) &= 3 \, \int (1-u) \, e^{3 u} \, du + c_{1}    
\end{align}
or 
$$f(t) = \frac{1}{(1-t)^2} \, \left( 3 \, \int (1-u) \, e^{3 u} \, du + c_{1} \right).$$
This leads to
$$f(t) = \frac{c_{0} + (4 - 3 t) \, e^{3 t}}{3 \, (1-t)^2}$$
and using $f(0) = 1$ yields
$$f(t) = \frac{(4 - 3 t) \, e^{3 t} - 1}{3 \, (1-t)^2}.$$
Edit
Coefficients and/or solution:
The first few terms of $a_{n}$ are $a_{n} \in \{ 1, 5, 24, 123, 696, \cdots \}_{n \geq 0}$ and, with some work, lead to the form
$$ a_{n} = \frac{(n+1)!}{3} \, \sum_{k=1}^{n+1} \frac{3^k}{k!}$$
or 
$$ a_{n} = \frac{(n+1)!}{3} \, ( e_{n+1}(3) - 1 ),$$
where the finite exponential function is defined by
$$ e_{n}(x) = \sum_{k=0}^{n} \frac{x^k}{k!}.$$
In general the difference equation
$$ a_{n+1} = (n+2) \, a_{n} + b^{n+1} \quad a_{0} = 1$$
has the solution
$$ a_{n} = \frac{(n+1)!}{b} \, ( e_{n+1}(b) - 1 ).$$
</s>