# Understanding Graham's proof of theorem on Unit Fractions.

In this paper by Ronald Graham, the theorem that every integer greater than 77 has a partition with the property that the sum of the reciprocals of the various "piles" in the partition is 1 (lovely!).

He gives a proof of this which is remarkably short but I find difficult to follow. He demonstrates that all the integers from 78 to 333 inclusive have such a representation and then demonstrates 2 transforms on a sum of reciprocals that add to 1 that retain this property, but which increase the sum of denominators from $$U$$ to $$2U+2$$ and $$2U+179$$.

He then essentially claims that by having a certain property (the above one) hold for all the integers from 78 to 333 and by knowing that the above transforms retain the property, it holds for all integers greater than 77. However, his method of explaining this is quite incomprehensible to me and appears to contain numerous arithmetic errors on top of this!

Can someone either give an alternative proof of the fact using what I've mentioned or simply explain Graham's argument, as it is a wonderful theorem?

• The "piles" in a partition are surprisingly called "parts". – Marc van Leeuwen Jan 16 at 14:39

You can prove this easily by strong induction. The base case of $$78\leq n\leq333$$ has been handled. Assume the theorem holds for all $$78\leq n\leq m$$, $$m\geq333$$. Then $$m+1=2k$$ or $$m+1=2k+1$$ for some natural number $$k$$.
Case $$m+1=2k$$: Let $$U=k-1$$. Then $$U\leq m$$ and $$U=(m-1)/2\geq(333-1)/2\geq78$$, so the theorem holds for $$U$$. Hence, the theorem holds for $$m+1=2U+2$$.
Case $$m+1=2k+1$$: Let $$U=k-89$$. Then $$U\leq m$$ and $$U=(m-178)/2\geq(333-178)/2=77\frac12$$. Because $$U$$ is an integer, $$U\geq78$$, so the theorem holds for $$U$$. Hence, the theorem holds for $$m+1=2U+179$$.