Sigma notation ninja tricks 2: splitting sums

[Previous posts in this series: jumping constants]

Trick 2: splitting sums

I’ve written about this before, but it’s worth spelling it out for completeness’ sake. If you have a sum of something which is itself a sum, like this:

$\displaystyle \sum (A + B)$

you can split it up into two separate sums:

$\displaystyle \sum (A + B) = \left( \sum A \right) + \left( \sum B \right)$

(You can also sort of think of this as the sigma “distributing” over the sum.) For example,

$\displaystyle \sum_{k=1}^n (k + 2) = \left( \sum_{k=1}^n k \right) + \left( \sum_{k=1}^n 2 \right).$

Why is this? Last time, the fact that we can pull constants in and out of a sigma came down to a property of addition, namely, that multiplication distributes over it. This, too, turns out to come down to some other properties of addition. As before, let’s think about writing out these sums explicitly, without sigma notation.

First, on the left-hand side, we have something like

$\displaystyle \sum_i (A_i + B_i) = (A_1 + B_1) + (A_2 + B_2) + (A_3 + B_3) + \dots$

And on the right-hand side, we have

$\displaystyle \left(\sum_i A_i\right) + \left(\sum_i B_i \right) = (A_1 + A_2 + A_3 + \dots) + (B_1 + B_2 + B_3 + \dots)$

We can see that we get all the same terms, but in a different order. But as we are all familiar with, the order in which you add things up doesn’t matter: addition is both associative and commutative, so we can freely reorder terms and still get the same sum.¹

So $\sum$ “distributes over” sums! Let’s use the example from above to see how this can be useful. Suppose we want to figure out a closed-form expression for

$\displaystyle \sum_{k=1}^n (k + 2).$

If we didn’t otherwise know how to proceed we could certainly start by trying some examples and looking for a pattern. Or we could even be a bit more sophisticated and notice that this sum will be $3 + 4 + 5 + \dots + (n+2)$ , so it must be $3$ less than the triangular number $1 + 2 + 3 + \dots + (n+2)$ . But we don’t even need to be this clever. If we just distribute the sigma over the addition, we transform the expression into two simpler sums which are easier to deal with on their own:

$\displaystyle \sum_{k=1}^n (k + 2) = \left( \sum_{k=1}^n k \right) + \left( \sum_{k=1}^n 2 \right)$

The first sum is $1 + 2 + 3 + \dots + n$ , that is, the $n$ th triangular number, which is equal to $n(n+1)/2$ . The second sum is just $2 + 2 + \dots + 2$ ( $n$ times), so it is equal to $2n$ . Thus, an expression for the entire sum is

$\displaystyle \frac{n(n+1)}{2} + 2n = \frac{n(n+1) + 4n}{2} = \frac{n(n+5)}{2}.$

As a double check, is this indeed three less than the $(n+2)$ nd triangular number?

$\displaystyle \frac{(n+2)(n+3)}{2} - 3 = \frac{n^2 + 5n + 6}{2} - \frac{6}{2} = \frac{n(n+5)}{2}$

Sure enough! Math works!

At least, as long as the sum is finite! This still works for some infinite sums too, but we have to be careful about convergence.↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

3 Responses to Sigma notation ninja tricks 2: splitting sums

xander says:

March 18, 2017 at 9:48 pm

I know that this might be a bit beyond your desired scope, but I can’t help but bring up one of my favorite results. While *finite* addition is commutative and we can rearrange the terms of a finite sum as much as we want, it all falls apart if we want to deal with infinite sums. In particular, Riemann’s rearrangement theorem states that if you are handed any number $L$ and an infinite sum that adds up to something finite, but adds to infinity if you slap absolute values on the summands (i.e. the infinite sum converges, but not absolutely), then there is a rearrangement of the sum so that it adds up to $L$ . It is a really bizarre result, and highlights the care that must be taken whenever infinities get into the mix.
- Brent says:
  
  March 19, 2017 at 4:18 pm
  
  Thanks for the comment! This is why I added a footnote about finite vs infinite sums, but I hadn’t remembered the details of Riemann’s rearrangement theorem. It is a bizarre and wonderful theorem indeed. Do you happen to know how difficult it is to prove?
  - xmhenderson says:
    
    March 19, 2017 at 5:46 pm
    
    Quantifying how difficult something is to prove is always a bit of a challenge, as it depends quite a bit on what one knows. However, I think that the basic idea is pretty clear. First, one needs a little lemma:
    
    Lemma: Let $(a_n)_{n=1}^{\infty}$ be a sequence such that $\sum_{n=1}^{\infty} a_n$ converges, but does not converge absolutely. For each $n$ , define $a_n^+ = \max\{a_n, 0\}$ and $a_n^- = \min\{a_n,0\}$ . Then both $\sum_{n=1}^{\infty} a_n^+$ and $\sum_{n=1}^{\infty} -a_n^-$ diverge to infinity.
    
    Essentially, the idea is to consider the sums of the positive and negative terms separately. If both of these series converged, then the original series would be absolutely convergent, which contradicts the hypothesis that the series converges only conditionally. If one of the series is convergent and the other divergent, then the sum of the two series must diverge (basically, something infinite plus something finite must be infinite). We get a proof of the lemma by making this rigorous.
    
    Once the lemma is proved, we can prove the rearrangement theorem.
    
    Theorem: Suppose that $\sum_{n=1}^{\infty} a_n$ converges, but not absolutely, and let $L$ be any extended real number (i.e. any real number, or positive or negative infinity). Then there is a permutation $\sigma$ of $\mathbb{N}$ such that $\sum_{n=1}^{\infty} a_{\sigma(n)} = L$ .
    
    Again, I’m not going to try to be rigorous here, but the basic idea is that we can first arrange the positive terms in decreasing order, and the negative terms in increasing order. Since the series converges conditionally, the sequence $(a_n)_{n=1}^{\infty}$ must tend to zero. This means that the sequences of positive and negative terms must also tend to zero. Now, add positive terms together until you get something just bigger than $L$ , then add negative terms to that until you get something just less than $L$ , then add positive terms again until you get something just bigger than $L$ , and so on. Since the amounts that you are adding and subtracting are getting smaller, the error shrinks as we repeat this process over and over again. In the limit, we get exactly $L$ . But $L$ was an arbitrary constant that we fixed at start, which gives the proof.