[seqfan] Re: The Virtues of X_{n+1}=(4+3*X_{n})/(3+2*X_{n})

[David Seal]

> X_{n+1}=(4+3*X_{n})/(3+2*X_{n})
> ======================
> ...
> * With X = P/Q, the rational iterator decomposes to integer-only form :
> ( P_{n+1} , Q_{n+1} )=( 3*P_n + 4*Q_n , 2*P_n + 3*Q_n )

I'll observe that that is equivalent to two iterations of the function:

  (x,y) -> (x+2y,x+y)

which associates the integer solutions of the Pell equation x^2 - 2y^2 = +/-1 with each other. In particular:

  (x+2y)^2 - 2(x+y)^2 = (x^2 + 4xy + 4y^2) - 2(x^2 + 2xy + y^2)
    = -(x^2 - 2y^2)

I.e. if I calculate x^2-2y^2 for each (x,y) pair I get, each iteration of my function changes its sign. So with one iteration of your function being equivalent to two of mine, yours leaves that x^2-2y^2 value unchanged: 4^2 - 2*3^2 = 24^2 - 2*17^2 = 140^2 - 2*99^2 = ... = -2. And as the values of P and Q grow, that -2 difference becomes more and more insignificant relative to the squares, which gives an easy way to see why x/y tends to sqrt(2).
 
> * ( P_0 , Q_0 ) = ( 4 , 3 ) is a good enough initial condition, better than
> ( 0 , 1 ) in the sense that 0 does not provide any semblance of an
> approximation to sqrt(2), ha! ...

Well, (0,1) does have the property that 0^2-2*1^2 = -2, so it does fit in! The bad approximation is just the converse of what I say above: as the values of x and y shrink, x/y gets further away from sqrt(2).

>... The iterated sequence seems to recover (
> A005319, A001541 ); though, my reading of the entries did not rigorously
> clarify this question.

A005319 says that it's the y values in the solutions to 2x^2-y^2=2, which after swapping the roles of x and y and negating is equivalent to the x values in the solutions to x^2-2y^2 = -2. So they're your P values.

A001541 says that it's the x values in the solutions to x^2-8y^2 = 1, which after doubling, swapping the roles of x and y and negating is equivalent to the y values in the solutions to (4x)^2-2y^2 = -2. Or in other words, to the y values in the solutions to x^2-2y^2 = -2 for which x is a multiple of 4. Rewriting that as x^2+2 = 2y^2, look at the two sides of that equation mod 8: x^2+2 is 3 mod 8 if x is odd, 2 mod 8 if x is a multiple of 4 and 6 mod 8 if x is 2 mod 4, while 2y^2 is 0 mod 8 if y is even and 2 mod 8 if y is odd. There's only one way they can be equal, so all solutions to x^2-2y^2 = -2 have x a multiple of 4 (and y odd). And so the A001541 values are the y values in all the solutions to x^2-2y^2 = -2, i.e. your Q values.

> * The transformation is invertible:
> ( P_n , Q_n ) = (3*P_{n+1} - 4*Q_{n+1},-2*P_{n+1} + 3*Q_{n+1} )

Yes, and likewise mine has inverse (x,y) -> (2y-x,x-y). And those invertible transformations are the key to showing that one gets all solutions to x^2-2y^2 = +/-constant (for mine) or constant (for yours). Specifically, provided x and y are large enough in magnitude (just how large depends on the constant), one can show that one of the two transformations will transform to a solution with smaller-magnitude x and y - for both of our transformations, it's the inverse version if x and y have the same signs and the forward version if they have opposite signs. So starting with any solution, we can systematically transform it to a solution with x and y insufficiently large in magnitude. There are only finitely many such possibilities for x and y, which we can check for being solutions, and once we've done that, we know that all solutions can be found by applying the transformations to the solutions we've found. (That's only a sketch of how to produce rigorous proofs of the assertions in A005319 and A001541, by the way - I'll leave the details to the reader!)

For my transformations, it works out that all solutions can be obtained from the two small-magnitude solutions (+/-1,0), and for yours, that all solutions can be obtained from the two small-magnitude solutions (0,+/-1). Going in both directions from both of those, in each case we get (positive,positive), (positive,negative), (negative,positive) and (negative,negative) versions of the solutions (A005319 and A001541 of course just giving the (positive,positive) versions).

Best regards,

David