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

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