Real valued polynomial has real coefficients If a polynomial has real outputs for all real inputs, it must have all real coefficients. You can see this by using Taylor's formula, and the fact that all derivatives must also have real outputs for real inputs. 
Is there a more immediate proof of this that does not use calculus? 
 A: Let be $P$ a counterexample of minimal ($>0$) degree. $a_0 = P(0)\in\Bbb R$ by hypothesis. Then $Q(x) = (P(x) - a_0)/x$ is real for $x\in\Bbb R$, so $Q$ has real coefficients. But then $P(x) = xQ(x) + a_0$ has real coefficients.
A: Below is a sketch of an alternative proof using strong induction on the degree of the polynomial.
A $0^{th}$ degree polynomial is a constant, so that constant must be real in order for the polynomial to take real values on $\mathbb{R}$.
Assume the statement holds true for polynomials of degree $\le n$ where $n \ge 0$ and let $P(x)$ be a polynomial of degree $n+1$. Then it is easy to prove that $Q(x) = P(x+1) - P(x)$ is a polynomial of degree $\le n$ which has real values for $\forall x \in \mathbb{R}$. By the hypothesis of the induction step, all coefficients of $Q(x)$ must be real. But the coefficients of $Q(x)$ are linear combinations with integer factors of the coefficients of $P(x)$ for powers $\le n$, therefore those must be real as well. Then the coefficient of $x^{n+1}$ must also be real since all others are, which concludes the induction step.
A: Newton's interpolation formula is
$$
f(n) = d_0 \binom{n}{0} + d_1 \binom{n}{1} + d_2 \binom{n}{2} +  d_3 \binom{n}{3} +\cdots
$$
where $d_i$ are the numbers in the first column of the repeated differences array.
Therefore, a polynomial that takes real values at the integers is a real linear combination of the binomial polynomials and so has real coefficients.
A: Let 
$$P(x)=a_nx^n+...+a_1x+a_0 \\
Q(x)=\overline{a_n}x^n+....+\overline{a_1}x+\overline{a_0}$$
Now, for $x$ real you get
$$P(x)=\overline{P(x)}=Q(x)$$
Therefore $P-Q$ is a polynomial which has infinitely may roots (all real numbers are roots).
P.S. The solution can be written alternatelly in this form: if you split the coefficients into real and imaginary part, your polynomial becomes $R_1(x)+iR_2(x)$ for some real polynomials $R_{1,2}$. Then your condition means $R_2$ has infinitely many roots. 
It is the same solution...
A: Here are two not-so-original approaches that are disguises of some of the ideas in the other answers. Let the polynomial be $p(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}$. 


*

*(This one use calculus, though.) Let $D=\operatorname{diag}(1,2,\ldots,n)$. We have
$$
\begin{align*}
&\left(\int_0^1p(x)dx,\int_0^2p(x)dx,\ldots,\int_0^np(x)dx\right)\\
&=\left(a_0,a_1,\ldots,a_n\right)D^{-1}
\pmatrix{
1&1&\cdots&1\\
1&2&\cdots&n\\
1&2^2&\cdots&n^2\\
\vdots&\vdots&&\vdots\\
1&2^{n-1}&\cdots&n^{n-1}
}D.
\end{align*}
$$
Since the vector of integrals is real and both $D$ and the Vandermode matrix are real invertible, each $a_i$ must be real too.

*(In the spirit of N.S.'s or lhf's answers.) Pick $n$ distinct points on the real line and construct the Lagrange interpolation polynomial $L$ of $p$ at these $n$ points. As a degree-$(n-1)$ polynomial is uniquely determined by its values at $n$ distinct points, we get $p=L$, which has real coefficients.
