Polynomial $P$ satisfies $P(n)>n$ for all positive integers $n$. Every positive integer $m$ is a factor of some number of the form $P(1),P(P(1)),P(P(P(1))),\ldots $. Prove that $P(x)=x+1$.
Iterated polynomial problem
-
1The polynomial $P(x) = x+2$ is also a valid solution isn't it? I think any polynomial of the form $P(x) = x +k$ where $k$ is an integer would be a valid polynomial. – 2010-10-27
-
1@svenkat: No, in that case all the P(P(...P(1)...)) are odd. – 2010-10-27
-
0What is the source of this problem? Do you know it, Jaska? – 2010-10-27
-
0@Jaska: are the coefficients of the polynomial assumed to be integers? – 2010-10-27
-
0A friend of mine asked me just for curious I think. – 2010-10-27
-
0@Yuval Filmus: I'm not sure in we can assume coefficients to be integers. A friend showed me the problem and that is the exact translation. – 2010-10-27
-
1I think the spirit of the problem requires integer coefficients. Otherwise $P(x)=x+\frac{1}{2}$ works as well – 2010-10-28
-
0@Ross But probably we can reduce the general case to this case, so that we get $P(x) = x + \frac{1}{k}$. – 2010-10-28
1 Answers
Denote the iterates by $x_0 = 1, x_{n+1} = P(x_n)$.
Assume that the coefficients of $P$ are integral.
If at some point $P(x_n) > 2x_n$, then I claim that $m = P(x_n)-x_n$ does not divide any iterate. First, $x_n < m$, so $x_0,\ldots,x_n$ cannot be divisible by $m$. Second, we prove by induction that for $k \geq n$, $x_k \equiv x_n \pmod{m}$:
$x_{k+1} = P(x_k) \equiv P(x_n) \equiv x_n \pmod{m}$.
Since $x_n < m$, we see that $m$ doesn't divide any of the iterates.
We conclude that always $P(x_n) \leq 2x_n$. Thus $P(x) = ax+b$ with $a \leq 2$. On the one hand $P(1) > 1$, and on the other hand $P(1) \leq 2$. Thus $P(1) = 2$, and therefore either $a = 1$ or $a = 2$. If $a = 2$ then $P(x) = 2x$, and we generate only powers of $2$. Thus $a = 1$ and $P(x) = x + 1$.
-
0I don't see how you get $x_k \equiv x_n \pmod{m}$. It's true for n+1, but why should $P(x_{n+2}) \equiv P(x_{n+1}) \pmod{m}$? – 2010-10-27
-
0@Ross $P(x_k) - P(x_n)$ is divisible by $x_k - x_n$. – 2010-10-27
-
0I thought it was by induction, but didn't see why $P(x_{n+2})-x_{n+2} \equiv P(x_{n+1})-x_{n+1} \pmod m$ – 2010-10-28