Could someone explain this step in this proof to me?

  • Thread starter flyingpig
  • Start date
  • #1
2,571
1

Homework Statement



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]
 

Answers and Replies

  • #2
1,086
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.
 
  • #3
2,571
1
Because nk+1 is strictly greater than k, and both are integers. So nk+1 is either k + 1 or an integer even greater.
I don't follow that

Before we had >, then ≥

Counterexample

5 > 4

5 + 1 > 4 + 1

6 > 5

6 ≠ 5, ever
 
  • #4
1,086
2
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.
 
  • #5
2,571
1
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.
Wow I hadn't even thought of it that way. I mean not the ≥ part, but 5 = 5.

Thanks problem solved
 

Related Threads on Could someone explain this step in this proof to me?

  • Last Post
Replies
2
Views
859
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
4
Views
911
Replies
4
Views
2K
Replies
3
Views
848
Replies
18
Views
2K
Replies
1
Views
1K
Replies
2
Views
662
Replies
2
Views
481
Top