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.

  • $\begingroup$ For $n=0$, the answer given by the notes is $0$, but you it's defined as $1$. $\endgroup$ – Davide Giraudo Apr 12 '12 at 18:26
  • 2
    $\begingroup$ Your second approach will work, it's just incomplete. There is a nice closed form for $z + 2z^2 + 3z^3 + ...$. $\endgroup$ – Qiaochu Yuan Apr 12 '12 at 18:27
  • $\begingroup$ @Davide Giraudo: It's strange, probably typos from my teacher. Thanks for pointing that out. $\endgroup$ – Chan Apr 12 '12 at 18:31
  • $\begingroup$ For 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 go.helms-net.de/math/divers/mse/MSE120412.pdf $\endgroup$ – Gottfried Helms Apr 13 '12 at 12:45

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.


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.