A sequence $(x_n)_{n\ge 0}$ is defined as follows: $x_0=a,x_1=2$ and $x_n=2x_{n-1}x_{n-2}-x_{n-1}-x_{n-2}+1$ for all $n>1$. Find all integers $a$ such that $2x_{3n}-1$ is a perfect square for all $n\ge 1$.
Problem
Source: Baltic Way 2005
Tags: number theory proposed, number theory
Rust
28.12.2010 20:44
Let $y_n=2x_n-1$. Then $y_n=y_{n-1}y_{n-2}, y_0=2a-1,y_1=3.$ It gives $y_2=3(2a-1), y_3=9(2a-1)$. Generally, from $y_n=y_{n-1}y_{n-2}\to y_n=y_{n-2}^2y_{n-3}$. Therefore, if $2a-1=n^2$, then $y_{3n}$ is perfect square.
leibnitz
28.04.2020 17:24
Rust wrote: Let $y_n=2x_n-1$. Then $y_n=y_{n-1}y_{n-2}, y_0=2a-1,y_1=3.$ It gives $y_2=3(2a-1), y_3=9(2a-1)$. Generally, from $y_n=y_{n-1}y_{n-2}\to y_n=y_{n-2}^2y_{n-3}$. Therefore, if $2a-1=n^2$, then $y_{3n}$ is perfect square. Isn't this supposed to be $y_n=\frac{y_{n-1}y_{n-2}+1}{2}$ (I could be wrong) sorry to bump tho
QuantomaticGuy
20.05.2021 07:17
can't we just let a be a perfect square i.e. a = A^2 and then 2a - 1 = n^2 is nothing but n^2 - 2A^2 = -1 which is the negative pell equation?
guptaamitu1
19.12.2021 14:08
The answer is $\boxed{\text{NO}}$. Define $y_n = 2x_n - 1$. Then $y_0 = 2a-1, y_1 = 3$ and
$$\frac{y_n+1}{2} = \frac{(y_{n-1} + 1)(y_{n-2} + 1)}{2} - \frac{y_{n-1} + 1}{2} - \frac{y_{n-2} + 1}{2} + 1 ~ \implies ~ \boxed{y_{n} = y_{n-1} y_{n-2} + 1}$$Now assume on the contrary that $y_{3n}$ is a perfect square for all $n \ge 1$. Note that $y_3$ is even, forcing $y_3 \equiv 0 \pmod{4}$. But then,
$$y_4 \equiv 1 ~~,~~ y_5 \equiv 1 ~~,~~ y_6 \equiv 2 \qquad \pmod{4}$$So $y_6$ cannot be a perfect square, so we obtain our desired contradiction. $\blacksquare$
@below: Yeah, I messed up the algebra.
Pal702004
19.12.2021 16:28
guptaamitu1 wrote: The answer is $\boxed{\text{NO}}$. Define $y_n = 2x_n - 1$. Then $y_0 = 2a-1, y_1 = 3$ and $$\frac{y_n+1}{2} = \frac{(y_{n-1} + 1)(y_{n-2} + 1)}{2} - \frac{y_{n-1} + 1}{2} - \frac{y_{n-2} + 1}{2} + 1 ~ \implies ~ \boxed{y_{n} = y_{n-1} y_{n-2} + 1}$$ WakeUp wrote: $x_n=2x_{n-1}x_{n-2}-x_{n-1}-x_{n-2}+1$ for all $n>1$. $2x_n=4x_{n-1}x_{n-2}-2x_{n-1}-2x_{n-2}+2$ $2x_n=(2x_{n-1}-1)(2x_{n-2}-1)+1$ $2x_n-1=(2x_{n-1}-1)(2x_{n-2}-1)$ Define $y_n=2x_n-1$ $\boxed{y_{n} = y_{n-1} y_{n-2}}$ $2x_{3n}-1=y_{3n}$ must be a square. $y_0=2a-1=b, y_1=3,y_2=3b,y_3=3^2b,y_4=3^3b^2,\cdots$ Or $y_n=3^{F_n}\cdot b^{F_n-1}\;\; \forall n>1$ where $F_n$ is Fibonacci sequence $F_{3n}$ is even for all n, but $F_{3n-1}$ is odd, so $b=2a-1$ must be a square.