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?

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

1 Answer 1


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$

  • $\begingroup$ 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 $\endgroup$
    – Mike
    Jul 1, 2014 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .