Exponential generating function to find recurrence formula $a_n$

Question

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?

Answer 1

It's easier if you divide through by $n+1$ and consider the exponential generating function of $a_n/(n+1)!$ to get

\begin{align}f(x)&=\sum_{n=0}^\infty\frac{a_n}{(n+1)n!}x^n=\sum_{n=0}^\infty\frac{a_n}{(n+1)!}x^n\\&=\sum_{n=0}^\infty\frac{a_{n-1}}{n!}x^n+\sum_{n=0}^\infty\frac1{(n+1)n!}(3x)^n\\&=a_{-1}+\sum_{n=0}^\infty\frac{a_n}{(n+1)!}x^{n+1}+\sum_{n=0}^\infty\frac{(3x)^n}{(n+1)!}\\&=a_{-1}+xf(x)+\frac1{3x}\sum_{n=1}^\infty\frac{(3x)^n}{n!}\\&=a_{-1}+xf(x)+\frac{\exp(3x)-1}{3x}\\{}\\f(x)&=\frac{a_{-1}+(\exp(3x)-1)/(3x)}{1-x}\end{align}

Answer 2

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 ).$$