4
$\begingroup$

In one of my homeworks I was given the following sequence $1^2-2^2+3^2-4^2+\dots (-1)^{n+1}n^2$, and I'm supposed to find a closed form formula and prove that it works.

Rewriting this as a sum gives the following

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

I have found the closed form, which is $-\frac{1}{2} (-1)^n n (n+1)$, and I also have the proof, which was trivial to get. The problem is that I do not know how to get to this formula in a systematic way, without a wild guess or a tool like Mathematica, which would somehow just spit out the answer.

I started reading Knuth's Concrete Mathematics, which seems to describe how to approach these problems in general, but I'm having a hard time understanding the text (I'm in first semester studying Computer Science.)

I tried comparing the data this sum generates ($1, -4, 9, -16, 25, -36, 49, -64$), and tried looking at the prefix sums ($1, -3, 6, -10, 15, -21, 28, -36, 45, -55$), but I just don't know how this is supposed to help me in finding this formula.

TL;DR: How can I systematically find a closed form formula for this particular summation, or any arbitrary one in general?

I tried looking through the other questions, but they tend to address more complicated formulars which I'm having hard trouble understanding.

$\endgroup$
1
$\begingroup$

As far as I'm aware, there isn't really a standard way of computing summations. Sometimes a guess, which you then inductively prove is sufficient. Quite often you use other known summations to get to the one you want (via algebraic manipulation). There are a large number of techniques I've seen people on this site use, which are well beyond me: it is a hard problem in general.

For your case however, and many similar summations, you can be reasonably systematic: there are two potential methods I can see. The first is to look at pairs of terms, which is motivated by the fact that the sum alternates, so perhaps parts of it will cancel.

$$(1^2-2^2)+(3^2-4^2)+\cdots+((n-1)^2-n^2)$$

Note I am implicitly assuming that $n$ is even in this representation, but we can go back and do the odd case later. Now, each part of this sum in parenthesis is of the form:

$$(i-1)^2-i^2=-2i+1$$

so, if $n=2k$ is even, the sum becomes:

\begin{align*} (1^2-2^2)+(3^2-4^2)+\cdots+((2k-1)^2-(2k)^2) &= (-3)+(-7)+\cdots+(-4k+1) \\ &= -(3+7+\cdots+(4k-1)) \end{align*}

This summation looks particularly simple in comparison: a systematic approach to computing it is to note that this is equal to:

\begin{align*} -\sum_{i=1}^{k}(4i-1) &= -4\sum_{i=1}^k i+\sum_{i=1}^k 1 \\ &= -\frac{4k(k+1)}{2}+k \\ &= -2k^2-k \\ &= -\frac{n(n+1)}{2} \end{align*}

You can do similar kinds of grouping when $n$ is odd:

$$1^2+(-2^2+3^2)+\cdots+(-(n-1)^2+n^2)$$

and obtain the corresponding formula $\frac{n(n+1)}{2}$.

Note how the fact that $\sum_{i=1}^k i=\frac{i(i+1)}{2}$ was used? This is a pretty bread and butter fact, along with similar identities for $\sum_{i=1}^k i^p$, for $p=1,2,3,\cdots$. For example if I wanted to calculate $$\sum_{i=1}^n (3i^3+7i^2-i+5)$$ then I could apply the formulas

$$\sum_{i=1}^n i = \frac{i(i+1)}{2},\;\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6},\;\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$

to obtain:

\begin{align*} \sum_{i=1}^n (3i^3+7i^2-i+5) &= 3\sum_{i=1}^n i^3+7\sum_{i=1}^n i^2-\sum_{i=1}^n i+\sum_{i=1}^n 5 \\ &= 3\cdot\frac{n^2(n+1)^2}{4}+7\cdot\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}+5n \end{align*}

which allows us to systematically compute a large range of summations.

Bearing this in mind, an alternate approach for dealing with alternating sums, is to split them up into two different sums. Once again we will have to deal with separate cases for even and odd, but this is not a huge issue. For example, if $n=2k+1$ is odd we might group as follows:

\begin{align*} 1^2-2^2+\cdots+(2k+1)^2 &= (1^2+3^2+\cdots+(2k+1)^2)-(2^2+4^2+\cdots+(2k)^2) \\ &= \sum_{i=1}^k (2i+1)^2-\sum_{i=1}^k (2i)^2 \\ &= \sum_{i=1}^k (4i^2+4i+1)-\sum_{i=1}^k 4i^2 \end{align*}

at this point there's a pretty obvious cancellation to be made, but in some alternating sums this won't occur.

\begin{align*} &= 4\sum_{i=1}^k i^2+4\sum_{i=1}^k i + \sum_{i=1}^k 1 - \sum_{i=1}^k 4i^2 \\ &= \frac{4k(k+1)(2k+1)}{6}+\frac{4k(k+1)}{2}+k-\frac{4k(k+1)(2k+1)}{6} \\ &= \vdots \\ &= \frac{n(n+1)}{2} \end{align*}

Hopefully that gives you a way to see how some of these computations can be motivated.

$\endgroup$
  • $\begingroup$ Thanks for such an exhaustive answer! $\endgroup$ – Jakub Arnold Oct 13 '14 at 0:41
1
$\begingroup$

A method to systematically find a closed formula for this and similar expressions is based upon formal power series. The idea is to start from the most basic sequence \begin{align*} (1)_{n\geq 0}=(1,1,1,\ldots) \end{align*} and iteratively apply operators to obtain the wanted sequence \begin{align*} \left(\sum_{j=0}^n (-1)^{j+1}j^2\right)_{n\geq 0}=(1,-3,6,-10,15,\ldots) \end{align*} Here we do it systematically in four steps \begin{align*} (1)_{n\geq 0} \quad\rightarrow\quad (n)_{n\geq 0} \quad\rightarrow\quad (n^2)_{n\geq 0} \quad\rightarrow\quad ((-1)^{n+1}n^2)_{n\geq 0} \quad\rightarrow\quad \left(\sum_{j=0}^{n}(-1)^{j+1}j^2\right)_{n\geq 0} \end{align*}

We start with the constant sequence $(1)_{n\geq 0}=(1,1,1,\ldots)$ represented by the generating function \begin{align*} \frac{1}{1-x}&=\sum_{n=0}^{\infty}x^n=1+x+x^2+\cdots \end{align*}

We next observe that applying differentiation and multiplication with $x$ of a formal power series $A(x)=\sum_{n=0}^{\infty}a_nx^n$ results in

\begin{align*} (xD)A(x)&=(xD)\sum_{n=0}^{\infty}a_nx^n\\ &=x\sum_{n=0}^{\infty}na_nx^{n-1}\\ &=\sum_{n=0}^{\infty}na_nx^n \end{align*}

We conclude that application of the operator $xD$ to a power series $A(x)=\sum_{n=0}^{\infty}a_nx^n$ transforms the sequence \begin{align*} (a_n)_{n\geq 0}\qquad \text{to}\qquad (na_n)_{n\geq 0} \end{align*} and applying the operator $xD$ to a power series $A(x)$ iteratively $k$ times, we obtain \begin{align*} (xD)^kA(x)=\sum_{n=0}^{\infty}n^ka_nx^n \end{align*}

Applying the operator $xD$ to the geometric series $\frac{1}{1-x}$ we obtain \begin{align*} (xD)\frac{1}{1-x}&=\frac{x}{(1-x)^2}\\ &=\sum_{n=0}^\infty nx^n\\ \end{align*}

Applying the operator $xD$ twice, we obtain \begin{align*} (xD)^2\frac{1}{1-x}&=(xD)\frac{x}{(1-x)^2}\\ &=\frac{1+x}{(1-x)^3}\\ &=\sum_{n=0}^\infty n^2x^n \end{align*}

Next we replace $x$ with $-x$ and multiply with $-1$ to obtain \begin{align*} (-1)\left.\left((xD)^2A(x)\right)\right|_{x=-x}&=-\frac{x(1-x)}{(1+x)^3}\\ &=\sum_{n=0}^{\infty}(-1)^{n+1}n^2x^n\tag{1} \end{align*}

The last step is to transform a sequence \begin{align*} (a_n)_{n\geq 0}\qquad\text{to}\qquad\left(\sum_{j=0}^{n}a_j\right)_{n\geq 0} \end{align*} which can be done in terms of formal power series by multiplication with $\frac{1}{1-x}$ \begin{align*} \frac{1}{1-x}A(x)&=\frac{1}{1-x}\sum_{n=0}^{\infty}a_nx^n\\ &=\sum_{n=0}^\infty\left(\sum_{j=0}^na_j\right)a_nx^n \end{align*}

Applying this multiplication to (1) results in \begin{align*} \frac{-1}{1-x}\left.\left((xD)^2A(x)\right)\right|_{x=-x}&= \frac{x}{(1+x)^3}\\ &=\sum_{n=0}^{\infty}\left(\sum_{j=0}^\infty(-1)^{j+1}j^2\right)x^n \end{align*}

You may notice that with some routine it's a quick and easy job to conclude:

The generating function of the summation formula under consideration is \begin{align*} \frac{x}{(1+x)^3}=\sum_{n=0}^{\infty}\left(\sum_{j=0}^n(-1)^{j+1}j^2\right)x^n \end{align*}

Now it is time to harvest. We use the binomial series expansion to find a closed formula. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We obtain for $n\geq 1$ \begin{align*} \sum_{j=0}^n(-1)^{j+1}j^2&=[x^n]\frac{x}{(1+x)^3}\\ &=[x^{n-1}]\frac{1}{(1+x)^3}\tag{2}\\ &=[x^{n-1}]\sum_{j=0}^{\infty}\binom{-3}{j}x^j\tag{3}\\ &=\binom{-3}{n-1}\tag{4}\\ &=\binom{n+1}{n-1}(-1)^{n-1}\tag{5}\\ &=(-1)^{n-1}\frac{n(n+1)}{2} \end{align*}

Comment:

  • In (2) we use the rule $[x^n]x^k=[x^{n-k}]$

  • In (3) we apply the binomial series expansion

  • In (4) we extract the coefficient of $x^{n-1}$

  • In (5) we use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q=\binom{p+q-1}{p-1}(-1)^q \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.