1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An inductionish problem.

  1. May 8, 2014 #1
    1. The problem statement, all variables and given/known data

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

    A: 2k[itex]\in[/itex]S [itex]\forall[/itex] k[itex]\in[/itex]N
    B: if k[itex]\in[/itex]s and k ≥ 2, then k-1[itex]\in[/itex]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[itex]\in[/itex]S by hypothesis, so m>2. This implies that m-1[itex]\in[/itex]N.

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

    This is where something seems wrong to me. I want to somehow get to m[itex]\in[/itex]S, so I have a proof by contradiction, but I'm not sure how I can do this with the given hypotheses.
  2. jcsd
  3. May 9, 2014 #2


    User Avatar
    Homework Helper

    Doesn't there exist a [itex]k \in \mathbb{N}[/itex] such that [itex]2^k \geq m[/itex]?
  4. May 9, 2014 #3
    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!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: An inductionish problem.
  1. A problem (Replies: 2)

  2. Problem - (Replies: 7)

  3. Limits problem (Replies: 4)