How can I prove that every rational number can be expressed as the sum of $1/n$? (for a set of integer n chosen by a certain algorithm) So there is this extra exercise in my textbook. I looked it over with the TA and neither of us could solve it. The exercise goes like this:
Let $\alpha$ be positive and rational. Then, choose the smallest natural number $N_0$ such that $1/N_0 \leq \alpha$. Now let $\alpha_1=\alpha-1/N_0$. Now choose $N_1$ as the smallest natural number such that $1/N_1 \leq \alpha_1$ etc.
The exercise is to prove that this algorithm terminates for every rational $\alpha$. (i.e. at some point $\alpha_i=N_i$ and it will end as $0$) It's easy to prove that $\alpha_i$ becomes arbitrarily small, but I don't see any approach to prove it reaches zero.
 A: Let us consider one step of the algorithm: we have $\frac kl$, and we take $n$ the smallest positive integer such that $\frac 1n \leq \frac kl$. Furthermore, let us restrict to the nontrivial case where $n > 1$ (that is, $\frac kl < 1$).
We claim that in one step of the algorithm, the numerator of the fraction always decreases. Since it cannot decrease below 0, the algorithm must terminate. After subtracting, the new fraction is
$$
\frac kl - \frac 1n = \frac{kn-l}{ln}.
$$
Now, by assumption, $n$, was minimal, so $k < \frac l{n-1}$. Otherwise, we could have used $n-1$. Thus, $k(n-1) < l$, or in other words, $kn - l < k$. This concludes the proof.
A: For any given $p$ and $q$. Since series $\left\{ 1 \over n \right\}$ diverge, there must exist an integer $n$ that:
$$
\sum_{i=1}^{n} \frac 1 i \le \frac p q \lt \sum_{i=1}^{n+1} \frac 1 i = \sum_{i=1}^{n} \frac 1 i + \frac 1 {n+1}
$$
Assume 
$$
x_0 = \frac p q - \sum_{i=1}^{n} \frac 1 i \lt \frac 1 {n+1}
$$
If $x_0=0$ trivial case, if $x \ne 0$, Then we can find coprime integer $a$ and $b$ that
$$
x_0 = \frac a b \lt \frac 1 {n+1}
$$
Finally we decomposite $\frac a b$, there must exist an integer $m_0$, where $m_0 \gt n$ and
$$
\frac 1 {m_0+1} \le \frac a b \lt \frac 1 {m_0}\\
$$
Then let
$$
x_1 = \frac a b - \frac 1 {m_0+1} = \frac {am_0+a-b}{b(m_0+1)}
$$
Since
$$
x_1 < \frac 1 {m_0} - \frac 1 {m_0+1} < \frac 1 {m_0+1}
$$
So we can repeat this step.
And from $\frac a b < \frac 1 {m_0}$, we have:
$$
am_0 < b\\
am_0 - b < 0\\
am_0 + a - b < a
$$
So the numerator of $x_i$ is strictly decreasing, so we can find $x_k = 0$ in no more than $a$ steps.
Finally
$$
\frac p q = \sum_{i=1}^n \frac 1 i + \sum_{i=0}^{k-1} \frac 1 {m_i}
$$
A: This is the so-called greedy algorithm for decomposing fractions into unit fractions. Here, a unit fraction is a fraction of the form $\frac{1}{n}$. The algorithm dates back to 1202 and is due to Fibonacci.
The reason why the algorithm terminates is that the numerators of $\alpha_1, \alpha_2 \ldots \alpha_k \ldots $ are strictly decreasing as $k$ increases: In every step we decompose a rational number $\frac{p}{q}$ as
$\underbrace{\frac{p}{q}}_{\alpha_k} = \frac{1}{s+1} + \underbrace{\frac{p - r}{q(s+1)}}_{\alpha_{k+1}}$
for some $s$ (which is chosen to be the maximal one such that this identity will hold).
Eventually we will reach an $\alpha_k$ which has denumerator $1$.
