8
$\begingroup$

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$.

  • 1
    Btw, Ronald Graham has an awesome [paper](http://www.math.ucsd.edu/~ronspubs/64_01_unit_fractions.pdf) about egyptian fractions in case you're interested.2012-04-05

2 Answers 2

4

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.

  • 0
    @RobertIsrael: OK, thanks.2012-04-05
14

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*}$

  • 0
    That's Ok, I got it. Thanks.2012-04-06