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.

  • $\begingroup$ Can you please elaborate how x = i can be derived from the given definition. From what I see, only positive integers are possible in the set $\endgroup$ Commented Sep 11, 2022 at 8:46
  • $\begingroup$ $S=\{a,bi\}$ where $a,b$ are powers of $2$? Or we start with $1,i$ are contained in $S$ in point 1. This is not excluded, since also then $1\in S$. Or should it be read "we only know that $1\in S$" in 1.? $\endgroup$ Commented Sep 11, 2022 at 8:48
  • $\begingroup$ One idea I have is that since we know $x+x \in S$, then maybe it's possible that $x + x + \ldots + x = x\cdot y \in S$, where $x$ is being added $y$ times. If $x,y \in \mathbb{N}$, you could try a strong induction proof. They're just my thoughts though. $\endgroup$ Commented Sep 11, 2022 at 19:02

2 Answers 2


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$.


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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .