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.
Answer
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.
No comments:
Post a Comment