6
$\begingroup$

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$.

  • 1
    The 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
  • 0
    What 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
  • 0
    A 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
  • 1
    I think the spirit of the problem requires integer coefficients. Otherwise $P(x)=x+\frac{1}{2}$ works as well2010-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 1

3

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$.

  • 0
    I 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
  • 0
    I 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