Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Could someone explain this step in this proof to me?

  1. Nov 21, 2011 #1
    1. The problem statement, all variables and given/known data

    I already have the solutions, just don't understand one step

    Let [tex](n_k)_{k=1}^{\infty}[/tex] be a sequence of integers

    [tex]n_1 < n_2 < n_3 < ...[/tex]

    Then [tex]n_k \geq k[/tex] [tex] \forall k = 1,2, ...[/tex]

    In particular [tex]n_k \to \infty[/tex] when [tex]k \to \infty[/tex]

    Prove this is true


    2. The solution

    Employ Induction

    (1) Base Case: k = 1

    [tex]n_1 \geq 1[/tex]

    (2) Induction: Assume [tex]n_k \geq k[/tex] for the case k. We show k + 1 case

    [tex]n_{k+1} > n_k > k \implies n_{k+1} > k \implies n_{k+1} \geq k + 1[/tex]

    Hence the result holds

    Question

    How on earth did we get to [tex]n_{k+1} \geq k + 1[/tex] from [tex] n_{k+1} > k [/tex]
     
  2. jcsd
  3. Nov 21, 2011 #2
    Because nk+1 is strictly greater than k, and both are integers. So nk+1 is either k + 1 or an integer even greater.
     
  4. Nov 21, 2011 #3
    I don't follow that

    Before we had >, then ≥

    Counterexample

    5 > 4

    5 + 1 > 4 + 1

    6 > 5

    6 ≠ 5, ever
     
  5. Nov 21, 2011 #4
    Hmm, first of all, if in your "counter-example", you took nk+1 = 5 and k = 4, then 5 ≥ 4 + 1 = 5. Secondly, just because 6 ≠ 5, that doesn't mean 6 ≥ 5 is not true. ≥ is just less strict than > and it allows equality, but doesn't fail even if the equality is never reached. It's still true that 6 is greater than or equal to 5.
     
  6. Nov 21, 2011 #5
    Wow I hadn't even thought of it that way. I mean not the ≥ part, but 5 = 5.

    Thanks problem solved
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook