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 s₀ = a, s₁ = b, s₂ = c and s₃ = d. We end up with:

(s₁ – s₀) +

(s₂ – s₁) +

(s₃ – s₂)

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

So let’s do that up to n:

(s₁ – s₀) +

(s₂ – s₁) +

…

(s_n – s_n-1)

which is, of course, s_n – s₀.

But what has that got to do with summing series?

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

u₁ + u₂ + … + u_n = s_n – s₀.

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. u_r = r. So we now have to find the s_r term. Remember s_r – s_r-1 has to equal r.

Try s_r = r (r + 1).

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

So s_r – s_r-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 s_r = ½ r (r + 1).

So s_n – s₀ = ½ 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 s_r = r (r + 1) (r + 2).

Again we need to find s_r-1.

It’s:

(r – 1) r (r + 1)

or, rearranging,

r (r+1) (r-1)

So

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

This is 3 times what we want so we should’ve guessed s_r = 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.