Here we go !
Je récapitule (en anglais comme l’énoncé était en anglais
)
Let P(x) be a polynomial of degree n>1 with integer coefficients and let k be a positive integer.
Consider the polynomial Q(x)=P(P(...P(P(x))...)), where P occurs k times. Prove that there are at most n integers t such that Q(t)=t.
[spoiler]Let P:\mathbf{R}\to\mathbf{R} denote the function \displaystyle x\longmapsto\sum_{i=0}^na_ix^i where the (a_i)_{0\leq i\leq n} are integers,with a_n\neq 0.
**Lemma I. ** For all integers x,y such that x\neq y, x-y|P(x)-P(y).
Proof. \displaystyle P(x)-P(y)=\sum_{i=0}^na_ix^i-\sum_{i=0}^na_iy^i=\sum_{i=1}^na_i(x^i-y^i). Hence the result.\square
Let t\in\mathbf{N} be such that Q(t)=t and P(t)\neq t.
Let’s define a sequence (t_i)_{i\in\mathbf{N}} such that t_0=t and t_{i+1}=P(t_i). All of its terms are integers, of course.
From Lemma I, it follows that t_{i}-t_{i-1} divides P(t_{i})-P(t_{i-1}), which is equal to t_{i+1}-t_i. Moreover, t_1-t_0=t_{k+1}-t_k, since t_k=t_0=t.
Since we have t_1-t_0|t_2-t_1|...|t_{k+1}-t_k, we can remark that |t_{i+1}-t_{i}| remains constant.
The set (a_i)_{0\leq i\leq k} is finite, hence it has a maximal element, denoted t_{max}. It follows that t_{max}-t_{max-1}=+|t_{i+1}-t_i| and that t_{max+1}-t_{max}=-|t_{i+1}-t_i|.
So we have t_{max-1}=t_{max+1}. Using mathematical induction, we get that the sequence (t_i)_{i\in\mathbf{N}} is composed of only two different values.
Therefore, if t is a fixed point of Q, it is either a fixed point of P or P^2 (denoting P\circ P).
It is evident that if t is a fixed point of P, then it is a fixed point of P^2.
Now let a, b\in\mathbf N be two fixed points of P^2, such that P(a)\neq P(b) and a\neq P(a). From lemma I, a-b|P(a)-P(b) and P(a)-P(b)|a-b, hence a-b=\pm(P(a)-P(b))
We also notice that P(a)-b|a-P(b) and a-P(b)|P(a)-b, hence P(a)-b=\pm(a-P(b)).
Two plus in the previous equations lead to the contradictory equality a=P(a). At least one equation has a minus sign, which leads to the following : a+P(a)=b+P(b).
If a is fixed, then t\in\mathbf{N} is a fixed point of P^2 if it is a root of the equation 0=a+P(a)-x-P(x). However, the polynomial a+P(a)-x-P(x) has degree n.
Lemma II. An $n$th degree polynomial has at most n real roots.
Proof. Evident from the intermediate value theorem, using mathematical induction on n.\square
Hence there are at most n fixed points for P^2, which leads to the following : they are at most n integers t such that Q(t)=t.[/spoiler]