Is this condition sufficient for an egyptian fraction to be greedy

61 Views Asked by At

An egyptian fraction

$\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} ...$

is greedy if each $a_n$ is as small as possible, given its predecessors. Every real number between 0 and 1 has exactly one representation as a greedy egyptian fraction.

(similar to continued fractions, for rational numbers this sequence is finite; for irrational numbers it's infinite)

Eg. $\frac12 + \frac1{12}$ is greedy; $\frac13 + \frac14$ is not

Clearly, for an egyptian fraction to be greedy it is necessary for each $a_{n+1}$ to be greater than $a_n \times (a_{n}-1)$ but is it also sufficient?

1

There are 1 best solutions below

1
On

I would say it is sufficient too. Assume that we have a sequence $\{a_n\}$ satisfying the property $a_{n+1}\geq a_n\cdot (a_n-1)+1$. Our number is: $$ a=\sum_{n=0}^\infty \frac{1}{a_n} $$ Assume this egyptian fraction is not greedy. Then, there exists an $N$ such that we didn't choose $a_N$ in an appropiate way, that is, we could have written $a_N-1$ because: $$ \sum_{n=N}^\infty \frac{1}{a_n} \geq \frac{1}{a_N-1} $$ Well, then consider $b_m=\frac{1}{a_N-1}-\sum_{n=N}^{m} \frac{1}{a_n}$. Let's see that $b_m\geq \frac{1}{a_m\cdot(a_m-1)}>0$ for every $m$ to generate a contradiction. We will prove it by induction. The base case: $$ b_N=\frac{1}{a_N-1}-\frac{1}{a_N}=\frac{1}{a_N\cdot (a_N-1)} $$ Now, suppose it is true that $b_m\geq \frac{1}{a_m\cdot (a_m-1)}$. Let's prove it for $b_{m+1}$: $$ b_{m+1}=\frac{1}{a_N-1}-\sum_{n=N}^{m+1} \frac{1}{a_n}=b_m-\frac{1}{a_{m+1}}$$ $$ \geq \frac{1}{a_m\cdot (a_m-1)}-\frac{1}{a_{m+1}}\geq \frac{1}{a_{m+1}-1}-\frac{1}{a_{m+1}}=\frac{1}{(a_{m+1}-1)a_{m+1}} $$ where we have used the induction hypothesis in the first inequality and the greedy assumption $a_{m+1}-1\geq a_m\cdot (a_m-1)$ in the second inequality.

Then $b_m\geq 0$ for every $m$. This clearly creates a contradiction with the initial hypothesis that the egyptian fraction is not greedy.