# Find the formula of the sequence using generating functions

I have the following sequence given:

$$\sum_{k=1}^{n} (-1)^{k}k^{2}$$

How can I do this? The sequence goes like this:

$$-1 + 4 - 9 + 16 - 25 + 36 - ...$$

So it doesn't have any variables inside. It looks like a geometric sequence for me, so the simple known formula would do the whole thing, but I actually doubt it's that simple.

So there are some generating functions that are quite similar, like:

$$\sum (-1)^{n}x^{n} = x - x^{2} + x^{3} - x^{4} + ...$$

But, uhm, well...what's next? The lack of x variable seems a bit strange to me.

Note that the generating function for the sequence $(-1)^k$ is $\frac{1}{1+x}$. Also observe that if $(a_k)$ is any sequence with generating function $f$, then the generating function for the sequence $(ka_k)$ is $x\frac{d}{dx} f$ and the generating function for the sequence $\sum a_k$ is $\frac{f}{1-x}$. With this in mind, we find the generating function for the sequence $(-1)^k k$ to be $$x\frac{d}{dx}\frac{1}{1+x}=-\frac{x}{(1+x)^2}$$ and so the generating function for $(-1)^k k^2$ is $$-x\frac{d}{dx}\frac{x}{(1+x)^2}=-\frac{(1-x)x}{(1+x)^3}$$

Thus, your generating function is $$-\frac{x}{(1+x)^3}$$

If we use partial fractions, we can write this as $$\frac{1}{(1+x)^3}-\frac{1}{(1+x)^2}$$ If we use the formla $$\frac1{(1+x)^k}=\sum_{n\ge 0}\binom{n+k-1}{k-1}(-x)^n$$ we finally get that the sum is $$\sum_{k=1}^n(-1)^k k^2=(-1)^n\left(\binom{n+2}{2}-\binom{n+1}{1}\right)$$

Edit: \begin{align} \frac{f}{1-x}&=\frac{1}{1-x}\sum_{k=0}^{\infty}a_kx^k=(1+x+...)\sum_{k=0}^{\infty}a_kx^k=\\ &=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+...= \\ &=\sum_{k=0}^\infty \left( \sum_{n=0}^k a_n\right)x^k \end{align}

• It might be helpful to explain why you divided by $1-x$ to get the generating function. – robjohn May 11 '13 at 14:38
• @robjohn Your wish is my command. – user60725 May 11 '13 at 16:08
• The effect of $x\frac{\mathrm{d}}{\mathrm{d}x}$ on a generating function is pretty simple, but the effect of dividing by $1-x$ is not. I was thinking of something more like this: If $$f(x)=\sum_{k=0}^\infty a_kx^k$$ then \begin{align} \sum_{n=0}^\infty\left(\sum_{k=0}^na_k\right)x^n &=\sum_{k=0}^\infty\sum_{n=k}^\infty a_kx^n\\ &=\sum_{k=0}^\infty a_k\frac{x^k}{1-x}\\ &=\frac{f(x)}{1-x} \end{align} – robjohn May 11 '13 at 16:42
• Your final expression simplifies to$$(-1)^n \left(\binom{n + 2}{2} - \binom{n + 1}{1} \right) =(-1)^n \left( \frac{(n + 2) (n + 1)}{2} - \frac{n + 1}{1} \right) = \frac{(-1)^n n(n + 1)}{2}$$ – vonbrand May 15 '13 at 15:57

The generating function is \begin{align} \sum_{n=0}^\infty\sum_{k=0}^n(-1)^kk^2x^n &=\sum_{k=0}^\infty\sum_{n=k}^\infty(-1)^kk^2x^n\\ &=\sum_{k=0}^\infty(-1)^kk^2\frac{x^k}{1-x}\\ &=\frac1{1-x}\sum_{k=0}^\infty(-1)^kk^2x^k\tag{1} \end{align} Starting with $\frac1{1+x}$ and taking derivatives, we get \begin{align} \frac1{1+x}&=\sum_{k=0}^\infty(-1)^kx^k\\ \frac1{(1+x)^2}&=\sum_{k=0}^\infty(-1)^k(k+1)x^k\\ \frac2{(1+x)^3}&=\sum_{k=0}^\infty(-1)^k(k+2)(k+1)x^k \end{align}\tag{2} Since $k^2=(k+2)(k+1)-3(k+1)+1$, we have \begin{align} \sum_{k=0}^\infty(-1)^kk^2x^k &=\frac2{(1+x)^3}-\frac3{(1+x)^2}+\frac1{1+x}\\ &=\frac{(x-1)x}{(1+x)^3}\tag{3} \end{align} Thus, the generating function we want is \begin{align} \frac1{1-x}\sum_{k=0}^\infty(-1)^kk^2x^k &=\frac1{1-x}\frac{(x-1)x}{(1+x)^3}\\ &=-\frac{x}{(1+x)^3}\\ &=-\sum_{n=0}^\infty\binom{-3}{n-1}x^n\\ &=\sum_{n=0}^\infty(-1)^n\binom{n+1}{n-1}x^n\\ &=\sum_{n=0}^\infty(-1)^n\binom{n+1}{2}x^n\tag{4} \end{align} Therefore, $$\sum_{k=0}^n(-1)^kk^2=(-1)^n\binom{n+1}{2}\tag{5}$$

Start with: $$\sum_{0 \le k \le n} (-1)^k z^k = \frac{1 - (-z)^{n + 1}}{1 - (-z)}$$ Then note that: $$z \frac{d}{dz} \sum_{k} a_k z^k = \sum_k k a_k z^k$$ This hints at differentiating the above sum twice and evaluating at $z = 1$: $$z \frac{d}{dz} \left(z \frac{d}{dz} \frac{1 - (-z)^{n + 1}}{1 + z} \right) \big\lvert_{z = 1} = \frac{(-1)^n n (n + 1)}{2}$$

Maxima help with the mess is gratefully acknowledged.

The lazy (meaning: professional) way of getting the result is to generate the first few terms of the partial alternating sum, -1, 3, -6, 10, -15,.. and then to look up the terms in the http://oeis.org, leading to http://oeis.org/A089594, and take the g.f. from the formula section.