Double trouble

This is a nice problem - it's great that you can really see what's going on! Let's see how you fared with it...

Hani, from the British School, started off by spotting a pattern:

1/2 + 1/4 = 3/4

1/2 + 1/4 + 1/8 = 7/8

1/2 + 1/4 + 1/8 + 1/16 = 15/16

In these sums, the denominator of the answer is the denominator of the last fraction in the sum, and the numerator is one less than the denominator.

Great! The class at Toongabbie Public School spotted this too. Well done! Ayesha, from Westfield Middle School, instead noticed something geometric:

In Charlie's diagram, if you draw the sum in a square, then for each new term of the sum you add, half of the remaining gap is halved again.

Zachary, from Sonoran Science Academy, wrote the following:

First, let us see what we are faced with. We want to simplify the expression:

$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^n}$.

Let's make the denominators the same. We will now see that the expression is:

$\frac{2^{n-1}}{2^n} + \frac{2^{n-2}}{2^n} + \dots + \frac{1}{2^n}$.

Now, we can rearrange the terms to get:

$\frac{1+2+4+8+\dots +2^{n-1}}{2^n}$.

This may seem like a hard term to simplify, but let us just look at the numerator of the term. For small values of n:

n=1 -> 1

n=2 -> 1+2= 3

n=3 -> 1+2+4= 7

n=4 -> 1+2+4+8= 15

It's easy to spot the pattern here: each value of n gives us $2^n - 1$. Now we have a nice simplified term: $\frac{2^n - 1}{2^n}$.

Nice, but how do you know that the pattern you've spotted will continue?

What about Alison's sum? Rajeev, from Haberdashers' Aske's Boys' School, noticed:

I notice that the answer was 1 less than the next number in the sequence, e.g. 1+2+4+8 = 15, which is one less than 16. The pattern will continue like this. The general pattern is $2^{n+1}-1$.

Thanks also to Jordi from Hall Meadow who gave the same answer. Amrit, from Newton Farm, noticed that these were both geometric series, and gave us a formula for them. (Charlie's first term was 1/2 and his ratio was 1/2; Alison's first term was 1 and her ratio was 2.) Well spotted!

Niharika gave - and proved! - a general formula for $1 + a + a^2 + \dots + a^n$. Her proof went as follows:

I looked at some cases when a and n were both small, and sooner or later I guessed the formula $1 + a + a^2 + \dots + a^n = \frac{1 - a^n}{\frac{1}{a} - 1}$.

Now suppose I know that $1 + a + a^2 + \dots + a^k = \frac{1 - a^k}{\frac{1}{a} - 1}$ for some number k. What happens when I add $a^{k+1}$ to both sides? Well, the right hand side becomes

$\frac{1 - a^k}{\frac{1}{a} - 1} + a^{k+1}$

$= \frac{1 - a^k}{\frac{1}{a} - 1} + \frac{a^{k+1}\left(\frac{1}{a} - 1\right)}{\frac{1}{a} - 1}$

$= \frac{1 - a^k}{\frac{1}{a} - 1} + \frac{a^{k} - a^{k-1}}{\frac{1}{a} - 1}$

$= \frac{1 - a^{k+1}}{\frac{1}{a} - 1}$.

What does this mean? It means that, if I know $1 + a + a^2 + \dots + a^k = \frac{1 - a^k}{\frac{1}{a} - 1}$ is true for some certain number k, then I know $1 + a + a^2 + \dots + a^{k+1} = \frac{1 - a^{k+1}}{\frac{1}{a} - 1}$ is true for k+1 too. So if I know that I'm allowed to plug in n = k into the formula $1 + a + a^2 + \dots + a^n = \frac{1 - a^n}{\frac{1}{a} - 1}$, then I know I'm also allowed to plug in n = k+1. But I can check it works for n = 1, so it must work for n = 2; but if it works for n = 2, it must work for n = 3; but if it works for n = 3, it must work for n = 4, and so on. It works for all values of n!

Wow! Thanks, Niharika. (For anyone who's interested, this is a special type of argument called a "proof by induction".) Niharika also found a method of using Charlie's sum to find the answer to Alison's sum, which she thought was 'cute':

Let's start off with Alison's sum, but without the 1 at the start:

$2 + 4 + 8 + \dots + 2^n$

$= 2^{n+1}\left( \frac{1}{2^n} + \frac{1}{2^{n-1}} + \dots + \frac{1}{8} + \frac{1}{4} + \frac{1}{2}\right)$

and the bit in brackets is Charlie's sum, which we've already worked out, so we get:

$= 2^{n+1} \left(\frac{2^n - 1}{2^n}\right)$

$= 2^{n+1} - 2$, and then we just add the 1 back to both sides.

That is cute. Well done!