Sum to closed form?
Matthew Harrington 
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?
$\endgroup$ 14 Answers
$\begingroup$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*}$$
$\endgroup$ $\begingroup$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.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$
