5
$\begingroup$

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!

  • 2
    What is "g" doing in the recurrence relation?2011-06-13
  • 0
    What is the $g$?2011-06-13
  • 4
    $$g = 6?$$ ${}$2011-06-13
  • 0
    @Beni-Gogosel @olivier-begassat Sorry, it should be a "6", I just corrected it. I ran out of coffee and must have missed it...2011-06-13

3 Answers 3

4

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

  • 0
    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? Thanks2011-06-14
  • 0
    @muffel, solve for $f$.2011-06-15
  • 0
    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?2011-06-15
  • 1
    @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.2011-06-15
  • 0
    @Gerry-Myseron ok, I then just followed the wrong approach. That finally does the trick! Thanks a lot!2011-06-19
5

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

  • 0
    Thank you, that helped me solving a)! Do you have any further hints for b) and c)?2011-06-13
  • 0
    @muffel For b) and c) recall that $\sum_{i=0}^ni^2=n(n+1)(2n+1)/6$.2011-06-13
4

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.

  • 0
    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).2011-06-13
  • 0
    @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$.2011-06-13
  • 1
    @muffel *Concrete Mathematics* is an awesom book when it comes to sums and generating functions. Just if you're curios.2011-06-13
  • 0
    @FUZxxl the one from Ronald L. Graham?2011-06-14
  • 1
    @muffel IIRC it's written by Graham, Patashnik and Knuth.2011-06-14
  • 0
    A very good book on generating functions and their use is Wilf's [generatingfunctionology](http://www.math.upenn.edu/~wilf/DownldGF.html).2014-04-07