Java Reference
In-Depth Information
14.1
Summation Techniques
Consider the following simple summation.
n
X
i:
i=1
In Section 2.6.3 it was proved by induction that this summation has the well-known
closed form n(n + 1)=2. But while induction is a good technique for proving that
a proposed closed-form expression is correct, how do we find a candidate closed-
form expression to test in the first place? Let us try to think through this problem
from first principles, as though we had never seen it before.
A good place to begin analyzing a summation it is to give an estimate of its
value for a given n. Observe that the biggest term for this summation is n, and
there are n terms being summed up. So the total must be less than n
2
. Actually,
most terms are much less than n, and the sizes of the terms grows linearly. If we
were to draw a picture with bars for the size of the terms, their heights would form a
line, and we could enclose them in a box n units wide and n units high. It is easy to
see from this that a closer estimate for the summation is about (n
2
)=2. Having this
estimate in hand helps us when trying to determine an exact closed-form solution,
because we will hopefully recognize if our proposed solution is badly wrong.
Let us now consider some ways that we might hit upon an exact equation for
the closed form solution to this summation. One particularly clever approach we
can take is to observe that we can “pair up” the first and last terms, the second and
(n 1)th terms, and so on. Each pair sums to n + 1. The number of pairs is n=2.
Thus, the solution is n(n+ 1)=2. This is pretty, and there is no doubt about it being
correct. The problem is that it is not a useful technique for solving many other
summations.
Now let us try to do something a bit more general. We already recognized
that, because the largest term is n and there are n terms, the summation is less
than n
2
. If we are lucky, the closed form solution is a polynomial. Using that as
a working assumption, we can invoke a technique called guess-and-test. We will
guess that the closed-form solution for this summation is a polynomial of the form
c
1
n
2
+ c
2
n + c
3
for some constants c
1
, c
2
, and c
3
. If this is true, then we can plug
in the answers to small cases of the summation to solve for the coefficients. For
this example, substituting 0, 1, and 2 for n leads to three simultaneous equations.
Because the summation when n = 0 is just 0, c
3
must be 0. For n = 1 and n = 2
we get the two equations
c
1
+ c
2
=
1
4c
1
+ 2c
2
=
3;
