Check these recursive definitions for me?

Question

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?

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$