Given the recurrence, $ a_n = \begin{cases} 1, & n = 0 \\ a_{n-1} + 2a_{n-2} + 3a_{n-3} + \ldots + (n - 1)a_1 + na_0, & n \geq 1 \end{cases} $ My attempt was, rewrite $a_n$ as: $a_n = \displaystyle{\sum_{i=0}^na_i}(n - i) \Leftrightarrow \displaystyle{\sum_{n=0}^{\infty}a_nz^n} = \displaystyle{\sum_{n=0}^{\infty}\bigg(\displaystyle{\sum_{i=0}^na_i(n - i)\bigg)}}z^n + 1$ then I tried to compare it with one of my generating function formulas: $\dfrac{G(z)}{1 -z} = \displaystyle{\sum_{n=0}^{\infty}\bigg(\displaystyle{\sum_{i=0}^na_i\bigg)}}z^n$ They're very similar except for the coefficient $n - i$ and the $1$. The answer given in the note was: $a_n = \dfrac{-1}{\sqrt{5}}\bigg(\dfrac{2}{3 + \sqrt{5}}\bigg)^n + \dfrac{1}{\sqrt{5}}\bigg(\dfrac{2}{3 - \sqrt{5}}\bigg)^n$ but I had no idea how did they get to that expression? I also tried to consider $G(z) - zG(z) - 2z^2G(z) - 3z^3G(z) - 4z^4G(z) - \ldots = 1$ but this approach leads to: $G(z) = \dfrac{1}{1 - z - 2z^2 - 3z^3 - \ldots }$ which is impossible to factor out the denominator. I guess there must be a clever trick to pull out the $n - i$ term but somehow I couldn't see it. I wonder could anyone give me a hint how to solve this problem? Thanks.
How to find generating function of cumulative sum?
-
0For my own exercise I've just made an attempt using a matrix-notation to show the most elementary operations which are required. Perhaps you like it; it can be found at http://go.helms-net.de/math/divers/mse/MSE120412.pdf – 2012-04-13
2 Answers
As Qiaochu notes, your second approach works but is incomplete. Consider what the derivative of the usual geometric series looks like - can this be massaged into the form you have at hand?
More generally, if $(a)_n=a(a-1)\cdots\big(a-(n-1)\big)$, we can observe the following:
$\frac{d^{\,k}}{dx^k} x^n = (n)_k x^{n-k} \quad\implies\quad \sum_{n=0}^\infty a_n (n)_k x^n =x^k\frac{d^{\,k}}{dx^k}\left(\sum_{n=0}^\infty a_nx^n\right).$
Notice that $\{(n)_1,(n)_2,\cdots\}$ forms a basis for the vector space of integer coefficient polynomials, so we can use the above formula to evaluate, for any rational coefficient polynomial $P$,
$A(x)=\sum_{n=0}^\infty a_n P(n) x^n \quad \mathrm{in~terms~of} \quad B(x)=\sum_{n=0}^\infty a_nx^n.$
Going the other direction frequently involves differential equations. As an example, using the above ideas and your formula for $G(z)/(1-z)$ we can evaluate equation (2) in your question to
$G(z)=z\frac{d}{dz}\left(\frac{G(z)}{1-z}\right)-\frac{1}{1-z}\left(z\frac{d}{dz} G(z)\right)+1.$
See if you can prove $a_n=3a_{n-2}-a_{n-4}$. I assume that once you get it to that form, you have methods to solve it.