How to solve this recurrence using generating functions?

Question

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?

Thank you in advance!

Answer 1

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

Answer 2

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

Answer 3

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.