Non-negative polynomials as sums of squares

Prove that any non-negative real polynomials can be expressed as a sum of squares.

More formally, if $P(x)$ is a polynomial with real coefficients such that $P(x) \geq 0 \forall x \in \mathbb{R}$, show that there exist $Q_1,Q_2,\cdots, Q_k$ polynomials with real coefficients such that $P(x) \equiv Q_1^2(x) + Q_2^2(x) + \cdots + Q_k^2(x)$.

Solution

Let $n$ be the highest degree in $P(x)$. If $n$ is odd, then $\lim_{x \to \inf} P(x)$ and $\lim_{x \to -\inf} P(x)$ have different signs, so $P(x)$ couldn't be non-negative. Therefore $n$ is even. We will prove by induction on $n$.

For $n=2$, clearly we can express $P(x) = (ax+b)^2 + c^2$ for some $a,b,c$ real numbers if $P$ is non-negative.

Now let $r$ be a root of $P$. If $r$ is real, then $r$ must have even multiplicity, otherwise $P(x)$ changes sign at $r$. Thus, $P(x) = (x-r)^2 Q(x)$ for some $Q$ polynomial with real coefficients. But that means $Q$ is non-negative as well, and thus can be expressed as a sum of squares. Therefore $P$ can also be expressed as a sum of squares.

But if $r$ is complex, then $P(r) = P(\bar{r}) = 0$. Then $P(x) = (x-r)(x-\bar{r})Q(x) = ((x+b)^2 + c^2)Q(x)$ for some $b,c$ real and some $Q$ real polynomial. That also means that $Q$ is non-negative and can be expressed as a sum of squares, and then so can $P$.