We know that $\sin(a+t)=\sin(a)\cos(t)+\sin(t)\cos(a)$, and a similar formula for $\cos(a+b)$. Using this identity, we can prove the claim by induction on $n$, as follows.
When $n=1$, this is clear.
If you assume this claim holds for both $\sin$ and $\cos$ for $n=m-1$, then you use the formula above with $a=(m-1)t$, to see that $\sin(mt)=\sin((m-1)t)\cos(t)+\sin(t)\cos((m-1)t)$. Since by induction $\sin((m-1)t)$ is a polynomial function in $\sin(t)$ and $\cos(t)$, then $\sin(mt)$ is a polynomial function. The same is true for $\cos(mt)$. Therefore, the claim holds for $n=m$.
I'm not very happy with this question.
The way it is posted makes it look like a problem with a solution ("the problem which was proposed on some contest"). So I spent much time trying to prove it.
And finally it all comes to a counterexample: $P(x) = \frac{(x^2 - x)^2}{2}$.
- For any $x \in \Bbb Z$, we have $P(x) \in 2\Bbb Z$.
- For any $x,y \in 2\Bbb Z$, we have $x - y\mid P(x) - P(y)$.
It follows that, for any $n$ and any $x \in \Bbb Z$, the sequence $(x_k)_k$ defined by $x_0 = x$ and $x_{k + 1} = P(x_k)$ is eventually periodic mod $n$.
This is because, starting from $k = 1$, the sequence stays in $2\Bbb Z$. Since there are only finitely many residues mod $n$, the sequence eventually has a repeated term mod $n$, say $x_s \equiv x_t\mod n$, with $1 \leq s < t$. But then $n \mid x_s - x_t \mid P(x_s) - P(x_t) = x_{s + 1} - x_{t + 1}$, and by induction we see that the sequence $(x_k)_k$ is periodic mod $n$, starting from $k = s$.
Best Answer
Yup, I just arrived at that.
Make a substitution $t^2=u$, then we have $f(u)$ can be any polynomial that is symmetric around $u=\frac{1}{2}$.
One example could be $a(u)=(u-\frac{1}{2})^2$ which corresponds to $f(t)=(t^2-\frac{1}{2})^2$.
Another example of a non-polynomial function would be $f(t)=|t^2-\frac{1}{2}|$.
Any polynomial that is a linear combination of even powers of $(t^2-\frac{1}{2})$ will work.