# Recursive definition of the set of odd numbers

Show that the following is another recursive definition of the set ODD (keep in mind you’ll need say something about even numbers too): Rule 1: 1 and 3 are in ODD. Rule 2: If x is in ODD, then so is x + 4.

I have no clue where to start on this so if someone could help me. thanks

Let $ODD$ be defined as given and let $S = \{2k - 1 \mid k \in \mathbb N\}$. We want to show that $ODD = S$. It should be easy to see that $ODD \subseteq S$.
To see that $ODD \supseteq S$, it suffices to prove by induction on $k \in \mathbb N$ that $2k - 1 \in ODD$.
Base Cases: This works for $k = 1$ and $k = 2$, since by Rule 1, we have that $1,3 \in ODD$.
Inductive Step: Assume that $2k' - 1 \in ODD$ for all $k' \in \{1, 2, \ldots, k - 1\}$, where $k \geq 3$.
It remains to prove that $2k - 1 \in ODD$. Indeed, notice that since $1 \leq k - 2 \leq k - 1$, we know by the induction hypothesis that $2(k - 2) - 1 \in ODD$. But then by letting $x = 2(k - 2) - 1$, it follows by Rule 2 that $[2(k - 2) - 1] + 4 = 2k - 1 \in ODD$, as desired.