Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?
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
I thought the idea for naming some "fundamental" solutions, from yesterday, was pretty good. I wrote a program to do that. I wanted to show what can happen if the target number is not squarefree. In the following output, $x^2 - 5 y^2 = 121,$ one out of three $(x,y)$ is just $11$ times a pair that solves $x^2 - 5 y^2 = 1.$
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
x^2 - 5 y^2 = 121
x: 11 y: 0 ratio: 0 fundamental
x: 21 y: 8 ratio: 0.380952 fundamental
x: 29 y: 12 ratio: 0.413793 fundamental
x: 99 y: 44 ratio: 0.444444
x: 349 y: 156 ratio: 0.446991
x: 501 y: 224 ratio: 0.447106
x: 1771 y: 792 ratio: 0.447205
x: 6261 y: 2800 ratio: 0.447213
x: 8989 y: 4020 ratio: 0.447213
x: 31779 y: 14212 ratio: 0.447214
x: 112349 y: 50244 ratio: 0.447214
x: 161301 y: 72136 ratio: 0.447214
x: 570251 y: 255024 ratio: 0.447214
x: 2016021 y: 901592 ratio: 0.447214
x: 2894429 y: 1294428 ratio: 0.447214
x: 10232739 y: 4576220 ratio: 0.447214
x^2 - 5 y^2 = 121
jagy@phobeusjunior:~$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Why not, here is $x^2 - 5 y^2 = -121.$
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
x^2 - 5 y^2 = -121
x: 2 y: 5 ratio: 2.5 fundamental
x: 22 y: 11 ratio: 0.5 fundamental
x: 82 y: 37 ratio: 0.45122 fundamental
x: 118 y: 53 ratio: 0.449153
x: 418 y: 187 ratio: 0.447368
x: 1478 y: 661 ratio: 0.447226
x: 2122 y: 949 ratio: 0.44722
x: 7502 y: 3355 ratio: 0.447214
x: 26522 y: 11861 ratio: 0.447214
x: 38078 y: 17029 ratio: 0.447214
x: 134618 y: 60203 ratio: 0.447214
x: 475918 y: 212837 ratio: 0.447214
x: 683282 y: 305573 ratio: 0.447214
x: 2415622 y: 1080299 ratio: 0.447214
x: 8540002 y: 3819205 ratio: 0.447214
x: 12260998 y: 5483285 ratio: 0.447214
x^2 - 5 y^2 = -121
jagy@phobeusjunior:~$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Here is a good pair, $x^2 - 11 y^2 = 14$ and then $x^2 - 11 y^2 = 350 = 14 \cdot 25.$
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
x^2 - 11 y^2 = 14
Wed Mar 30 11:32:36 PDT 2016
x: 5 y: 1 ratio: 0.2 fundamental
x: 17 y: 5 ratio: 0.294118 fundamental
x: 83 y: 25 ratio: 0.301205
x: 335 y: 101 ratio: 0.301493
x: 1655 y: 499 ratio: 0.301511
x: 6683 y: 2015 ratio: 0.301511
x: 33017 y: 9955 ratio: 0.301511
x: 133325 y: 40199 ratio: 0.301511
x: 658685 y: 198601 ratio: 0.301511
x: 2659817 y: 801965 ratio: 0.301511
x: 13140683 y: 3962065 ratio: 0.301511
Wed Mar 30 11:32:56 PDT 2016
x^2 - 11 y^2 = 14
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
x^2 - 11 y^2 = 350
Wed Mar 30 11:29:54 PDT 2016
x: 19 y: 1 ratio: 0.0526316 fundamental
x: 25 y: 5 ratio: 0.2 fundamental
x: 41 y: 11 ratio: 0.268293 fundamental
x: 47 y: 13 ratio: 0.276596 fundamental
x: 85 y: 25 ratio: 0.294118 fundamental
x: 157 y: 47 ratio: 0.299363 fundamental
x: 223 y: 67 ratio: 0.300448
x: 415 y: 125 ratio: 0.301205
x: 773 y: 233 ratio: 0.301423
x: 899 y: 271 ratio: 0.301446
x: 1675 y: 505 ratio: 0.301493
x: 3121 y: 941 ratio: 0.301506
x: 4441 y: 1339 ratio: 0.301509
x: 8275 y: 2495 ratio: 0.301511
x: 15419 y: 4649 ratio: 0.301511
x: 17933 y: 5407 ratio: 0.301511
x: 33415 y: 10075 ratio: 0.301511
x: 62263 y: 18773 ratio: 0.301511
x: 88597 y: 26713 ratio: 0.301511
x: 165085 y: 49775 ratio: 0.301511
x: 307607 y: 92747 ratio: 0.301511
x: 357761 y: 107869 ratio: 0.301511
x: 666625 y: 200995 ratio: 0.301511
x: 1242139 y: 374519 ratio: 0.301511
Wed Mar 30 11:29:55 PDT 2016
x^2 - 11 y^2 = 350
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=