Suppose the set S is defined recursively as follows:
1. 1 ∈ S,
2. If x ∈ S, then 2 · x ∈ S.
Prove that S = {2^n | n ≥ 0}.

Question

Suppose the set S is defined recursively as follows:
1. 1 ∈ S,
2. If x ∈ S, then 2 · x ∈ S.
Prove that S = {2^n | n ≥ 0}.

anonymous · Answer

It's a fairly straightforward proof by induction.

Establishing the base case is simple, since $2^0=1$ and it's explicitly given that $1\in S$.

Now assume that for $n=k$, we have $2^k\in S$. To show that $2^{k+1}\in S$ is a matter of referring to the second part of the recursive definition.

freckles · Answer

oh for some reason for the longest time I was stuck on number 2 I thought that was 2-x in S

freckles · Answer

My eyes are not what they used to be

anonymous · Answer

The problem I am getting is putting it in more formal terms based on the set.