Take the 2-minute tour ×

I am struggling with these two problems:

1) Let $p$ be a polynomial with integer coefficients. Show that for each sequence of $k$-times iterating the polynomial, $n,p(n),p(p(n))=p^{(2)} (n),\ldots,p^{(k)}(n)$, we have to have $k\leqslant 2$, if $p^{(k)}(n)=n$ and $p(n) \neq n,p^{(2)} (n)\neq n,\ldots,p^{(k-1)}(n)\neq n$.

After thinking for some time about this problem, I have the strong impression, that I somehow have to make of use the fact, that the integer roots of a polynomial with integer coefficients, because the remainder of $p^{(k)}$ is $p^{(k)} (r)$, where $r$ is the remainder of $p$.

2) One has to show if there exists a polynomial such that $p(\frac{1}{k})=\frac{1}{2k+1}$, for all $k\in \mathbb{N}$.

My hunch here is, that this would be impossible, since $p$ would have to "oscillate" to much...but I can't make this precise.

Any help would be much appreciated.

EDIT: Second problem solved. What I've got for the first one with user9325's help: After proving that the distance between the iterates has to be constant, one can distinguish between the following cases: If $p(n)-n=0$, the we are finished. If $\alpha:=p(n)-n \neq0$, then we have to have $p^{(2)}(n)=n+2\alpha,\ldots,p^{(k-1)}(n)=n+(k-1)\alpha$, since $n-p(n)=p(n)-p^{(2)}(n)=\ldots=p^{(k-2)}(n)-p^{(k-1)}(n)=p^{(k-1)}(n)-n$. But $n-p(n)=p^{(k-1)}(n)-n$ implies that $p^{(k-1)}(n)=n-\alpha$. Combining these to equations concerning $p^{(k-1)}(n)$ gives us that $k=0$. This should be a contradiction but I am not sure how to make that crystal clear...I have the feeling, that I can't really see through this problem yet...

share|improve this question
Shouldn't it be that $p^{(n)} (0)=\frac{(-1)^{n+1}}{2^n}$, for $n\geqslant 1$ ? –  temo Apr 22 '11 at 15:12
add comment

3 Answers

up vote 7 down vote accepted

1) Use the fact that $a-b$ divides $p(a)-p(b)$ in this situation to notice that all consecutive elements of this list have the same distance and use this to prove a corrected version of what you wrote (i.e. the smallest period is 1 or 2, but of course multiples are then also periods).

Draw the number line with the first iterates. If you do not return after the first step then you can never return because earlier values of the sequence block your way (and you would have a $2$-cycle somewhere else).

share|improve this answer
I corrected the problem. Could you maybe provide more information, why the fact that the elements of this list have the same distance imply that $k \leqslant 2$ ? –  temo Apr 24 '11 at 12:53
@temo: THis is the answer I was talking about... –  Aryabhata Apr 24 '11 at 17:56
@user9325 Sorry that I still don't get it fully, could you maybe be a little more explicit ? What I managed to come up with until now, using your advice, I have written in an edit to my question. –  temo Apr 25 '11 at 18:20
$p(n)-n | p^{(2)}(n) - p(n) | \ldots | n - p^{(k-1)}(n) | p(n) - n$ so assuming $p(n) \neq n$, all these numbers are equal to $\pm C$ (constant $C$). –  Plop Apr 25 '11 at 18:45
Yes, but how do I prove from there (more rigorously than in the edit to my question), that I get a contradiction ? (And that somewhere else I have to have a 2-cycle ?) Because I am not sure what $k=0$ contradicts, since there aren't any assumptions for the values $k$ can take, I think. –  temo Apr 27 '11 at 6:01
show 2 more comments

2) You can notice that the polynomial and the rational function are two analytical functions (in a circle around $0$) that coincide on a set of points with a cumulation point and conclude that they would have to be equal, but they are clearly different rational functions.


You can expand the fraction as a geometric series and notice that any polynomial of a certain degree can not do a better approximation for small $1/k$ than using the first terms (which is the pedestrian way of doing the first argument in this particular case). Thus, any polynomial will either be a bad approximation and thus wrong for small $1/k$, or it will be the start of the geometric series and thus never exactly the geometric series.

share|improve this answer
add comment

For the second one,

if $\displaystyle P(x)$ is such a polynomial of degree $\displaystyle n$, then we have the

$\displaystyle (2k+1) k^n P(1/k) - k^n = 0$

Now $\displaystyle Q(x) = x^n P(1/x)$ is another polynomial of degree at most $\displaystyle n$.

Thus we have that

$\displaystyle (2k+1) Q(k) - k^n = 0$ for infinitely many $\displaystyle k$.

Since $\displaystyle (2k+1) Q(k) - k^n$ is a polynomial too and has infinite roots, it is identically zero.

Now setting $\displaystyle k = \frac{-1}{2}$ gives rise to a contradiction. Note: We don't really need the coefficients to be integers.

share|improve this answer
thank you, I managed to solve it. Have you an idea for the first one, though ? –  temo Apr 24 '11 at 17:37
@temo: I believe one of the other answers has it. –  Aryabhata Apr 24 '11 at 17:49
@Moron: If you adjust your last line, the solution would be perfect (a polynomial can have infinitely many roots, but then it is zero, which in this case implies that 2k+1 divides $k^n$. –  Phira Apr 24 '11 at 18:00
@user: That was implicit, but I will make it explicit. Thanks. –  Aryabhata Apr 24 '11 at 18:09
@Moron: I did not mean to imply that you did not understand it. –  Phira Apr 24 '11 at 18:11
show 1 more comment

Your Answer


