# 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}}$$

-
Seen this? – J. M. Oct 12 '11 at 1:18
See this also. – J. M. Oct 12 '11 at 1:40

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.

-
This is fine for $0\lt x\lt1$, but OP imposed no upper bound on $x$. – Gerry Myerson Dec 25 '11 at 1:29
Well, there was... – J. M. Dec 25 '11 at 4:04
you would think that by now I would know to look at edit history before making such a comment. Sorry. – Gerry Myerson Dec 26 '11 at 4:00