Proof of Fibonacci's algorithm for Egyptian fractions

In my previous post I described Fibonacci's algorithm for Egyptian fractions. Here I want to go through the proof of why this algorithm always works as I think it is rather neat. This is exercise 1.2.2 of John Stillwell's 'Elements of Number Theory' and I wouldn't have got very far without being pushed in the right direction by this exercise. Note, though, that there are no solutions to the exercises in the book, so this is my own solution.

Let a, b and q be natural numbers such that
$$\frac{1}{q+1}<\frac{b}{a}<\frac{1}{q}   ...(1)$$
then 1/q is at most 1 and so it follows that b<a as we saw previously. It also follows from (1) that 1/(q+1) is the largest unit fraction less than b/a since 1/(q+1) and 1/q straddle b/a. Now
$$\frac{b}{a}-\frac{1}{q+1}=\frac{b(q+1)-a}{a(q+1)}   ...(2)$$
so let
$$b'=b(q+1)-a   ...(3)$$
and
$$a'=a(q+1)   ...(4)$$
First we show that b'>0. From (1) we have that
$$\frac{b}{a}>\frac{1}{q+1}\Leftrightarrow b(q+1)>a\Leftrightarrow b(q+1)-a>0\Leftrightarrow b'>0$$
as required. Next we show that b'<b. Also from (1) we have
$$\frac{b}{a}<\frac{1}{q}\Leftrightarrow bq<a\Leftrightarrow bq+b-a<b\Leftrightarrow b(q+1)-a<b\Leftrightarrow b'<b$$
as required. It also follows from the definitions of a' and b' and the fact that b'>0 that a' and b' are natural numbers.

Finally we show that b'<a'. From (2), (3) and (4) we have
$$\frac{b}{a}-\frac{1}{q+1}=\frac{b'}{a'}   ...(5)$$
and so
$$\frac{b}{a}<1\Leftrightarrow \frac{b}{a}-\frac{1}{q+1}=\frac{b'}{a'}<1-\frac{1}{q+1}=\frac{q}{q+1}<1\Leftrightarrow \frac{b'}{a'}<1$$

We now demonstrate why Fibonacci's algorithm always works. Let b₁/a₁ be the initial fraction such that
$$\frac{1}{q_{1}+1}<\frac{b_{1}}{a_{1}}<\frac{1}{q_{1}}   ...(6)$$
where a₁, b₁, and q₁ are natural numbers, then 1/(q₁+1) is the largest possible unit fraction less than b₁/a₁. Thus, on the first iteration, on subtracting 1/(q₁+1) from b₁/a₁ we obtain the fraction
$$\frac{b_{1}}{a_{1}}-\frac{1}{q_{1}+1}=\frac{b_{2}}{a_{2}}   ...(7)$$
where a₂ and b₂ are natural numbers and b₂<b₁ and b₂<a₂. On the second iteration we find q₂ such that
$$\frac{1}{q_{2}+1}<\frac{b_{2}}{a_{2}}<\frac{1}{q_{2}}   ...(8)$$
then 1/(q₂+1) is the largest possible unit fraction less than b₂/a₂. Thus, on the second iteration, on subtracting 1/(q₂+1) from b₂/a₂ we obtain the fraction
$$\frac{b_{2}}{a_{2}}-\frac{1}{q_{2}+1}=\frac{b_{3}}{a_{3}}   ...(9)$$
where a₃ and b₃ are natural numbers and b₃<b₂<b₁ and b₃<a₃ and so on.

Hence, by a process of descent we must eventually end up with a b_j=1 for some j, and we have from (7), (9) etc
$$\frac{b_{1}}{a_{1}}=\frac{1}{q_{1}+1}+\frac{1}{q_{2}+1}+ ... +\frac{1}{a_{j}}   ...(10)$$

as expected. Phew! That was tricky to write out correctly!