# Give a recursive definition for the set of polynomials with integer coefficients.

I'm thinking of the form

$$p_n = a_0t^0 + a_1t^1 + a_2t^2 +\cdots + a_nt^n.$$

However the only way I can think to write it is

$$p_n = p_{n-1}+ a_nt^n.$$

I'm probably thinking the wrong way. This "definition" wouldn't even define any numbers when used recursively, it would just show that there's some a $p_n$ with some coefficients $a_0, a_1,a_2, \ldots, a_n$. Or... maybe I'm doubting myself? I'm not sure.

-

I don’t normally like to produce full answers to homework questions, but I can’t think of a hint that seems likely to be helpful, so I’m going to go to the other extreme to try to produce a model that you can use in thinking about other problems of this kind.

The simplest polynomials in $t$ with integer coefficients are those of the form $a$, where $a\in\Bbb Z$, so you should take this as the basis of your recursive definition:

Basis Clause: If $a\in\Bbb Z$, $a$ is a polynomial in $t$ with integer coefficients.

That gets me started. Now I want a rule that takes whatever integer polynomials I already have and gives me more, in such a way that if I keep iterating it, I eventually get all of the integer polynomials. The natural idea, which you already had, is to build up by generating polynomials of higher and higher degree.

Suppose that I already had available to me all integer polynomials of degree at most $n$, say; how could I get all integer polynomials of degree at most $n+1$? You might try taking any of the polynomials that you already have and adding a $t^{n+1}$ with a non-zero coefficient; that’s pretty much what you tried to do. In order to do this, however, you need to know at which stage of the construction you’re currently working. It can be done that way, but it gets a little messy.

There’s a slicker way that lets you increase the degree by one without having to know the degrees of the polynomials that you already have. If $p(t)$ is a polynomial with integer coefficients, and $a$ is any integer, $tp(t)+a$ is a polynomial with integer coefficients and degree greater by $1$ than that of $p(t)$. Can you see that if you already have all of the integer polynomials of degree $\le n$, this automatically produces all of the integer polynomials of degree $\le n+1$, no matter what $n$ is? Now turn this idea into the generation clause of your recursive definition:

Generation Clause: If $p(t)$ is a polynomial in $t$ with integer coefficients, and $a\in\Bbb Z$, then $tp(t)+a$ is a polynomial in $t$ with integer coefficients.

Finally, you want a rule that says that the only integer polynomials are the things produced by (1) and (2). (This point is sometimes overlooked, even in textbooks.)

Limitation Clause: Anything not generated by (1) and (2) is not a polynomial in $t$ with integer coefficients.

These three clauses form a recursive definition of the set of polynomials in $t$ with integer coefficients, which for convenience I’ll call $\mathscr{P}$.

They can be used to determine in a mechanical way whether something belongs to $\mathscr{P}$. If I want to check whether $t^4+2t^2+3t+4$ is such an object, for instance, I can proceed as follows.

\begin{align*} t^4+2t^2+3t+4&=t(t^3+2t+3)+4\;;\tag{1}\\ t^3+2t+3&=t(t^2+2)+3\;;\tag{2}\\ t^2+2&=t(t)+2\;;\tag{3}\\ t&=t(1)+0\;;\tag{4}\\ 1&\in\Bbb Z\;.\tag{5} \end{align*}

Now work back from the bottom up: $(5)$ and the Basis Clause imply that $1\in\mathscr{P}$. That fact, $(4)$, and the Generation Clause imply that $t\in\mathscr{P}$. That fact, $(3)$, and the Generation Caluse then imply that $t^2+2\in\mathscr{P}$, and after two more inferences of this type we conclude that yes, $t^4+2t^3+3t+4\in\mathscr{P}$.

In this case the value of such a definition probably isn’t very apparent, since we already understand very well what things are in $\mathscr{P}$. There are two answers to that objection. The first is that this is something of a toy example, designed to help you understand how recursive definitions work. The second is that as I tried to suggest above, a description of this kind can make checking membership in a collection a very mechanical process of the sort easily programmed on a computer.

-
or, from the bottom up: $\Bbb{Z}[x] = \bigcup P_n$ where: $P_0 = \Bbb{Z}$ and $P_n = xP_{n-1} + P_{n-1}$. –  David Wheeler Apr 8 '12 at 10:17
@David: Yes, but I preferred to give an example of the type of definition that in my experience is usually found in textbooks for elementary discrete math courses. –  Brian M. Scott Apr 8 '12 at 10:29