I'm planning on being a TA for a computer science class and I'm reviewing a few things that have slipped my memory. Currently I'm working on this:

Show that the polynomials are closed under composition such that for all polynomials $x,y : \mathbb{R} \rightarrow \mathbb{R}$, the function $r: \mathbb{R} \rightarrow \mathbb{R}$ defined by $z(n) = x(y(n))$ is also a polynomial.

I've tried several approaches on paper, but I can't come up with a cohesive answer.

  • 2
    $\begingroup$ Products of polynomials are polynomials. So powers of a polynomial are polynomials by induction. The sum of two polynomials is a polynomial. Combining the above gives you that polynomials of polynomials are polynomials. $\endgroup$ – Dylan Nov 18 '15 at 21:50
  • 1
    $\begingroup$ @Dylan & one more preliminary proposition, to cover coefficients of the polynomial being substituted to: constant multiples of polynomials are polynomials. $\endgroup$ – BrianO Nov 18 '15 at 23:27
  • $\begingroup$ @BrianO One could argue that that is already taken care of because constants are polynomials. But I will admit that when I posted the comment that I had forgotten about constants and that they should be considered, so thank you pointing that out. $\endgroup$ – Dylan Nov 18 '15 at 23:32
  • $\begingroup$ @Dylan Yes one could argue — quite convincingly — that it's handled by products of polynomials being polynomials :) It is worth mentioning, though, that that case also shows const * poly --> poly. $\endgroup$ – BrianO Nov 18 '15 at 23:36

A good computer-sciencey approach would be to prove generally, by structural induction:

Lemma. If $E$ is any expression built from the operators $+$ and $\times$, real constants, and a single variable $\mathtt X$, then the function that results from evaluating $E$ with an input value bound to $\mathtt X$ is a polynomial.

Next, if $p$ and $q$ are polynomials, then simply unfolding their definitions in the expression $p(q(\mathtt X))$ gives you something built out of $+$, $\times$, real constants, and the variable symbol, to which you can apply the lemma.


Every polynomial is $$ p(x) = \cdots\cdots + \square x^k + \cdots\cdots $$ (where $\text{“}\square\text{''}$ is a coefficient). So \begin{align} p(q(x)) & = \cdots\cdots+\square(q(x))^k+\cdots\cdots \\ & = \cdots\cdots+ \square\Big( \square x^m + \square x^{m-1} + \square x^{m-1} + \cdots + \square \Big)^k +\cdots\cdots. \end{align} How you you expand $(a+b+c+\cdots+z)^k$? When you expand it, each term is a constant times a power of $x$. So you end up with a sum of finitely many of those.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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