The Harmonic Hurdler

Here’s a classic exercise in elementary number theory.

Consider a (mathematical and thus constrained to a point) rabbit who starts at zero on the real number line and starts to jump towards her right.

Her first jump is of length 1, her second jump is of length 1/2, her third jump is of length 1/3, and so on, so that after k jumps, her position S(k) on the line is

S(k) = \sum_{n=1}^{k} \frac{1}{n} = 1+ \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k}.

There are hurdles which are placed at the integers from 2 onwards. Of course, we don’t have a hurdle at the integer 1, for this is where the rabbit lands on her first jump. The question is:

Will the rabbit ever land on a hurdle?

Or, put mathematically:

Is S(k) an integer for any k \geq 2?

The answer to both questions is no; the rabbit will never hit a hurdle, for it turns out that the sum

\sum_{n=1}^{k} \frac{1}{n} = 1+ \frac{1}{2} + \frac{1}{3} + \cdots \frac{1}{k}

is never an integer for k \geq 2. The proof we will give here involves the following theorem.

Bertrand’s postulate: For every real number x > 1 there is a prime in the interval (x,2x).

Now, let’s prove that the rabbit never lands on a hurdle. We will prove this by contradiction. Assume that we have the equation

1+ \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k} = m

where k \geq 2 and m is an integer. If we set x=k/2 in Bertrand’s postulate, it follows that there must be a prime p in the interval (k/2,k). This means that the term 1/p appears on the left hand side of the above equation, and we may subtract it from both sides to get

1+ \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1} + \frac{1}{p+1} + \cdots + \frac{1}{k} = m - \frac{1}{p}.

Now, the left hand side of the above equation can be written as a fraction a/b, where b is not divisble by the prime p. This is because we have moved the term involving p to the other side, and there are no other integers from 1 to k which are divisible by p, as we chose p \in (k/2,k) so that its first multiple 2p is greater than k. Thus we have

\frac{a}{b} = m - \frac{1}{p} = \frac{mp-1}{p}

which we can rearrange to get

ap = b (mp-1).

This gives us a contradiction as the left hand side is divisible by the prime p, but the right hand side is not, as both b and mp-1 are not divisible by p.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s