2
$\begingroup$

Define $P_0(x) = 0$ and for $n > 0, \ P_n(x) = (x \ + \ P_{n-1}^2(x)) / 2$ and $Q_n(x) = P_n(x) - P_{n-1}(x)$. Are all the coefficients of the polynomials $Q_n(x)$ nonnegative?

1 Answers 1

4

EDIT: Shortened according to a comment by Richard Hevener.

Let $\mathcal S$ be the set of polynomials with nonnegative coefficients. Then by looking at how the coefficients of sums and products are obtained we observe the following simple

Lemma. The set $\mathcal S$ is closed under addition and multiplication, i.e. $f,g\in\mathcal S$ implies $f+g,f\cdot g\in\mathcal S$.

Clearly, $P_0=0\in\mathcal S$ and by the lemma and the recursion formula for $P_n$, we have $P_n\in\mathcal S$ for all $n\ge 0$ by induction on $n$. Now $\begin{align}Q_{n+1} &= P_{n+1}-P_n\\ &=\frac12(x+P_{n}^2)-\frac12(x+P_{n-1}^2) \\&=\frac12(P_n+P_{n-1})(P_{n}-P_{n-1})\\ &=\frac12(P_n+P_{n-1})Q_n,\end{align}$ hence $Q_{n+1}\in\mathcal S$ if $Q_n\in\mathcal S$ and $n\ge1$. Thus the claim follows by induction for all $n\ge1$ because $Q_1=P_1\in\mathcal S$.

  • 0
    D'oh, why did I not see $P_n\ni\mathcal S$ right away? I was afraid, I'd need more explicit info about $P_n$ ...2012-11-21