# What does “give a recursive definition of the set of polynomials with integer coefficients”, mean?

What is the set of polynomials with integer coefficients look like? Help!

Thanks!

-
I think the question is telling you to characterize the set by giving a few "basic polynomials" which you know are inside the set, and give some operations that produce more integer polynomials given those already inside the set. Then you need to prove that your rules encapsulate every integer polynomial. – Herng Yi Feb 10 '13 at 7:16

## 2 Answers

Here, as an example of the sort of thing that’s wanted, is a recursive definition of the set $T$ of positive integers that multiples of $3$:

1. $3\in T$.
2. If $m,n\in T$, then $m+n\in T$.
3. $T$ contains only those integers required by the first two clauses.

To see that $12\in T$, for instance, we note that $3\in T$ by (1), so $3+3=6\in T$ by (2), and then $6+6\in T$ by a second application of (2).

Now let $T'=\{3n:n\in\Bbb Z^+\}$; we’d like to prove that $T=T'$, i.e., that we really did define the set of positive multiples of $3$. We first prove by induction that $T\subseteq T'$.

The base case is easy: $3=3\cdot1\in T'$. That is, the one member of $T$ that we’re explicitly given in (1) is in $T'$. Now we show that the constructor clause (2) preserves membership in $T'$: if $m,n\in T'$, then there are positive integers $a$ and $b$ such that $m=3a$ and $n=3b$, and therefore $$m+n=3a+3b=3(a+b)\in T'$$ as well. In short, we start with an element of $T'$, namely $3$, and we add new elements to $T$ via (2) in a way that can only give us multiples of $3$ if we start with multiples of $3$, so end up with nothing but multiples of $3$: $T\subseteq T'$.

To show that $T'\subseteq T$ (and hence that $T=T'$), suppose that $T'\setminus T\ne\varnothing$, and let $m$ be the smallest member of $T'\setminus T$. Since $m\in T'$, $m=3k$ for some positive integer $k$. We know that $k\ne 1$, since $3\cdot1=3\in T$, so $k>1$. But then $k-1$ is still a positive integer, so $3(k-1)\in T'$. $3(k-1)<m$, and $m$ is the smallest member of $T'\setminus T$, so $3(k-1)\notin T'\setminus T$. Certainly $3(k-1)$ is in $T'$, so this implies that $3(k-1)\in T$ as well. But then $$m=3k=(3k-3)+3=3(k-1)+3$$ is the sum of two members of $T$, so $m\in T$ by clause (2) of the definition of $T$. And this is a contradiction, since we assumed that $m\notin T$. Thus, the supposition that $T'\setminus T\ne\varnothing$ must be false, i.e., we must have $T'\subseteq T$.

You want a recursive definition of the set of polynomials in one variable $x$ with integer coefficients. (I’m assuming that polynomials in one variable were intended; if that’s not the case, the definition is a little more complicated, but the ideas are similar.) The simplest ones are the constant ones; take those as the base elements, analogous to $3$ in my example. If $P$ is the set of polynomials that you’re trying to define, you could start with this:

1. Every integer belongs to $P$.

How do you build up more complicated polynomials from simpler ones? You can multiply by $x$, or you can add two polynomials that you already have. For instance, if want $3x^2-2x+4$, you could get it from $3,-2$, and $4$ by the following steps: multiply $3$ by $x$ to get $3x$; add $-2$ to get $3x-2$; multiply by $x$ to get $3x^2-2x$; and add $4$. Thus, you’ll have two growth clauses instead of the one in my example. One is will say that if $p(x)$ is in $P$, so is $xp(x)$; what will the other say?

Your question doesn’t say so, but you may well be expected to prove that your definition really does define the intended set of polynomials. Such proofs are typically similar in general outline to the one that I gave with my example.

-
is the other one: if p(x) is in P and p(y) is in P then p(x) + p(y) is in P? We don't have to give a proof for our recursive definition but I'd love to see one :). – papercuts Feb 10 '13 at 9:36
@papercuts: Yes, that’s the other growth clause (if you take this particular approach to a recursive definition of $P$: it’s not the only possible one). The proof boils down to showing by induction that you can derive $a_0+a_1x+\ldots+a_nx^n$ by starting with $a_n$, multiplying by $x$, adding $a_{n-1}$, multiplying by $x$, adding $a_{n-2}$, multiplying by $x$, ..., and finally multiplying by $x$ and adding $a_0$. – Brian M. Scott Feb 10 '13 at 9:42

Hint:

Here's a "recursive definition of the set of positive rationals".

1. $1$ is in the set.
2. If $a$ and $b$ are in the set, so is $a + b$.
3. If $c$ and $d$ are in the set, so is $c/d$.

Now, I prove that this "recursive algorithm" covers all of the positive rationals. (1) and (2) clearly produce all positive integers. Since every rational is of the form $p/q$, where $p$ and $q$ are positive integers, (3) clearly includes $p/q$ in the set.

Adapt this idea to generate integer polynomials!

-