Sequence of positive integers $\{x_k\}_{k\geq 1}$ is given such that $x_1=1$ and for all $n\geq 1$ we have $$x_{n+1}^2+P(n)=x_n x_{n+2}$$where $P(x)$ is a polynomial with non-negative integer coefficients. Prove that $P(x)$ is the constant polynomial. Proposed by Navid Safaei
Problem
Source: Iran 2024 3rd round p6
Tags: algebra
27.08.2024 07:02
bump pls
27.08.2024 08:48
Here you can see the solution, https://t.me/matholampiad123
27.08.2024 09:38
Could someone post the solutions file from the above channel? It seems that I can't download them. Edit: Thanks! For anyone who doesn't have telegram and can't open it: By induction $x_{n+1}>2^{n-c}$ for some constant $c$. But $x_{n+1} \mid P(n)^2-P(n-1)P(n+1)$ and thus this can't hold for sufficiently large $n$ by size.
27.08.2024 10:09
It's a mp4 file, a film https://t.me/matholampiad123/618
29.08.2024 10:54
a_507_bc wrote: By induction $x_{n+1}>2^n$. I think that it is not exactly true. We can have $x_2=x_3=...=x_k=1$ a long subsequence of $1$. But it seems that the same words work: we can say that $x_n \geq 2^{n-c}$ and anyway $x_n>P(n)$ for a large $n$.
17.09.2024 21:47
What a great problem! I wish to many countries that they have people to come up with such problems. We have $x_{n+1}^2 + P(n) = x_nx_{n+2}$, $x_{n+2}^2 + P(n+1) = x_{n+1}x_{n+3}$ and $x_{n+3}^2 + P(n+2) = x_{n+2}x_{n+4}$. These give the congruences $x_{n+1}^2 \equiv -P(n)$, $P(n+1) \equiv x_{n+1}x_{n+3}$, $x_{n+3}^2 \equiv -P(n+2)$ mod $x_{n+2}$, hence $x_{n+2} \mid P(n)P(n+2) - P(n+1)^2$. On the other hand, observe that $x_n$ grows exponentially: indeed, if $x_n = 1$ for all $n$, then $P \equiv 0$ and we are done; otherwise let $M \geq 2$ be minimal with $x_M \geq 2$ (note that $x_1 = 1$), so from $x_{n+2} \geq \frac{x_{n+1}^2}{x_n}$ (as $P$ has non-negative coefficients) we obtain (as $x_{M-1} = 1$) $x_{M+1} \geq x_M^2$ and $x_{M+k} \geq x_M^{k+1}$ by induction. Therefore $x_{n+2} > |P(n)P(n+2) - P(n+1)^2|$ for sufficiently large $n$, thus it has to be the case that $P(n)P(n+2) = P(n+1)^2$ for sufficiently large $n$ and hence for all $n$, as $P$ is a polynomial. Finally, as a consequence $\frac{P(n+2)}{P(n+1)} = \frac{P(n+1)}{P(n)}$, so with $m$ being minimal with $P(m) > 0$ we have by induction $P(m+n) = P(m)c^{n-1}$ for some constant $c>0$. If $c\neq 1$, then $P$ grows exponentially, contradiction. Therefore $c = 1$ and so $P(n) = P(m)$ for all $n$ is constant, as desired. (Alternative finish from $P(n)P(n+2) = P(n+1)^2$: if $P$ is non-constant, then take a complex root $\alpha$ - by induction it follows that $\alpha + k$ is also a root for any integer $k$, contradiction.)