# Polynomials closed under composition

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.

• 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. – Dylan Nov 18 '15 at 21:50
• @Dylan & one more preliminary proposition, to cover coefficients of the polynomial being substituted to: constant multiples of polynomials are polynomials. – BrianO Nov 18 '15 at 23:27
• @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. – Dylan Nov 18 '15 at 23:32
• @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. – BrianO Nov 18 '15 at 23:36

## 2 Answers

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.