Solution to sum of unit fractions puzzle

This is a solution to the sum of unit fractions puzzle posted earlier.

The problem:

Show that every positive rational number can be written as a sum a finite number of distinct unit fractions (unit fraction = number of the form 1/n).

Solution

---

[This proof appears in the classic number theory book by Niven and Zuckerman]

First, consider rationals $\lt 1$ in the reduced form $\frac{a}{b}$, with $0 \lt a \lt b$ and $\gcd(a,b) = 1$.

We prove by strong induction on $a$.

If $a = 1$, there is nothing to prove.

If $a = 2$, then $b$ must be odd (say $2x+1$).

Then we can use the identity

$$\frac{2}{2x+1} = \frac{1}{x+1} + \frac{1}{(x+1)(2x+1)}$$

Now given $\dfrac{a}{b}$ (in reduced form)

Let $c$ be the smallest integer such that $ac \gt b$.

Then we must have that $ac = b + r$, for some $0 \lt r \lt a$.

If $r \gt a$, then $c$ won't be the smallest integer such that $ac \gt b$.

Now consider $\dfrac{ca}{b} = 1 + \dfrac{r}{b}$.

Thus

$\dfrac{a}{b} = \dfrac{1}{c} + \dfrac{r}{bc}$

By induction hypothesis, $\dfrac{r}{bc}$ can be written as a sum of distinct unit fractions.

Now $\dfrac{r}{bc} \lt \dfrac{1}{c}$, so none of those unit fractions can be $\dfrac{1}{c}$.

Thus $\dfrac{a}{b}$ can be written as a sum of distinct unit fractions.

Now, if $r$ is any rational $\gt 1$, then since the series $\sum_{k=1}^{\infty} \frac{1}{k}$ diverges, there is some m such that

$$1 + \frac{1}{2} + \dots + \frac{1}{m} \le r \lt 1 + \frac{1}{2} + \dots + \frac{1}{m+1}$$

Consider $r - (1 + \dfrac{1}{2} + \dots + \dfrac{1}{m})$, this is a rational number < $\dfrac{1}{m+1}$, and so can be written as a sum of distinct unit fractions, and each denominator will be $\gt m$.

Thus we are done.