Proving a solution to a double recurrence is exhaustive

Question

The equation $$ b^2 = \frac{a(a+1)}{2} + 1 $$ where $a$ and $b$ are integers, has the following smallish-integer solutions:

b        a
23      -33
11      -16
4        -6
2        -3
1        -1
1         0
2         2
4         5  <--- the motivating one!
11       15
23       32
64       90

These solutions (if I call them $a_i, b_i$, where $a_0 = 0$) appeared to me to satisfy a pair of recurrences, namely

\begin{align} a_{k+4} &= 8 b_{k+2} + a_{k} \\ b_{k+4} &= 4 a_{k+2} + b_{k} + 2 \end{align}

I've since proved that these recurrences, initialized with either the 0th and 2nd row or the 1st and 3rd row, generate sequences of numbers that do satisfy the given equation. (The proof involves decoupling, and then solving the resulting constant-coefficient 4th-order recurrences, one homogeneous and one inhomogeneous, solving for initial conditions, and verifying that the main equation holds for the resulting sequences.)

What I now wish to prove is that these are the only possible solutions, and I don't see a simple way to do that. Any ideas or hints?

Note: This problem arose from observing that the 15 balls on a pool table form a triangle whose side consists of 5 balls, but that when the cue-ball is added, you can form a square with four balls on a side. I made this observation about 47 years ago, discovered the recurrences by staring at the table of pairs for a long time, together with some blind luck and tinkered with it over the years. Now that I've done the part I always wanted to do (the recurrences do generate new solutions), I'm interested in getting help with proving that they're the only ones.

Answer 1

Here we take $W=2A+1.$

The structure of the $\mathbb Z$ automorphism group of an indefinite binary quadratic form is discussed in many places in many ways. In brief, the proper automorphism group is infinite cyclic along with $\pm 1,$ so one commonly switches attention to $PSL_2 \mathbb Z.$ Then, as always applies for Pell forms $x^2 - D y^2,$ we throw in a single improper automorph, $(x,y)\mapsto (x,-y).$ My favorite book that discusses the group is Binary Quadratic Forms by Duncan A. Buell. Another one, some differences in notation, also called Binary Quadratic Forms, by Buchmann and Vollmer.

J. H. Conway introduced the topograph method for indefinite binary quadratic forms in The Sensual Quadratic Form. There is a brief presentation in Elements of Number Theory by John Stillwell. I have taken a sort of overlap of the two presentations, in which I play down the middle coefficients of the forms but emphasize the specific solutions to $x^2 - D y^2 = n,$ along with incorporating the automorphism group of the form in the diagram. So, below are all solutions to what I called $W^2 - 8 B^2 = -7.$

Meanwhile, acting on column vectors, the generator of the automorphism group of the form is $$ M = \left( \begin{array}{rr} 3 & 8 \\ 1 & 3 \end{array} \right). $$

We call $M$ an automorphism (proper) of the quadratic form because $\det M = 1$ and $$ \color{red}{ M^T G M = G}, $$ where $$ G = \left( \begin{array}{rr} 1 & 0 \\ 0 & -8 \end{array} \right). $$

Note that $M$ is a 2 by 2 matrix, determinant $1$ and trace $6.$ By Cayley-Hamilton, we have $$ M^2 - 6 M + I = 0, $$ or $$ M^2 = 6M - I. $$ As a result, put all solutions $(W_n, B_n)$ in sequence, and we get $$ W_{n+2} = 6 W_{n+1} - W_n, $$ $$ B_{n+2} = 6 B_{n+1} - B_n. $$ As you can see in the diagram, one may see how the values for $-7$ actually split into two interleaved sequences according to these recurrences: $$ W_n = 5,31,181,... $$ and $$ W_n = 1,11,65,... $$ We also get two threads for the $B's,$ $$ B_n = 2,11,64,... $$ and $$ B_n = 1,4,23,... $$ Sometimes the two threads can be combined, usually not. As you can see in the diagram below, the two threads are caused by an improper automorph, this time let us call it $(x,y)\mapsto (-x,y).$

Alrighty, I thought it might help to fill in as much of the complete diagram as would fit on my original. Properly speaking, every edge of the infinite graph, actually a tree, should have either a $0$ or a positive integer and a little arrow. I put many of those in, using orange, which is a little too close to the red I used for each occurrence of $(-7).$ Can't win them all. Also, as we move away from the "river," that being the central line, we simply add coordinates. For example $(1,0)+(3,1)= (4,1).$ On the negative side,$(-2,1)+(-1,1)= (-3,2).$ Worth emphasizing that there are two types of phenomena that give finiteness for the number of "orbits" that give $-7,$ the second of which is the "climbing lemma," that the absolute values of the numbers only increase when we move away from the river. So, in the first layer of negative values, we get $-4,-7,-8,-7,-4,$ and so on. In the second layer, possibly hard to read, we get only $-23,-31,-31,-23,$ over and over. So that is it, any further layers on the negative side have absolute values strictly larger than $7.$

Answer 2

For the equation:

$$a^2=\frac{b(b+1)}{2}+1$$

The solution can be written using the Pell equation:

$$p^2-2s^2=\pm1$$

To find them easily. Knowing what one solution can be found on the following formula.

$$p_2=3p_1+4s_1$$

$$s_2=2p_1+3s_1$$

To begin to $+1$ with $(p,s) - (3 ; 2)$

To begin to $-1$ with $(p,s) - (1 ; 1)$

Then the formula of the solutions can be written.

$$a=2p^2-5ps+4s^2$$

$$b=\pm(2p^2-8ps+6s^2)$$

$$***$$

$$a=p^2+ps+2s^2$$

$$b=\mp(p^2+4ps)$$

The upper sign according to the decision of the Pell equation for $+1$.

Lower $-1$.

$p,s $ - these numbers can have any sign.

Answer 3

This year Tito called my attention to an idea that gives a very quick answer as to a problem such as $w^2 - 8 b^2 = -7,$ which is how I wrote it in 2014. There we go, $w = 2a+1,$ so we need to include both $\pm w$ once we have all positive $w.$

All this program does is find solutions with positive $w,b$ by brute force. A few of the solutions are labelled "seed," and these generate all solutions using the (oriented) automorphism group of the form, $$ (w,b) \mapsto (3w+8b, w + 3b). $$ The inverse mapping is $$ (w,b) \mapsto (3w-8b, -w + 3b). $$ Almost all solutions with $w,b >0$ are carried to a smaller solution with positive entries by the inverse mapping. Eventually, we reach "seed" solutions, which have $w,b>0,$ however either $3w-8b \leq 0 0$ OR $-w+3b \leq 0.$ That is all there is to it. It is easy enough to show that all the non-seed, or "derived" solutions, have $w/b \approx \sqrt 8.$ A seed solution has either $w/b \leq 8/3 = 2.6666666,$ or $w/b \geq 3.$ It is the first possibility that occurs because $-7 < 0.$ It is easy enough to derive bounds on the absolute values of $w,b$ in a seed solution, as $-7 = w^2 - 8 b^2 = (w + b \sqrt 8)(w - b \sqrt 8)$

jagy@phobeusjunior:~$  ./Pell_Target_Fundamental

  3^2 - 8 1^2 = 1

 w^2 - 8 b^2 = -7

 Pell automorph 
3  8
1  3

 Pell automorph inverse
 3   -8
-1    3





Tue Apr 19 12:52:29 PDT 2016

w:  1  b:  1 ratio: 1  SEED 
w:  5  b:  2 ratio: 2.5  SEED 
w:  11  b:  4 ratio: 2.75
w:  31  b:  11 ratio: 2.818181818181818
w:  65  b:  23 ratio: 2.826086956521739
w:  181  b:  64 ratio: 2.828125
w:  379  b:  134 ratio: 2.828358208955223
w:  1055  b:  373 ratio: 2.828418230563003
w:  2209  b:  781 ratio: 2.82842509603073
w:  6149  b:  2174 ratio: 2.828426862925483
w:  12875  b:  4552 ratio: 2.828427065026362
w:  35839  b:  12671 ratio: 2.828427117038907
w:  75041  b:  26531 ratio: 2.828427122988202
w:  208885  b:  73852 ratio: 2.828427124519309
w:  437371  b:  154634 ratio: 2.82842712469444
w:  1217471  b:  430441 ratio: 2.828427124739511
w:  2549185  b:  901273 ratio: 2.828427124744667
w:  7095941  b:  2508794 ratio: 2.828427124745993
w:  14857739  b:  5253004 ratio: 2.828427124746145
w:  41358175  b:  14622323 ratio: 2.828427124746184

Tue Apr 19 12:53:09 PDT 2016

 w^2 - 8 b^2 = -7

jagy@phobeusjunior:~$