Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?
If $d \ne 0$ is a non-square integer, and $(u,v)$ is an integer solution to the Pell equation $$ X^2 - dY^2 = 1, \tag{$\star$} $$ then each solution $(x_i,y_i)$ can be recursively calculated using the formulas \begin{align} x_{n+1} &= ux_n + dvy_n, \\ y_{n+1} &= vx_n + uy_n\tag1 \end{align} n.b. If $(u,v)$ is not the fundamental solution to ($\star$), the recursion still works, though you will instead get $(x_{n+m},y_{n+m})$ for some integer $m$ determined by which solution $(u,v)$ actually is. Thus you can always determine a larger solution to ($\star$), though not necessarily the next largest solution, using only a single solution $(x_n,y_n)$ and the recursion \begin{align} x_{n+1} &= x_n^2 + dy_n^2, \\ y_{n+1} &= 2x_ny_n\tag2 \end{align}
QUESTION: Considering the equation $$ X^2 - dY^2 = k, \qquad k \ne 1, $$ is there a similar simple recursion to determine $(x_{n+1},y_{n+1})$ knowing only $(x_n,y_n)$ [and possibly, though not necessarily, one other solution $(u,v)$]?
With $d=6$ and $k=3$, I tried applying the recursion for $X^2-6Y^2=1$ to the fundamental solution $(3,1)$ of the equation $X^2-6Y^2=3$, and ended up with a solution to the equation $X^2-6Y^2=9$. Since $9=3^2=k^2$, I feel like there might be just a small adjustment to be made to the recursion, to compensate for $k \ne 1$, but I haven't found it.
Yes. The recursion is just the Brahmagupta-Fibonacci Identity in disguise,
$$(u x + d v y)^2 - d(v x + u y)^2 = (u^2 - d v^2) (x^2 - d y^2) = k$$
The coefficients $u,v$ are determined by the fundamental solution to $u^2 - d v^2=1$. And you simply plug in initial $x_1,y_1$ to $x^2 - d y^2 = k$, whether $k=1$ or not, to get subsequent ones. For ex, the universal recursion for $d = 6$,
$$x^2-6y^2 = k$$
is given by,
$$x_{n+1} = \color{blue}5\,x_n + 12y_n$$
$$y_{n+1} = \color{blue}2\,x_n + 5y_n$$
which uses uses $\color{blue}5^2-6\times\color{blue}2^2=1$. To apply for $k=3$, using $3^2-6\times1^2=3$, hence initial $x_1,y_1 = 3,1$, we get,
$$x_2, y_2 = 27,11$$
so $27^2-6\times11^2=3$, and so on.
Make this an answer. It turns out that, using the recursion you describe, the set of all solutions to $x^2 - dy^2 = k$ split into a small number of orbits. The cleanest way to locate the "seed" values for the different orbits is Conway's topograph method. In essence, $k=\pm 1$ give the smallest number of orbits, namely one. Not much worse for $k $ prime. The number of orbits increases with the number of prime factors of $k,$ as long as the primes $p$ satisfy $(d|p)= 1.$ There is no truly easy way to find all the necessary seed values when $k$ is such a composite number.
Example: $11$ and $19$ are primes represented by $x^2 - 5 y^2,$ and $11 \cdot 19 = 209.$ The solutions to $x^2 - 5 y^2 = 209$ need more than one orbit under your recursion. We can make it worse by throwing in $29,$ and solving $x^2 - 5 y^2 = 6061.$ The only reason it is not bad is that we have class number one.
Here are the 8 seed pairs I get for $x^2 - 5 y^2 = 6061.$ If you apply the mapping $$ (x,y) \mapsto (9x + 20y, 4x + 9y) $$ you get a pair with larger entries than any of these 8. A proof that these eight really are enough takes more work, although I have done plenty of these and think the list is complete.
x: 79 y: 6
x: 81 y: 10
x: 129 y: 46
x: 159 y: 62
x: 191 y: 78
x: 241 y: 102
x: 529 y: 234
x: 591 y: 262
Why not? Here is a longer list, including pairs from the same orbits:
x: 79 y: 6
x: 81 y: 10
x: 129 y: 46
x: 159 y: 62
x: 191 y: 78
x: 241 y: 102
x: 529 y: 234
x: 591 y: 262
x: 831 y: 370
x: 929 y: 414
x: 2081 y: 930
x: 2671 y: 1194
x: 3279 y: 1466
x: 4209 y: 1882
x: 9441 y: 4222
x: 10559 y: 4722
x: 14879 y: 6654
x: 16641 y: 7442
x: 37329 y: 16694
x: 47919 y: 21430
x: 58831 y: 26310
x: 75521 y: 33774
x: 169409 y: 75762
x: 189471 y: 84734
x: 266991 y: 119402
x: 298609 y: 133542
x: 669841 y: 299562
x: 859871 y: 384546
x: 1055679 y: 472114
x: 1355169 y: 606050
x: 3039921 y: 1359494
x: 3399919 y: 1520490
x: 4790959 y: 2142582
x: 5358321 y: 2396314
x: 12019809 y: 5375422
x: 15429759 y: 6900398
x: 18943391 y: 8471742
x: 24317521 y: 10875126
EDIT: it is possible to make a definition of "fundamental solution" that fits well into the group action on the form. As $x,y$ get large, we know that $y/x \approx 1/\sqrt 5 \approx 0.447213596.$ For large $x,y,$ we also know we can back up the solution by the inverse mapping, $$ (x,y) \mapsto (9x-20y, -4x+9y) $$ and get another solution with positive $x,y.$ So, in a nod to Hurwitz, why not call a solution fundamental if either $9x-20y < 0$ or $-4x+9y < 0?$ That way, a solution is fundamental if either $y/x < 0.45$ or $y/x > 0.4444444.$ Below I list the first few solutions with the ratio $y/x$ in decimal. If that decimal is close to $0.44721$ then the solution is not fundamental. This can be upgraded to an "effective" set of bounds on $x,y$ to show that the set of fundamental solutions is finite. Good.
x: 79 y: 6 ratio: 0.0759494 fundamental
x: 81 y: 10 ratio: 0.123457 fundamental
x: 129 y: 46 ratio: 0.356589 fundamental
x: 159 y: 62 ratio: 0.389937 fundamental
x: 191 y: 78 ratio: 0.408377 fundamental
x: 241 y: 102 ratio: 0.423237 fundamental
x: 529 y: 234 ratio: 0.442344 fundamental
x: 591 y: 262 ratio: 0.443316 fundamental
x: 831 y: 370 ratio: 0.445247
x: 929 y: 414 ratio: 0.44564
x: 2081 y: 930 ratio: 0.446901
x: 2671 y: 1194 ratio: 0.447024
x: 3279 y: 1466 ratio: 0.447088
x: 4209 y: 1882 ratio: 0.447137
x: 9441 y: 4222 ratio: 0.447198
x: 10559 y: 4722 ratio: 0.447201
x: 14879 y: 6654 ratio: 0.447207
x: 16641 y: 7442 ratio: 0.447209
x: 37329 y: 16694 ratio: 0.447213
x: 47919 y: 21430 ratio: 0.447213
x: 58831 y: 26310 ratio: 0.447213
x: 75521 y: 33774 ratio: 0.447213
x: 169409 y: 75762 ratio: 0.447214
x: 189471 y: 84734 ratio: 0.447214
I did the same run for $x^2 - 5 y^2 = -6061.$ Here the ratio $y/x$ decreases until it gets lower than $0.45$
x: 8 y: 35 ratio: 4.375 fundamental
x: 28 y: 37 ratio: 1.32143 fundamental
x: 112 y: 61 ratio: 0.544643 fundamental
x: 128 y: 67 ratio: 0.523438 fundamental
x: 188 y: 91 ratio: 0.484043 fundamental
x: 212 y: 101 ratio: 0.476415 fundamental
x: 488 y: 221 ratio: 0.452869 fundamental
x: 628 y: 283 ratio: 0.450637 fundamental
x: 772 y: 347 ratio: 0.449482
x: 992 y: 445 ratio: 0.448589
x: 2228 y: 997 ratio: 0.447487
x: 2492 y: 1115 ratio: 0.447432
x: 3512 y: 1571 ratio: 0.447323
x: 3928 y: 1757 ratio: 0.447301
x: 8812 y: 3941 ratio: 0.447231
x: 11312 y: 5059 ratio: 0.447224
x: 13888 y: 6211 ratio: 0.447221
x: 17828 y: 7973 ratio: 0.447218
x: 39992 y: 17885 ratio: 0.447214
x: 44728 y: 20003 ratio: 0.447214
x: 63028 y: 28187 ratio: 0.447214
x: 70492 y: 31525 ratio: 0.447214
x: 158128 y: 70717 ratio: 0.447214
x: 202988 y: 90779 ratio: 0.447214