5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Have a look at en.wikipedia.org/wiki/Egyptian_fraction $\endgroup$ – G Cab Sep 13 '16 at 12:40
  • 1
    $\begingroup$ Your title says "set of integer $n$". Does this imply that any $n$ should occur at most once (as in a set)? Your algorithm does not ensure this for $n=1$ (though it does for all larger $n$). $\endgroup$ – Marc van Leeuwen Sep 13 '16 at 12:40
  • $\begingroup$ True, I should have added the comment that $N_i>N_(i-1)$. It doesn't make much of a difference for the problem though. $\endgroup$ – Lotte Sep 13 '16 at 13:58
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's the way to go! Thank you very much! $\endgroup$ – Lotte Sep 13 '16 at 13:56
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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 = \frac p q - \sum_{i=1}^{n} \frac 1 i \lt \frac 1 {n+1} $$

If $x=0$ trivial case, if $x \ne 0$, Then we can find coprime integer $a$ and $b$ that

$$ x = \frac a b \lt \frac 1 {n+1} $$

Finally we decomposite $\frac a b$, there must exist an integer $m$, where $m \gt n$ and

$$ \frac 1 {m+1} \le \frac a b \lt \frac 1 m\\ $$

Then let $$ y = \frac a b - \frac 1 {m+1} = \frac {am+a-b}{b(m+1)} $$

From $\frac a b < \frac 1 m$, we have:

$$ am < b\\ am - b < 0\\ am + a - b < a $$

We saw that the numerator of $x$ and $y$ is strictly decreasing, and $y < \frac 1 m - \frac 1 {m+1} < \frac 1 {m+1}$, so we can repeat this step until the numerator goes to 0 in no more than $a$ steps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.