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$ .

Share this:

Like this:

Related

Leave a Reply Cancel reply