I remind that the greedy algorithm for egyptian fraction expansion for a positive number $x_0 <1$ goes like this:


$a_n$ are positive integers and are defined:



And $x_n$ are defined:


This expansion may rival the simple continued fractions in its importance to the number theory. It's unique for every number and terminating if and only if $x_0$ is rational.

I thought almost no regular GA EF expansions for 'simple' irrationals were known.

The only example I knew from this answer was:


Where the denominators are $2^n$th Fibonacci numbers.

But it turns out that many numbers of the form $p-\sqrt{q}$ I tried have GA EF expansion with a regular pattern, described by $2^n$th terms of a linear second order recurrence.

I summarize the examples below:

$$3-2 \sqrt{2}=\frac{1}{6}+\frac{1}{204}+\frac{1}{235416}+\dots$$

Denominators are $2^n$th terms of the recurrence $A_n=34A_{n-1}-A_{n-2},~A_0=0,~A_1=6$. http://oeis.org/A082405

$$4-2 \sqrt{3}=\frac{1}{2}+\frac{1}{28}+\frac{1}{5432}+\dots$$

Denominators are $2^n$th terms of the recurrence $A_n=14A_{n-1}-A_{n-2},~A_0=0,~A_1=2$. http://oeis.org/A011944


Denominators are $2^n$th terms of the recurrence $A_n=16A_{n-1}-A_{n-2},~A_0=0,~A_1=3$. http://oeis.org/A001080


Denominators are $2^n$th terms of the recurrence $A_n=20A_{n-1}-A_{n-2},~A_0=0,~A_1=3$. http://oeis.org/A001084

Is there a general pattern here? How to prove these conjectures?

I know that there is a deep connection between recurrences of this kind and square roots (i.e. Fibonacci numbers and the Golden Ratio), but I don't know what the actual connection is in this case.

  • $\begingroup$ In the first expansion, for $2-\phi$, should the third fraction be $1/987$, not $1/981$? $\endgroup$ – John Bentin Sep 1 '16 at 5:35
  • $\begingroup$ @JohnBentin, you are right. I edited $\endgroup$ – Yuriy S Sep 1 '16 at 6:39
  • $\begingroup$ This is just to give a reference. There are two papers of G. Stratemeyer from the 1930s (in German), that give the GA EF (aka Sylvester expansion) for fractions of the type $$ \frac{t}{u} - \sqrt{D}, $$ where $D>1$ is rational number that is not a square, and $t,u$ are integers (or half integers), that satisfy $$t^2 - u^2 D = 1. $$ This covers all of your cases, in a similar way to @Noam D. Elkies solution. With a little bit more work, it is possible to show the connection to linear recurrences. $\endgroup$ – sometempname Sep 13 '16 at 3:05
  • $\begingroup$ However, this doesn't cover all types of interesting quadratic integers, for example: $$4 - \sqrt{13} = \frac13 + \frac1{17} + \frac1{437} + \frac1{283104} + \dots.$$ $\endgroup$ – sometempname Sep 13 '16 at 3:06
  • $\begingroup$ @sometempname, what is special about this number compared to the general relation in the answer below? $\endgroup$ – Yuriy S Sep 13 '16 at 7:23

Suppose $u>1$. Then the numbers $c_n := u^n - u^{-n}$ satisfy the linear recurrence $$ c_{n+1} - (u+u^{-1}) c_n + c_{n-1} = 0. $$ Moreover, $$ \frac1{c_n} = \frac{u^n}{u^{2n}-1} = \frac1{u^n-1} - \frac1{u^{2n}-1}. $$ Hence the sum of the reciprocals of the $2^m$-th terms can be evaluted as a telescoping sum: $$ \sum_{m=1}^\infty \frac1{c_{2^m}} = \sum_{m=1}^\infty \frac1{u^{2^m}-1} - \frac1{u^{2^{m+1}}-1} = \frac1{u^2-1}. $$ Now suppose $u+u^{-1} = k > 2$. Then $c_1^2 + 4 = k^2$, so $c_1 = \sqrt{k^2-4}$, and the $a_n := c_n / c_1$ are polynomials in $k$: $$ (a_1, a_2, a_3, a_4, \ldots) = (1, k, k^2-1, k^3-2k, \ldots) $$ and we have $$ \sum_{m=1}^\infty \frac1{a_{2^m}} = \sqrt{k^2-4} \sum_{m=0}^\infty \frac1{c_{2^m}} = \frac{\sqrt{k^2-4}}{u^2-1} = \frac{k-\sqrt{k^2-4}}{2}. $$ This accounts for all your examples:

$k=3$ gives the Fibonacci sum;

$k=4$ gives the expansion of $2-\sqrt{3}$ multiplied by $2$;

$k=6$ gives the expansion of $3-2\sqrt{2}$;

$k=16$ gives an expansion of $8-3\sqrt{7}$, from which the expansion of $3-\sqrt{7}$ follows by adding $1$ and dividing by $3$; and

$k=20$ gives an expansion of $10 - 3\sqrt{11}$, from which the expansion of $4 - \frac13 - \sqrt{11}$ follows by again dding $1$ and dividing by $3$.

  • $\begingroup$ Telescoping sum. That's just great. Thank you for the explanation. I'll wait a little before awarding the bounty, I hope it's ok $\endgroup$ – Yuriy S Sep 11 '16 at 8:26
  • $\begingroup$ You're welcome. Sure, no rush (and somebody else may yet provide a reference or some other relevant information). $\endgroup$ – Noam D. Elkies Sep 11 '16 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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