Possible Duplicate:
Prove that any rational can be expressed in the form $\sum\limits_{k=1}^n{\frac{1}{a_k}}$, $a_k\in\mathbb N^*$
Can anyone help me with this problem? It's a little strange:
Let $M$ be a natural number. Prove that we can write $1=\frac{1}{t_1}+\cdots+\frac{1}{t_n}$ such that all $t_i$'s are distinct natural numbers greater than $M$.
On
Hint. $$\frac{1}{n} +\frac{1}{n} = \frac{1}{n} + \frac{1}{n+1}+\frac{1}{n(n+1)}.$$
For example, say $N=3$. Then we can write: $$\begin{align*} 1 &= \frac{1}{4}+\frac{1}{4} + \frac{1}{4}+\frac{1}{4}\\ &= \frac{1}{4} + \frac{1}{5}+\frac{1}{20} + \frac{1}{5}+\frac{1}{20}+\frac{1}{5}+\frac{1}{20}\\ &= \frac{1}{4}+\frac{1}{5}+\frac{1}{20} + \frac{1}{6}+\frac{1}{30} + \frac{1}{21}+\frac{1}{420} + \frac{1}{6}+\frac{1}{30} + \frac{1}{21}+\frac{1}{420}\\ &= \frac{1}{4}+\frac{1}{5}+\frac{1}{20}+\frac{1}{6}+\frac{1}{30}+\frac{1}{21}+\frac{1}{420} + \frac{1}{7}+\frac{1}{42} + \frac{1}{31}\\ &\qquad\mathop{+}\frac{1}{930} + \frac{1}{22}+\frac{1}{462} + \frac{1}{421}+\frac{1}{176820}\\ &= \frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{20}+\frac{1}{21}+\frac{1}{22}+\frac{1}{30}+\frac{1}{31}+\frac{1}{42}\\ &\qquad\mathop{+}\frac{1}{420}+\frac{1}{421}+\frac{1}{462}+\frac{1}{930}+\frac{1}{176820}. \end{align*}$$
Another possibility is to use Fibonacci's Greedy algorithm.
Start with $t_1=M+1$ and then proceed inductively: define $t_{n+1}$ to be the smallest natural number greater than $t_n$ for which $$\frac1{t_1}+\frac1{t_2}+\cdots+\frac1{t_{n+1}}\le1.$$ In other words: $$\begin{array}{rl}t_1:=&M+1\\t_{n+1}:=&\min\lbrace m\in\mathbb N|\text{ }m>t_n\text{ and } \frac1{t_1}+\frac1{t_2}+\cdots+\frac1{t_{n}}+\frac1m\le1\rbrace=\\=&\max\left\lbrace\left\lceil(1-\frac1{t_1}-\frac1{t_2}-\cdots-\frac1{t_{n}})^{-1}\right\rceil,t_n+1\right\rbrace\end{array}$$ This will terminate after finitely many steps because you can prove that the numerators of the fraction $1-\frac1{t_1}-\frac1{t_2}-\cdots-\frac1{t_n}$ begin decreasing eventually. This is also known as Fibonacci's algorithm.