Define On as inductively as follows: O1 = {1}; On+1 = On ∪ {2n+1}. Let O = ∪nOn. Let O = ∪nOn
Prove by Induction that On = {1,3,...,2n-1}
P(n) would be the statement that On+1 = On ∪ {2n+1}.
However, I'm having trouble doing with the base case.
P(1) ( i.e. O2 = O1 ∪ {3} ) is true because ...
By the definition, isn't O2 = {2}? and the RHS {1,3}? Surely I'm missing something here?
Also, what does a Union symbol with a subscript mean?
Thanks.
If you're working from a not too unusual presentation of induction, $P(n)$ is supposed to be the claim that you want to prove holds for all $n$.
Thus, when you say that $P(n)$ means $O_{n+1} = O_n \cup \{2n+1\}$, you're already going wrong, because $O_{n+1} = O_n \cup \{2n+1\}$ is something you already know to be true, in that it is your definition of what $O_i$ means.
In a proof of $O_n = \{1,3,\ldots,2n-1\}$ by induction on $n$, your $P(n)$ should be that claim: $$ P(n) \;\equiv\; O_n = \{1,3,\ldots,2n-1\}$$
Even so, you will run into some problems because in order to reason properly about things like $\{1,3,\ldots,2n-1\}$ with dots in them, you need a definition for what that notation means. And the most straightforward definition of $\{1,3,5,\ldots,2n-1\}$ would be exactly the recursive definition for $O_n$ you start out with -- but in that case there's nothing at all for you to prove!
For class purposes you can probably get away with just winging it and use a non-rigorous intuitive understanding of $\{1,3,\ldots,2n-1\}$ instead of an actual definition. But don't be surprised if it feels like you're not really doing anything ...