Prove that if x and y belong to the set defined by following definition, then x*y also belongs to the set

Question

We have the following recursive definition of a set

1. The number 1 belongs to set S
2. if x belongs to set S, then so does x+x
3. Only those elements defined by above rules belong to set S

Now, suppose x and y are two elements of set S. Prove that x*y also belongs to set S.

I realize that the set defined by three rules is the set of powers of 2 i.e. {1, 2, 4, 8, 16, 32,.....} and for any two powers of 2, we can use algebra to prove that their product is also a power of 2. But in this case, I need to prove that x*y belongs to set S only by using the recursive definition of set S.

Answer 1

Since only the elements defined in this way are in the set, if $x\in S$ and $x\neq 1$, then $x/2\in S$. Suppose that $x\in S$ is the smallest element such that there exists $y\in S$ with $xy\not \in S$. We can't have $x$ or $y$ equal to $1$, so $x/2 \in S$. Then $(x/2)*(2y)=xy\not \in S$, contradicting minimality of $x$.

Answer 2

Fix $x \in S$ and use induction on the recursive definition of the assertion that $y \in S$. In the base case, $y = 1$ and $x \times y = x \in S$, by assumption. In the inductive step $y = y' + y'$ where $y' \in S$ and the inductive hypothesis gives us that $x \times y' \in S$, but then $x\times y = (x \times y') + (x \times y')$ is also in $S$.