Let $p(x)$ be a polynomial that is nonnegative for all $x\in\mathbb R$. Prove that for some $k$, there are polynomials $f_1(x),f_2(x),\ldots,f_k(x)$ such that $$p(x)=\sum_{j=1}^kf_j(x)^2$$
WLOG, assume the polynomial is monic. Now we can write $p(x)$ as $$p(x)= [(x-a_1)(x-a_2) \cdots (x-a_n)][(x-\overline{a_1})(x-\overline{a_2}) \cdots (x-\overline{a_n})]$$ where $a_1,a_2, \cdots , a_n$ are complex number which aren't necessarily distinct. Let $a_j =m_j+in_j$ then $$(x-a_j)(x- \overline{a_j})= (x-m_j)^2+n_j ^2$$ Now we use the identity $(a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad + bc)^2$ to finish.
Is this correct?
Your proof is correct. However it can be made slightly faster. The polynomial is of the form $p(x)=\displaystyle c\prod_{k=1}^n(x-a_i)(x-\overline{a}_i),c>0.$ Let $h(x)=\displaystyle \sqrt{c}\prod_{k=1}^n(x-a_i)=A(x)+iB(x),$ where $A(x)={\rm Re}\,h(x),\ B(x)={\rm Im}\,h(x).$ Then $A(x)$ and $B(x)$ are polynomials with real coefficients and $$p(x)=|h(x)|^2=A(x)^2+B(x)^2$$