Find a closed form of the generating function

Question

I need to find the closed form of the generating function $a(z)$ given $(n+1)a_{n+1} = 3a_n + 1$ and $a_0 = 0$.

My attempt:

Using $a_0 = 0$ the first few terms can be found. $a_1 = 1$, $a_2 = 2$, $a_3 = \frac{7}{3}$, $a_4 = 2$. \begin{align*} (n+1)a_{n+1} &= 3a_n + 1\\ \sum_{n\geq0}(n+1)a_{n+1}z^n &= \sum_{n\geq0}3a_nz^n + \sum_{n\geq0}z^n\\ D(a(z)) &= a(z) + \frac{1}{1-z}\\ \end{align*} Here is a differential equation. I used an integrating factor of $e^{-3z}$ which gives a solution of $a(z) = e^{3z}\int e^{-3z}\frac{1}{1-z}dz$. I'm not sure how to integrate this.

It looks to me that this is too complicated as a solution. I'm not sure if i am doing this correctly.

Any help will be appreciated. Thanks.

Answer 1

Welcome to MSE! It seems to me that you've done everything correctly.

Writing $A(z) = \sum a_n z^n$, you successfully turned your recurrence into the differential equation $A' = 3A + \frac{1}{1-z}$, with the initial condition $A(0) = 0$. It turns out that the solution to this differential equation doesn't admit a nice closed form.

Indeed, we can ask sage or wolframalpha to solve it for us, and we get a function in terms of the Exponential Integral $\text{Ei}(z)$. In particular, there is no (elementary) antiderivative for your expression $\int e^{-3z} \frac{1}{1-z}\ dz$, so you shouldn't feel bad about getting stuck!

Sage tells us our solution is

$$A(z) = e^{3(z-1)} \big (\text{Ei}(3) - \text{Ei}(3 - 3z) \big )$$

We can compute a series expansion, though, and sage tells us:

$$ A(z) = 0 + 1z + 2z^2 + \frac{7}{3}z^3 + 2z^4 + \frac{7}{5}z^5 + \frac{13}{15}z^6 + \frac{18}{35}z^7 + \frac{89}{280}z^8 + \frac{547}{2520}z^9 + O(z^{10}) $$

We can easily check that this agrees with the recurrence, so we can be confident that we found the correct solution.

As a quick moral, many problems we encounter are solvable, even if the "closed form" we have to work with involves special functions or a priori "insoluble" integrals. After all, without the $\log$ function, we couldn't integrate $\int \frac{1}{t}\ dt$. You should view these functions as no scarier than the logarithm (though perhaps they're currently less familiar to you). In particular, you should feel free to use them to solve problems!

The other moral (then I'll get off my soapbox, I promise) is that (when in doubt) if you have a concrete problem, you can always ask a computer to do some of the heavy lifting. If you aren't confident in your answer, check if the first $10$ terms of your series agrees with the first $10$ terms of the recurrence! There's absolutely no rules against it, and it's a nice sanity check.

---

I hope this helps ^_^