# Memory Breakdown in Firefox

(Originally posted 2011-07-19.)

Here’s another neat piece of algebra: A technique for summing series.

You know what b – a + c – b + d – c is. Right?

Suppose I were to write the same sum as:

(b – a) +

(c – b) +

(d – c)

The answer is still d – a. Right?

Now, suppose I re-label with s0 = a, s1 = b, s2 = c and s3 = d. We end up with:

(s1 – s0) +

(s2 – s1) +

(s3 – s2)

This is actually pretty scalable terminology as you can write sr for any arbitrary value of r. And that’s one of the strengths of algebra: generalisation.

So let’s do that up to n:

(s1 – s0) +

(s2 – s1) +

(sn – sn-1)

which is, of course, sn – s0.

But what has that got to do with summing series?

If we can replace each (sr – sr-1) by a single term ur you may see the relevance…

u1 + u2 + … + un = sn – s0.

The series summation boils down to a "simple" subtraction. The trick is to find these s terms, given the u terms. Let’s try it with an example.

### Summing The Integers

This is the series 1, 2, 3, … , n.

The r’th u term is just r. ur = r. So we now have to find the sr term. Remember sr – sr-1 has to equal r.

Try sr = r (r + 1).

Then sr-1 = (r – 1) r   or   r (r – 1).

So sr – sr-1 = [(r + 1) – (r – 1)] r   or   2r. Not quite what we wanted. But we know – dividing by the factor of 2 – we should’ve guessed sr = ½ r (r + 1).

So sn – s0 = ½ n (n + 1) – ½ 0 (0 + 1) = ½ n (n + 1) – 0 = ½ n (n + 1).

The sum of the first n integers being ½ n (n + 1) is a well-known result. Admittedly it could’ve been done another way. But it’s simple enough to show the method.

### Another Example – Summing The Squares Of The Integers

This is the series 1, 4, 9, … , n² .

In this case we need to do something that will appear slightly perverse:

Rewrite r² as r ( r + 1) – r.

If you can split each of the terms in a series into two terms you can sum these sub terms. I just did the split. We already know how to sum the "r" portion. It’s ½ n (n + 1). So we need to sum the r (r+1) portion and subtract ½ n (n+1) from the result.

Try sr = r (r + 1) (r + 2).

Again we need to find sr-1.

It’s:

(r – 1) r (r + 1)

or, rearranging,

r (r+1) (r-1)

So

sr – sr-1 = [(r + 2) – (r – 1)] r (r + 1) or 3r (r + 1).

This is 3 times what we want so we should’ve guessed sr = 1/3 r (r + 1) (r + 2).

So this portion of the sum is 1/3 n (n + 1) (n + 2) – 1/3 0 (0 + 1)(0 + 2) or 1/3 n (n + 1) (n + 2).

But we need to subtract ½ n (n + 1) from this:

1/3 n (n + 1) (n +2) – ½ n (n + 1) = 2/6 n (n + 1) (n +2) – 3/6 n (n + 1)

or

1/6 n (n + 1) [ 2 (n + 2) – 3] = 1/6 n (n + 1)( 2 n + 1) .

If you try it for a few values you’ll see it’s right. This isn’t such a well known result as for the sum of the integers.

I’m conscious there’s been some fiddliness here – which is where I normally fall down. 😦

But I think the "sum a series by converting it to a single subtraction" trick is a neat one – which is why I share it with you.