Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $x\in\mathbb{Q}$ with $x>0$.

Prove that we can find $n\in\mathbb{N}^*$ and distinct $a_1,...,a_n \in \mathbb{N}^*$ such that $$x=\sum_{k=1}^n{\frac{1}{a_k}}$$

share|improve this question
6  
Seen this? –  J. M. Oct 12 '11 at 1:18
    
See this also. –  J. M. Oct 12 '11 at 1:40

1 Answer 1

up vote 13 down vote accepted

Any rational number $0 < x < 1$ possesses a so-called Egyptian fraction decomposition, which writes $x$ as a sum of fractions with unit numerators. One constructive proof is to use a "greedy" algorithm, which keeps subtracting off the unit fractions of the form $\dfrac1{\lceil 1/x\rceil}$.

Here's some Mathematica code demonstrating the greedy approach for $\dfrac{21}{23}$:

f = 21/23; l = {};
While[f != 0, l = {l, p = Ceiling[1/f]}; f -= 1/p;];
Flatten[l]

{2, 3, 13, 359, 644046}

This says that

$$\frac{21}{23}=\frac12+\frac13+\frac1{13}+\frac1{359}+\frac1{644046}$$

This is a very naïve method, as there are other algorithms that yield unit fractions with tinier denominators. For the purposes of this question, it suffices to prove that the algorithm halts. As mentioned here (the proof is attributed to Fibonacci), if we let $m=\lceil 1/x \rceil$, then we always have the bracketing $\dfrac1{m} \leq x < \dfrac1{m-1}$. The numerator of $x-\dfrac1{m}$ can then be shown to be smaller than the numerator of $x$. Thus, the repeated application of the steps of reciprocation and subtraction results in numerators that go smaller and smaller, until the remainder after subtracting off unit fractions is zero.

See this for a nice bibliography of decomposition methods.

share|improve this answer
    
This is fine for $0\lt x\lt1$, but OP imposed no upper bound on $x$. –  Gerry Myerson Dec 25 '11 at 1:29
    
Well, there was... –  J. M. Dec 25 '11 at 4:04
    
you would think that by now I would know to look at edit history before making such a comment. Sorry. –  Gerry Myerson Dec 26 '11 at 4:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.