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.
 A: 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=1}^\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 adding $1$ and
dividing by $3$.
