# Check these recursive definitions for me?

Looking for

Give a recursive definition of

A) the set of odd positive integers

B) the set of positive integer powers of 3

C) the set of polynomials with integer coefficients

I have

a. Basis: $p(1)=1$ Recusive: $p(n+1)= p(n) +2$

b. Basis: $f(1) = 3$ Recursive: $f(n+1) = f(n)(3)$

c. Basis: $f(1) = 0$ Recursive: $f(n+1)=f(n) + cn^x$, where $c$ and $x$ are integers.

Does this suffice?

• I think for a. you mean $p(n+1)=p(n)+2$. Jul 1, 2014 at 17:45
• Is this a homework question? For part c, shouldn't $f(n)$ yield a single polynomial for each $n$? Jul 1, 2014 at 17:48
• thanks joff. and yeah it's a homework question. I guess I don't know what else it could be
– Mike
Jul 1, 2014 at 18:13

You have the right idea, but your notation is wrong. You are attempting to define sets, but writing them as functions. Instead, you should specify each set by one or more base elements and rules for generating the remaining elements.

For instance, (a) can be described as the minimal* set $A$ such that:

• $1$ is in $A$
• If $n$ is in $A$, then $n+2$ is in $A$

* It's important to specify that $A$ is the minimal such set, otherwise any set containing the set you want will also qualify.

Part (b) is similar to (a). Part (c) is a little trickier. Your answer points towards the minimal set $C$ such that:

• $0 \in C$
• If $p(x) \in C$, and $c$ and $k$ are integers, then $p(x) + cx^k \in C$

This is a little inelegant, since it refers to elements of another infinite set (the integers). Can you see how to avoid this? Here is one way:

$C$ is the minimal set such that:

• $0 \in C$
• If $p(x) \in C$, then $p(x) + 1 \in C$
• If $p(x) \in C$, then $p(x) - 1 \in C$
• If $p(x) \in C$, then $p(x) \cdot x \in C$

• great criticism I appreciate it. I'm not sure how I would change my statement to get rid of the C and X and only use one variable, if that's what you're suggesting :S
– Mike
Jul 1, 2014 at 18:56