Upper Limit of Number of Unit Fractions to express Proper Fraction from Greedy Algorithm

Theorem

Let $\dfrac p q$ denote a proper fraction expressed in canonical form.

Then $\dfrac p q$ is expressed using no more than $p$ unit fractions.

Let $\dfrac {x_k} {y_k}$ and $\dfrac {x_{k + 1} } {y_{k + 1} }$ be consecutive stages of the calculation of the unit fractions accordingly:

$\dfrac {x_k} {y_k} - \dfrac 1 {\ceiling {y_n / x_n} } = \dfrac {x_{k + 1} } {y_{k + 1} }$

$\dfrac {x_{k + 1} } {y_{k + 1} } = \dfrac {\paren {-y_k} \bmod {x_k} } {y_k \ceiling {y_k / x_k} }$

It is established during the processing of Fibonacci's Greedy Algorithm that:

$\paren {-y_k} \bmod {x_k} < x_k$

Hence successive numerators decrease by at least $1$.

Hence there can be no more unit fractions than there are natural numbers between $1$ and $p$.

Hence the result.

$\blacksquare$

This result was proved by James Joseph Sylvester in $1880$.