(0)貪欲法

ある正の分数を\(\frac{y}{x}\)として、
\[ \sum_{k=2}^{n}\frac{1}{k}\leq\frac{x}{y} \] を満たす最大の\(n\)を求め、
\[ \frac{x}{y}=\sum_{k=2}^{n}\frac{1}{k}+\left(\frac{x}{y}-\sum_{k=2}^{n}\frac{1}{k}\right) \] として、第1項の\(\sum_{k=2}^{n}\frac{1}{k}\)を求めるエジプト式分数に加え、第2項の\(\frac{x}{y}-\sum_{k=2}^{n}\frac{1}{k}\)を\(\frac{a}{b}\)とおいてこれをエジプト式分数で表す。
また、このとき、最大の\(n\)を求めたので、
\[ \frac{x}{y}<\sum_{k=2}^{n+1}\frac{1}{k} \] となり、
\begin{align*} \frac{a}{b} & =\frac{x}{y}-\sum_{k=2}^{n}\frac{1}{k}\\ & <\frac{1}{n+1} \end{align*} となる。
天井関数と剰余の関係
\[ \alpha=\beta\left\lceil \frac{\alpha}{\beta}\right\rceil +\mod\left(\alpha,-\beta\right) \] より、\(\frac{a}{b}\)は真分数なので、
\begin{align*} \frac{a}{b} & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }-\frac{\mod\left(b,-a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\\ & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }+\frac{\mod\left(-b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\\ & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }+\frac{a\left|\sgn\mod\left(b,a\right)\right|-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\\ & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }+\frac{a-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil } \end{align*} となる。
第1項をエジプト式分数に加え、第2項は真分数になるので\(\frac{a-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\)をもう一度\(\frac{a}{b}\)とおいてこれを0になるまで繰り返せばいい。
これは
\[ \frac{1}{m}<\frac{a}{b} \] となる最小の\(m\)を求めているのと同じであり\(m=\frac{1}{\left\lceil \frac{b}{a}\right\rceil }\)となる。
\(\frac{a}{b}\)は真分数なので
\[ \frac{1}{\left\lceil \frac{b}{a}\right\rceil }>\frac{a-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil } \] となり、単位分数\(\boldsymbol{\frac{1}{\left\lceil \frac{b}{a}\right\rceil }}\)が再度加わることはないので重複はない。
また
\begin{align*} \frac{1}{\left\lceil \frac{b}{a}\right\rceil } & <\frac{1}{\frac{b}{a}}\\ & =\frac{a}{b}\\ & <\frac{1}{n+1} \end{align*} より、先に求めたエジプト式分数の単位分数と重複するとこはない。
また分子だけを考えると、\(a\rightarrow a-\mod\left(b,a\right)\)となり負にはならずに小さくなっていき、いずれ0になるので有限個の単位分数で表せる。

(0)-2

ある正の分数を\(\frac{a}{b}\)とする。
\(a=1\)のとき、
\begin{align*} \frac{1}{b} & =\frac{b+1}{b\left(b+1\right)}\\ & =\frac{1}{b+1}+\frac{1}{b\left(b+1\right)} \end{align*} となるので、\(2\leq b\)のときエジプト式分数で表せる。
\(b=1\)のときは\(\frac{1}{2}\)が重複してしまうので、もう一度適用して、
\begin{align*} 1 & =\frac{1}{2}+\frac{1}{2}\\ & =\frac{1}{2}+\frac{1}{2+1}+\frac{1}{2\left(2+1\right)}\\ & =\frac{1}{2}+\frac{1}{3}+\frac{1}{6} \end{align*} とすればいい。
これを繰り返し使えば任意\(m\)以降の単位分数で表すことが出来る。
すなわち、
\[ \frac{1}{b}=\frac{1}{m}+\cdots \] とできる。
\(a=k\)のときエジプト式分数で表せると仮定すると、\(a=k+1\)のとき、
\[ \frac{k+1}{b}=\frac{k}{b}+\frac{1}{b} \] となるが、\(\frac{k}{b}\)は仮定よりエジプト式分数で表され、有限個の単位分数の和なので、\(\frac{1}{b}\)を重複しないようにそれ以降のエジプト式分数で表せばいい。
これより、\(\frac{k+1}{b}\)はエジプト式分数で表せるので、数学的帰納法より任意の正の分数はエジプト式分数で表せる。