# Numbers $p-\sqrt{q}$ having regular egyptian fraction expansions?

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

$$x_0=\frac{1}{a_0}+\frac{1}{a_1}+\frac{1}{a_2}+\dots$$

$a_n$ are positive integers and are defined:

$$x_n-\frac{1}{a_n}>0$$

$$x_n-\frac{1}{a_n-1}<0$$

And $x_n$ are defined:

$$x_{n+1}=x_n-\frac{1}{a_n}$$

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:

$$\frac{3-\sqrt{5}}{2}=2-\phi=\frac{1}{3}+\frac{1}{21}+\frac{1}{987}+\dots$$

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

$$3-\sqrt{7}=\frac{1}{3}+\frac{1}{48}+\frac{1}{12192}+\dots$$

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

$$4-\frac{1}{3}-\sqrt{11}=\frac{1}{3}+\frac{1}{60}+\frac{1}{23880}+\dots$$

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.

• In the first expansion, for $2-\phi$, should the third fraction be $1/987$, not $1/981$? – John Bentin Sep 1 '16 at 5:35
• @JohnBentin, you are right. I edited – Yuriy S Sep 1 '16 at 6:39
• 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. – sometempname Sep 13 '16 at 3:05
• However, this doesn't cover all types of interesting quadratic integers, for example: $$4 - \sqrt{13} = \frac13 + \frac1{17} + \frac1{437} + \frac1{283104} + \dots.$$ – sometempname Sep 13 '16 at 3:06
• @sometempname, what is special about this number compared to the general relation in the answer below? – 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$.

• 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 – Yuriy S Sep 11 '16 at 8:26
• You're welcome. Sure, no rush (and somebody else may yet provide a reference or some other relevant information). – Noam D. Elkies Sep 11 '16 at 14:20