[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:
you can split it up into two separate sums:
(You can also sort of think of this as the sigma “distributing” over the sum.) For example,
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
And on the right-hand side, we have
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.1
So “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
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 , so it must be less than the triangular number . 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:
As a double check, is this indeed three less than the nd triangular number?
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.↩