Prove that there exist infinitely many positive integers $k$ such that the sequence $\{x_n\}$ satisfying $$ x_1=1, x_2=k+2, x_{n+2}-(k+1)x_{n+1}+x_n=0(n \ge 0)$$ does not contain any prime number.
Problem
Source: 2019 FKMO Problem 3
Tags: number theory
Hypernova
23.03.2019 12:55
$n^2-3$, sorry but posted already
lminsl
23.03.2019 17:23
For reference: here.
Letteer
19.11.2019 04:39
I tried to workout the question for $k=1$ and I got that $x_n=2n-1 $ which contains prime numbers. From the statement of the question $x_2=k+2$ so there are infinitely many integers $k$ for which $k+2$ is a prime number. For $k=1, x_2=3$ which is prime and you have a contradiction
I tried using the Z transform. From the question, we conclude that $x_0 = -1$. And taking the Z transform we get:
$$ x_{n+2} - (k+1)x_{n+1}+x_n = 0 $$$$ z^2X(z)-x_0z^2-x_1z-(k+1)(zX(z)-x_0z) + X(z) = 0 $$$$ X(z) = \frac{(k+1)z+z-z^2}{z^2-(k+1)z+1} $$if we let $a=k+1$ then after taking the inverse Z transform we get:
$$ x_n = 2^{-n-1}\frac{ (-\sqrt{a^2-4}+a+2)(\sqrt{a^2-4}+a)^n - (\sqrt{a^2-4}+a+2)(a-\sqrt{a^2-4})^n }{\sqrt{a^2-4}}$$This might be helpful for further solving.
For $a=2$ which is $k=1$ the sequence becomes:
$$ x_n = 2n - 1 $$and it contains infinitely many prime numbers since it is a sequence of odd numbers and we have a contradiction.
mathgalaxy
07.07.2020 14:52
We have $x_{n+2}x_{n}=x_{n+1}^{2}-(k+3)$. Then, if $k+3=m^{2}$$(k \ge 2)$, $x_{n+2}x_{n}=(x_{n+1}-m)(x_{n+1}+m)$. Trivially, you can prove that $x_{n+1}$ is greater than $x_{n}$ by induction and $x_{2}=k+2>m$. So, $x_{n+1}=(k+1)x_{n}-x_{n-1}>kx_{n}>(k-1)x_{n}+x_{2}>x_{n}+m$ and $x_{n+1}-m>x_{m}$. $x_{n+2}=\frac{(x_{n+1}-m)(x_{n+1}+m)}{x_{n}}$and $x_{n}<x_{n+1}-m, x_{n}<x_{n+1}+m$ , so $x_{n+2}$ is not a prime number for all positive integer $n$.