November 22nd
Today I learned the finish for the fact that the greedy algorithm for Egyptian fractions works. Suppose that we want to write a reduced, positive rational $p/q$ as sum of rationals of the form $1/n.$ Without loss of generality $p/q$; else we just have to subtract $1/1$ a whole bunch of times.
Now, the greedy algorithm chooses the largest possible $1/n$ which will fit and then continues. Indeed, we want to use the integer $n$ such that\[\frac1n\le\frac pq \lt \frac1{n-1}.\]In other words, $n\ge q/p \gt n-1,$ so $n=\ceil{q/p}.$ So basically, the algorithm (formally) computes $\ceil{q/p}$ and then recursively continues with\[\frac pq-\frac1{\ceil{q/p}}.\]We'd like to show that this algorithm must terminate. For this, a monovariant or an invariant would be useful because terms in the above are in $\NN,$ so well-order would finish. Well, we claim that the numerator is strictly smaller in the new fraction when reduced; this will finish because there are only finitely many possible numerators to go through, so termination would be forced. Indeed, the new fraction is\[\frac{p\ceil{q/p}-q}{q\ceil{q/p}}.\]
After reducing, the numerator is no more than $p\ceil{q/p}-q,$ so it remains to show that this is less than $p.$ (In fact, it might be equal, so the inequality $p\ceil{q/p}-q \lt p$ had better holds regardless.) Explicitly, we need\[p\ceil{\frac qp}-q \lt p.\]Dividing by $p,$ this reads\[\ceil{\frac qp}-\frac qp \lt 1,\]which is true by the definition of ceiling. The ceiling is the smallest positive integer above $q/p,$ so if the left-hand side were at least $1,$ then we could select $\ceil{q/p}-1$ as a smaller integer above $q/p,$ contradicting.
As an aside, we can also notice that the inequality is\[p\ceil{q/p} \lt q+p.\]The common number-theoretic way to deal with floors and ceilings is to note that $p\ceil{q/p}$ is the smallest multiple of $p$ above $q.$ Well, there's a multiple of $q$ somewhere in $[q,q+p)$ because this fully covers $\ZZ/p\ZZ,$ so the above inequality follows.