Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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$.

share|cite|improve this answer
It is clear that $P_n$ is in $S$. The result then follows immediately from the representation $Q_{n+1} = (P_n + P_{n-1}) Q_n / 2$. – Richard Hevener Nov 21 '12 at 0:56
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$ ... – Hagen von Eitzen Nov 21 '12 at 12:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.