0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks. It makes a lot of sense now $\endgroup$
    – tommycatpr
    Aug 28 '14 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.