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

  • 0
    Sorry, edited!!2012-04-05
  • 6
    The magic words are "Egyptian fraction decomposition".2012-04-05
  • 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
    Not quite. $t_{n+1}$ can't be $\lceil(1 - 1/t_1 - \ldots - 1/t_n)^{-1}\rceil$ unless that $> t_n$.2012-04-05
  • 0
    @RobertIsrael: Yes, and that is eventually the case, right? If I made a mistake anywhere, please let me know.2012-04-05
  • 0
    @RobertIsrael: I edited the answer some minutes before your comment, so I'm not sure which version it concerns. If it concerns the first version, I have to apologize, since I was a bit hasty and forgot to put the $\max$ there. =)2012-04-05
  • 0
    It was the first version. Now it's OK, I think.2012-04-05
  • 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
    Thanks, I know this. Could you please show me how this will help? Thanks.2012-04-05
  • 2
    @John: Write $1$ as $\frac{1}{M+1}+\cdots+\frac{1}{M+1}$. Then replace each of the last $M$ fractions with $\frac{1}{M+1}+\frac{1}{(M+1)(M+2)}$. Continue doing this: every time you have a repeated fraction, you can replace the second one with a sum of two fractions with strictly larger denominator. Show that this will eventually terminate, and you will have a decomposition that has no repeated denominators, and all denominators are larger than $M$.2012-04-05
  • 0
    I taught on your comment for a while, but I couldn't figure out how it would work. would you please be more specific? Thanks again.2012-04-05
  • 1
    @John Tesh: I hope the example I added clearified it; if not, I'm afraid it's going to have to wait (I'm on my way out).2012-04-05
  • 0
    That's Ok, I got it. Thanks.2012-04-06