4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ empirically, your sequence also satisfies the recursion $a_{n+1}=4a_n-a_{n-1}$ (include $a_0=1$ for completeness). $\endgroup$
    – lulu
    Aug 30 '15 at 23:17
  • $\begingroup$ got it, finally. I think it's fairly hard. Solution posted below. $\endgroup$
    – lulu
    Aug 31 '15 at 0:15
4
$\begingroup$

REVISED SOLUTION:

As you remarked, we have $$a_{n+1}^2-4a_{n+1}a_n+a_n^2=-2$$

Of course, we also have: $$a_n^2-4a_na_{n-1}+a_{n-1}^2=-2$$

Thus, $a_{n+1}$ and $a_{n-1}$ are roots of the quadratic $$A^2-4Aa_n+a_n^2+2$$

They are distinct because the $a_n$ are increasing.

It follows that $$a_{n+1}+a_{n-1}=4a_n$$

Your desired result follows instantly.

Note that this is easily solved to get:

$$a_n=\frac{3-\sqrt{3}}{6}\,(2+\sqrt{3})^n\;+\;\frac{3+\sqrt{3}}{6}\,(2-\sqrt{3})^n$$

Though you do not need this.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Just another way to look at it, consider the Diophantine equation $x^2=3y^2-2$, or in a more Pell-like form $x^2-3y^2=-2$.

From Pell theory, if you start with any integer solution $(x_1, y_1)$, you generate another integer solution by the recursion $x_2+\sqrt3y_2 = (x_1+\sqrt3 y_1)(2+\sqrt3)$. Thus $y_2 = x_1+2y_1 = 2y_1 + \sqrt{3y_1^2-2}$, which is exactly the recursion we have.

Here we are starting with the particular solution $(x_1, y_1) = (1, 1)$ and $a_n = y_n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.