Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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