Two polynomial problems 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...
 A: 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).
A: 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.
Or
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.
A: 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.
