Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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)$$ –  J. M. May 9 '12 at 2:38

4 Answers 4

up vote 2 down vote accepted

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*}$$

share|improve this answer

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.

share|improve this answer
1  
See also the book $A=B$. –  lhf May 9 '12 at 3:15

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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