N = (x^2 + y^2)/(1+xy) is a Square

If the number (a^2 + b^2)/(1+a*b)  with a,b integers is a positive 
integer, then it is a perfect square.  (The stipulation of *positive*
integer is required, because we have integers a=1, b=-2 such that 
(a^2 + b^2)/(1+ab) equals the integer -5, but this is not a perfect 
square.)  To prove this, first note that, for any positive integer 
N, if the equation 

                      x^2 + y^2
                      ---------  =  N
                       1 + xy

is an integer, with x > y (clearly x cannot y except when x=y=1), 
then we have the following polynomial with integer coefficients

                x^2 - (Ny)x + (y^2 - N)  = 0

The two roots of this equation x1 and x2 satisfy the relation

              x1 + x2 = Ny            x1 x2 = y^2 - N

Hence if (x1,y) is a solution, then so is (x2,y) where x2 = Ny - x1.
Also, since x1 exceeds y, we know that y exceeds x2, as is clear from
the right hand expression above.

Repeating this process, we have a strictly decreasing sequence of
integers given by

    s[0] = x1,      s[1] = y,      s[k] = N s[k-1] - s[k-2]

We know that
                    s[k]^2 + s[k+1]^2
                    -----------------  =  N
                     1 + s[k]s[k+1]

for k=1,2,3,...  If s[k+1] = 0 for some index k, then N = s[k]^2, so
N is a square.  The key is to show that this sequence MUST pass 
through 0.  To prove this, suppose the sequence does not pass through
zero.  It follows that, since the sequence is strictly decreasing, it
must contain two consecutive integers with opposite signs.  Thus the 
quantity  (x^2 + y^2)/(1+xy)  must be either infinite (if xy=-1) or 
negative (if xy < -1), contradicting that fact that this quantity 
equals N, which is a finite positive integer.  This completes the
proof.

Notice that if the quantity N = (x^2 + y^2)/(1+xy) is a negative 
integer for integers x,y, then N=-5.  There are exactly two distinct
infinite families of solutions in this case, given by the following
sequences (with alternating signs)
 
       1   2   9  43  206  987 ...

       1   3  14  67  321  1538 ...

each of which satisfies the recurrence s[k] = 5s[k-1] - s[k-2].

We can generalize the proposition to cover positive integers of the
form
                    x^2 + Kxy + y^2
                    ---------------  =  N
                        1 + xy

for all integers N greater than K, where K is a positve integer not
equal to 2.  (We exclude 2 for reasons that will be explained below.)
In this case we have the polynomial

               x^2 - (Ny-Ky)x + (y^2 - N)  =  0

which shows that if (x1,y) is a solution, then (x2,y) is also a 
solution, where x2 = (N-K)y - x1.  Also, if x1 exceeds y, then x2 is
less than y.  If we try to prove that every integer N (greater than 
K) given by this equation is a square, we can proceed just as before,
except that now, depending on the value of K, it is possible to have
x,y with opposite signs yielding an integer value of N greater than
K.  We excluded the case K=2 because in that case we can achieve
ANY value of N by setting y=1 and x=N-1.  This is not ruled out by
the "descent" argument because all these cases descend back to the
pair 1,-1, which gives the indeterminate 0/0, and allows for any
value of N.

So, excluding that special case, let X,Y denote the absolute values
of x and y, and observe that if x and y have opposite signs the 
expression for N can be written in the form

                          X^2 + Y^2 - K
                  N = K - -------------
                              XY-1

which shows that x^2 + y^2 must be less than K in order for N to 
exceed K.  Thus there are just a finite number of pairs (x,y) with
opposite sign that can yield a value of N greater than K.  These
are the only possible non-square values of N.  The smallest possible
pair is 1,-2 (which is equivalent to 2,-1), in which case we have
N = (5-2K)/-1, which we require to be greater than K.  This implies
the inequality K > 5.  Hence, any integer value of N (greater than K)
must be a square for K = 0, 1, 3, 4, or 5.

For K=6 the pair 1,-2 gives N=7, so every integer value of N greater
than 6 is either a square or equal to 7.  More generally, every value
of K greater than 5 allows the pair 1,-2, so we always have the N 
value of N = 2K-5.  For example, with K=7 the pair 1,-2 gives N=9.
However, in this particular case the "exceptional" N value also
happens to be a square, so we can say that any integer N greater
than 7 is a square.  This occurs for K = 7, 15, and 115, so the
non-negative integers K such that every positive integer N of the
form (x^2 + Kxy + y^2)/(1+xy) greater than K is a square is

                   0, 1, 3, 4, 5, 7, 15, 115

The number of minimal pairs x,y with opposite sign yielding integer
values of N tends to increase as K increases, but it appears that
there are infinitely many K for which the only reduced pair is 1,-2.
The first such K values are

    6, 7, 8, 9, 10, 13, 15, 19, 21, 25, 31, 37, 39, 45, 49,
     61, 81, 85, 99, 109, 115, 129, 141, 145, 151, 159, 169,
      175, 229, 285, 295, 319, 325, 361, 375, 445, 501, ...

(This list includes the squares of 3, 5, 7, 9, 13, 19, and 63.)  These
numbers are the result of a progressive sieve, analogous to the prime
sieve.  For example, every term greater than 10 must not be divisible
by 2, because otherwise it would give an integer N for (3K-10)/2 based
on the pair 1,-3.  Likewise from the pair 2,-2 we see that every term
greater than 8 must not be congruent to 2 modulo 3, because otherwise
it would give an integer N for (4K-8)/3.  Here is a short table of
the expressions that must not be integers for sufficiently large 
"prime K" values

         -1        -2         -3         -4          -5

   1      -     (2K-5)/1  (3K-10)/2  ( 4K-17)/ 3  ( 5K-26)/ 4
   2            (4K-8)/3  (6K-13)/5  ( 8K-20)/ 7  (10K-29)/ 9
   3                      (9K-18)/8  (12K-25)/11  (15K-34)/14
   4                                 (16K-32)/15  (20K-41)/19
   5                                              (25K-50)/24

In each case the expression (AK-B)/(A-1) implies that for K values
greater than B we must exclude those such that K = B (mod A-1).  In
other words, the sieve excludes every number greater than q = x^2 + y^2
congruent to q mod (xy-1).