# Showing all rationals in $(0,1)$ are sums of certain reciprocals by induction

Help me please to understand this exercise and probably to solve it.

Show that every positive rational number $\frac{m}{n}\in (0,1)$ can be represented as $$\frac{m}{n} = \frac{1}{q_1} + \frac{1}{q_2} + \cdots + \frac{1}{q_r},$$ where $q_1 \lt q_2\lt \cdots \lt q_r$ are positive integers and $q_i$ is a divisor of $q_{i+1}$ for all $i=1,2,\ldots,r-1$.

I don't get the last part? Tja, actually, I don't know in general how to solve it.

-
The last part means that $q_1 = d_1$, $q_2 = d_2 \cdot d_1$, $q_r = d_r \cdots d_2 \cdot d_1$. Consider an example $m=4$ and $n=5$. Then $d_1=d_2=2$ and $d_3 = 5$ is a solution. – Sasha Oct 14 '11 at 16:23
It looks like some sort of a constrained Egyptian fraction decomposition... – J. M. Oct 14 '11 at 16:39

Find the least integer $q_1$ with

$$\frac mn\ge\frac1{q_1}\tag1$$

and write

$$\frac mn=\frac1{q_1}(1+x)\;.$$

Solving for $x$ yields

$$x=\frac{q_1m-n}n\;.$$

By $(1)$, we have $x\ge0$. Since $q_1$ is the least number for which $(1)$ holds, we also have

$$\frac mn\lt\frac1{q_1-1}\;,$$

which yields

$$q_1m-n\lt m$$

and thus

$$x\lt\frac mn\lt1\;.$$

Thus we have $x\in[0,1)$. If we slightly generalize to include $0$ in the interval (with $r=0$), the result follows by induction: $x$ has the same denominator as $m/n$ but a lower numerator, so if we apply the same procedure to $x$ recursively, the recursion must eventually end; then substituting the results and multiplying out all the parentheses yields the desired representation.

-
Just to add: The "induction" we are doing is a kind of "bounded" induction: we fix $n$, and we do induction on $m$, but only need to worry about $1\leq m\lt n$. – Arturo Magidin Oct 14 '11 at 16:32