# An inductionish problem.

1. May 8, 2014

### frobeniustaco

1. The problem statement, all variables and given/known data

Let S is a subset of the natural numbers [denote S$\subseteq$N] such that

A: 2k$\in$S $\forall$ k$\in$N
B: if k$\in$s and k ≥ 2, then k-1$\in$S

Prove that S=N

2. Relevant equations

3. The attempt at a solution

My first instinct was to approach it like one would prove the principle of mathematical induction, but I got to a point and it seems like it won't work that way. I'm not sure how else to approach the proof. Here's what I've got:

Suppose S≠N. Then N\S [the compliment of N with respect to S, or the set of elements that are in N but not in S] is nonempty, and by the Well-Ordering Property of N, N\S has some least element m.

2$\in$S by hypothesis, so m>2. This implies that m-1$\in$N.

Since m-1 < m, and m is the smallest element in N that is not in S, we conclude that m-1$\in$S.

This is where something seems wrong to me. I want to somehow get to m$\in$S, so I have a proof by contradiction, but I'm not sure how I can do this with the given hypotheses.

2. May 9, 2014

### pasmith

Doesn't there exist a $k \in \mathbb{N}$ such that $2^k \geq m$?

3. May 9, 2014

### frobeniustaco

That does make sense. That had crossed my mind briefly, but now that I've spent a little more time thinking about it I feel more comfortable. I'd been confusing myself since m doesn't have an upper limit, but since N isn't bounded above even if you pick an m higher than 2k, there's still going to be a 2k+1 that is bigger. I think I should be able use the second hypothesis to work my way back down to m.

Thank you much!