[Math] Proving that all terms in sequence are positive integers (Recursive)

Question

I am preparing for Putnam and working through practice-like questions and I am boggled. I've got the sequence defined by $a_1 = 1$ and $a_{n+1} = 2a_n+\sqrt{3a_n^2-2}$ for any $n\in\mathbb{N}$ and I'm trying to show that every term is a positive integer. I am getting as far as $a_{n+1}^2 -4a_{n+1}a_n + a_n^2 = -2$ but I can't figure out how to use the recursive relationship to show that all terms are integers. I've tried expanding the sequence in terms of $a_n$ or $a_{n+2}$ but it doesn't seem to get me far. Any hints or help would be greatly appreciated.

Answer 1

what you are missing is the automorphism group of the quadratic form $x^2 - 4 x y + y^2.$ On this site, the relevant observation is usually referred to as Vieta Jumping, which is a special case. The point is that a solution $(x,y)$ to $x^2 - 4 x y + y^2= k$ (in this case $k=-2$) can be replaced by a new solution $$ (y, 4y - x). $$ CHECK!!!!!!!!

This means that $(a_n, a_{n+1})$ becomes $(a_{n+1}, a_{n+2})$ with the specific $$ a_{n+2} = 4 a_{n+1} - a_n. $$ Thus, they are all integers. Furthermore, as long as $a_{n+1} > a_n,$ then $a_{n+2} > a_{n+1},$ so they continue increasing and positive forever by induction.

next day: a short tutorial. Suppose we have positive integers $x,y,q$ and a fixed target $T,$ an integer. Then suppose we have $$ \color{blue}{ x^2 - q xy + y^2 = T.} $$ Let us take $0 < x < y.$ The increasing direction in Vieta Jumping is $$ \color{green}{ (x,y) \mapsto (y, qy-x).} $$ The decreasing (with $0 < x < y$) direction is $$ \color{red}{ (x,y) \mapsto ( qx-y, x).} $$ To be specific, the thing keeps decreasing the sum of the entries as long as $qx < 2y.$ The way proofs are arrived at in these problems is to examine those solutions with $x \leq y$ but $qx \geq 2y.$ These are what Hurwitz, in 1907, called Grundlösungen, or fundamental solutions. If there are no fundamental solutions, there are no solutions at all, because positive integers cannot decrease forever. If the fundamental solution has one of the variables $x,y$ equal to zero, that says that the target $T$ is a square. And so on. By and large, the jumping phenomenon stays the same, it is the inequalities towards the end that vary.