Given an infinite positive integer sequence $\{x_i\}$ such that $$x_{n+2}=x_nx_{n+1}+1$$Prove that for any positive integer $i$ there exists a positive integer $j$ such that $x_j^j$ is divisible by $x_i^i$. Remark: Unfortunately, there was a mistake in the problem statement during the contest itself. In the last sentence, it should say "for any positive integer $i>1$ ..."
Problem
Source: Kazakhstan National Olympiad 2022 Grade 10-11 P6
Tags: Sequence, Divisibility, number theory
20.04.2022 20:49
Let $x_i=p_1^{t_1}p_2^{t_2}...p_m^{t_m}$ Let $a_n=(x_n \pmod{p_1},x_{n+1} \pmod {p_1})$ is sequence of pairs. $a_n$ can take not more than $p_1^2$ different values and so it is periodic with period $T_1$ So $a_i=a_{i+kT_1} \to x_{i+kT_1} \equiv x_i \equiv 0 \pmod {p_1}$ for positive integer $k$ Then we can find such $T_1,T_2,..,T_m$ that $p_m|x_{i+kT_m}$ for $n \leq m$ and positive integer $k$ Let $T=T_1...T_m$ then $p_1p_2...p_m|x_{i+kT}$ for positive integer $k$ we can choose big enough $k$ such that $j=i+kT \geq i*max (v_{p_n}(x_i))$( $n \leq m$) and then we will have $v_{p_n}(x_j^j) \geq j \geq i*max (v_{p_n}(x_i))$ and so $x_i^i|x_j^j$
20.04.2022 21:44
What an original problem! See ISL 1994 N6 https://artofproblemsolving.com/community/c6h31735p196779
20.04.2022 23:03
Chosing problem for National MO from different contests maybe understandable, but choosing from old SL is very absurd...
13.05.2022 14:03
lmao goofy ah problem