6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I see no issue in your solution. So, without using any special functions, the integral representation you have gotten is the best we can hope for. $\endgroup$ Oct 7, 2021 at 4:24

1 Answer 1

4
$\begingroup$

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 ^_^

$\endgroup$
2
  • $\begingroup$ Thank you. That helps a lot $\endgroup$
    – Moz
    Oct 10, 2021 at 10:30
  • $\begingroup$ Happy to help ^_^. If this answered your question, you should mark it as such so that other users know how to spend their time. $\endgroup$ Oct 10, 2021 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.