Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Exercise: For $n \geq 0$ let $a_n = \sum \limits_{i=0}^n (i^2- 2i + 1)$

a) Show that $$a_{n+4} -4a_{n+3} + 6a_{n+2} - 4a_{n+1} + a_n = 0, n \geq 0$$

b) Identify the genereating series $\sum \limits_{n\geq 0} a_n x^n$.

c) Identify a polynomial $p(n)$ in $n$ so $p(n) = a_n$.


I still don't understand how to get on this series exercises and don't have any idea at all how to solve this.

Could you please help me and show me what to do to solve them - and if possible in a way even a math-moron like me can understand it?

Thank you in advance!

share|cite|improve this question
What is "g" doing in the recurrence relation? – Beni Bogosel Jun 13 '11 at 13:21
What is the $g$? – Olivier Bégassat Jun 13 '11 at 13:23
$$g = 6?$$ ${}$ – jspecter Jun 13 '11 at 13:26
@Beni-Gogosel @olivier-begassat Sorry, it should be a "6", I just corrected it. I ran out of coffee and must have missed it... – muffel Jun 13 '11 at 18:15
up vote 4 down vote accepted

"Identify the generating series" usually means show the generating function is equal to some simpler expression, where "simpler" means not involving any infinite processes (like infinite sums).

Here's one way to do it.

First, give the series a name: I'll let $f(x)=\sum_{n=0}^{\infty} a_nx^n=a_0+a_1x+a_2x^2+\dots$.

Now, part a) involves $a_{n+1}$, $a_{n+2}$, etc., so let's look at $\sum_{n=0}^{\infty}a_{n+1}x^n=a_1+a_2x+a_3x^2+\dots$. You get this series from the one for $f$ by subtracting $a_0$ and dividing by $x$, so $\sum_{n=0}^{\infty}a_{n+1}x^n=x^{-1}(f-a_0)=x^{-1}f-a_0x^{-1}$.

Similarly, $\sum a_{n+2}x^n=x^{-2}f-a_1x^{-1}-a_0x^{-2}$, $\sum a_{n+3}x^n=x^{-3}f-a_2x^{-1}-a_1x^{-2}-a_0x^{-3}$, and $\sum a_{n+4}x^n=x^{-4}f-a_3x^{-1}-a_2x^{-2}-a_1x^{-3}-a_0x^{-4}$

Now the recirrence relation you got in part a) shows that $$\eqalign{&\sum a_{n+4}x^n-4\sum a_{n+3}x^n+6\sum a_{n+2}x^n-4\sum a_{n+1}x^n+\sum a_nx^n\cr&\qquad=\sum(a_{n+4}-4a_{n+3}+6a_{n+2}-4a_{n+1}+a_n)x^n=0\cr}$$

Now use the expressions we got for all those other sumsto turn this into an equation for $f(x)$.

share|cite|improve this answer
Myerson I tried to go on, but don't see any possibility to sum them up: $$\begin{eqnarray*} 0&=& \sum a_{n+4}x^n-4\sum a_{n+3}x^n+6\sum a_{n+2}x^n-4\sum a_{n+1}x^n+\sum a_nx^n\cr&\qquad \\ & =& x^{-4}f-a_3x^{-1}-a_2x^{-2}-a_1x^{-3}-a_0x^{-4} - 4(x^{-3}f-a_2x^{-1}-a_1x^{-2}-a_0x^{-3}) + 6(x^{-2}f-a_1x^{-1}-a_0x^{-2}) \\ && -4(x^{-1}f-a_0x^{-1}) + f \\ & =& x^{-4}f-a_3x^{-1}-a_2x^{-2}-a_1x^{-3}-a_0x^{-4} -4 x^{-3}f + 4 a_2x^{-1} +4 a_1 x^{-2} +4 a_0 x^{-3} \\ && + 6 x^{-2} f -6 a_1 x^{-1} -6 a_0 x^{-2} -4 x^{-1} f +4 a_0 x^{-1} +f \\ &=& ? \end{eqnarray*}$$ Any further hint? Thanks – muffel Jun 14 '11 at 18:59
@muffel, solve for $f$. – Gerry Myerson Jun 15 '11 at 0:44
Myerson Thank you, that worked. Now the last part - how do I transform $f = \frac{a_0 - 4x^3 + 6 x^2 - 4x + 1) + x(a_1(6x^2 -4x + 1) + x (-4a_2 x + a_2 + a_3 x))}{(x-1)^4}$ into a polynomial? – muffel Jun 15 '11 at 6:50
@muffel, who said anything about transforming $f$ into a polynomial? The problem says $a_n$ should be a polynomial. So: calculate $a_0,\dots,a_3$ so you have $f=p(x)/(1-x)^4$ for some polynomial $p$. Expand $(1-x)^{-4}$ by the binomial theorem. Multiply by $p(x)$ and you should find the coefficient of $x^n$ is a polynomial in $n$. If all else fails, ask your teacher, who is paid to answer your questions. – Gerry Myerson Jun 15 '11 at 13:20
@Gerry-Myseron ok, I then just followed the wrong approach. That finally does the trick! Thanks a lot! – muffel Jun 19 '11 at 20:54

Hint: Notice that

$$a_n=\sum_{i=0}^n(i^2-2i+ 1)=\sum_{i=0}^n(i-1)^2=\sum_{i=-1}^{n-1}i^2$$

share|cite|improve this answer
Thank you, that helped me solving a)! Do you have any further hints for b) and c)? – muffel Jun 13 '11 at 18:35
@muffel For b) and c) recall that $\sum_{i=0}^ni^2=n(n+1)(2n+1)/6$. – FUZxxl Jun 13 '11 at 19:40

For part (a), you do not even need to be aware of the simplification mentioned by FUZxxl: you can take a purely mechanical approach.

Note first of all (this is kind of a joke, but not quite) that


Now to get $a_{n+1}$, we take the sum up to $i=n$, then add the next term, which is $(n=1)^2-2(n+1)+1$. It is convenient, just to save space, to notice that $j^2-2j+1=(j-1)^2$, so to get to $a_{n+1}$, we added $n^2$ to $a_n$. Thus $$a_{n+1}=a_n+ n^2$$

Similarly, to get $a_{n+2}$, we add $(n+1)^2$ to $a_{n+1}$. Thus $$a_{n+2}=a_{n+1}+ (n+1)^2=a_n+n^2+(n+1)^2$$

The same sort of reasoning shows that $$a_{n+3}=a_n+n^2+(n+1)^2+(n+2)^2$$ and that $$a_{n+4}=a_n+n^2+(n+1)^2+(n+2)^2+(n+3)^2$$

Now "plug in" the values we found into the expression $$a_{n+4}-4a_{n+3}+6a_{n+2}-4a_{n+1}+a_n$$

Simplify, using algebra. If you do the simplification cleverly, it will not even be a lot of work.

After some manipulation, you will get $0$. All this work for nothing (feeble pun).

The point I am making is that once you get a grasp of what $a_k$ actually means, the verification of the desired identity is purely mechanical.

Naturally there are better (or at least slicker) ways of doing the job. However, for such slicker ways one needs somewhat more theoretical background, which at this stage you may not yet have. Maybe you almost do. If you are beginning to be comfortable with generating functions ("series"), you can look for a generating function argument.

I will assume that you can do the other parts. If difficulties remain, please leave a comment, and I or others may be able to help.

share|cite|improve this answer
Thank you for your solution as well! I don't start getting comfortable with generation functions as I neither have found any good books nor understand what they are really good for. Referred to Wikipedia they "encode" information about a sequence, but how exactly? I haven't found any good example (yet) that covers them from the very beginning. So regarding the exercises I need to understand most times I don't event know what I should prove (not to mention how to do prove it). – muffel Jun 13 '11 at 18:43
@muffel: The definition is straightforward. The sequence $b_0, b_1, b_2, \dots$ is encoded using the series $b_0+b_1x+b_2x^2+\cdots$. An important simple example is the sequence $1,1,1,\dots$ which is encoded by $1+x+x^2+\cdots$, which, for most purposes, can be written as $1/(1-x)$ (remember the formula for the sum of a geometric progression). The sequence $0^2, 1^2, 2^2, 3^2, \dots$ is encoded by $x+4x^2+ 9x^3+\cdots$. – André Nicolas Jun 13 '11 at 18:57
@muffel Concrete Mathematics is an awesom book when it comes to sums and generating functions. Just if you're curios. – FUZxxl Jun 13 '11 at 19:42
@FUZxxl the one from Ronald L. Graham? – muffel Jun 14 '11 at 7:35
@muffel IIRC it's written by Graham, Patashnik and Knuth. – FUZxxl Jun 14 '11 at 12:14

Your Answer


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.