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.