# How to solve this recurrence using generating functions?

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

Hi!

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?

-
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

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

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

-
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

$$a_n=a_n$$

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.

-
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