Prove that any rational can be expressed in the form $\sum\limits_{k=1}^n{\frac{1}{a_k}}$, $a_k\in\mathbb N^*$

Let $x\in\mathbb{Q}$ with $x>0$.

Prove that we can find $n\in\mathbb{N}^*$ and distinct $a_1,...,a_n \in \mathbb{N}^*$ such that $$x=\sum_{k=1}^n{\frac{1}{a_k}}$$

Solution 1:

Any rational number $0 < x < 1$ possesses a so-called Egyptian fraction decomposition, which writes $x$ as a sum of fractions with unit numerators. One constructive proof is to use a "greedy" algorithm, which keeps subtracting off the unit fractions of the form $\dfrac1{\lceil 1/x\rceil}$.

Here's some Mathematica code demonstrating the greedy approach for $\dfrac{21}{23}$:

f = 21/23; l = {};
While[f != 0, l = {l, p = Ceiling[1/f]}; f -= 1/p;];
Flatten[l]

{2, 3, 13, 359, 644046}

This says that

$$\frac{21}{23}=\frac12+\frac13+\frac1{13}+\frac1{359}+\frac1{644046}$$

This is a very naïve method, as there are other algorithms that yield unit fractions with tinier denominators. For the purposes of this question, it suffices to prove that the algorithm halts. As mentioned here (the proof is attributed to Fibonacci), if we let $m=\lceil 1/x \rceil$, then we always have the bracketing $\dfrac1{m} \leq x < \dfrac1{m-1}$. The numerator of $x-\dfrac1{m}$ can then be shown to be smaller than the numerator of $x$. Thus, the repeated application of the steps of reciprocation and subtraction results in numerators that go smaller and smaller, until the remainder after subtracting off unit fractions is zero.

See this for a nice bibliography of decomposition methods.