Polynomials closed under composition

Question

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.

Answer 1

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.

Answer 2

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.