4
$\begingroup$

Is there a general method for removing a sum from an expression to produce a closed form?

For example I needed to "unroll" the following expression in a recent programming competition (as $k_1$ and $k_2$ are large) and couldn't do it...

$ \sum_{w=2}^{k_1}\sum_{h=2}^{k_2}(w-1)(h-1) $

Do I miss some discrete math training? By what method would you go about solving this? Is there a common textbook that would cover this?

  • 0
    Note that your summation easily factorizes to $\left(\sum_{w=2}^{k_1}(w-1)\right)\left(\sum_{h=2}^{k_2}(h-1)\right)$2012-05-09

4 Answers 4

4

The inner sum is $\sum_{h=2}^{k_2}(h-1) = 1 + 2 + \cdots + (k_2-1)$ which has the well-known total $\sum_{h=2}^{k_2}(h-1) = 1+2+\cdots+(k_2-1) = \frac{(k_2-1)k_2}{2}.$ Similarly for $\sum_{w=2}^{k_1}(w-1).$ Now "undistribute" the constant terms using the fact that if $a$ does not depend on $j$, then $\sum_{i=r}^s af(i) = a\sum_{i=r}^2f(i)$ so $\begin{align*} \sum_{w=2}^{k_1}\sum_{h=2}^{k_2}(w-1)(h-1) &= \sum_{w=2}^{k_1}\left( (w-1)\sum_{h=2}^{k_2}(h-1)\right)\\ &= \sum_{w=2}^{k_1}(w-1)\left(\frac{(k_2-1)k_2}{2}\right)\\ &= \frac{(k_2-1)k_2}{2}\sum_{w=2}^{k_1}(w-1)\\ &= \frac{(k_2-1)k_2}{2}\left(\frac{(k_1-1)k_1}{2}\right)\\ &= \frac{k_1k_2(k_1-1)(k_2-1)}{4}. \end{align*}$

3

To answer the question you asked, there is not in general a method for converting a summation to closed form.

However, the book Concrete Mathematics, by Graham, Knuth, and Patashnik, discusses the evaluation of sums in great detail, and is full of techniques for converting them to closed form. It is also extremely readable. If you have not yet read it, then yes, you have missed some essential discrete math training.

  • 1
    See also the book [$A=B$](http://www.math.upenn.edu/~wilf/AeqB.html).2012-05-09
0

How about something like: $ \sum_{w=2}^{k_1}\sum_{h=2}^{k_2}(w-1)(h-1) = \sum_{w=2}^{k_1} (w-1) \sum_{h=2}^{k_2} (h-1) $ You can compute a closed form answer for both of these summations using a small change of variable and a standard summation formula.

0

This can be solved fairly easily. Note that the innermost sum is with respect to h, so the factor $w - 1$ is a "constant" w.r.t. h. Thus, we can pull it out to get

$\sum_{w=2}^{k_1} \left((w - 1) \sum_{h=2}^{k_2} (h - 1)\right) = \left(\sum_{w=2}^{k_1} (w - 1)\right)\left(\sum_{h=2}^{k_2} (h - 1)\right)$

Now use the fact

$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$.

and linearity to evaluate the sums.