Originally Posted by

**emakarov** The induction statement P(n) is "there exists a k such that n ≤ k² ≤ 2n". You assume P(j) and you are allowed to call the number whose existence is guaranteed by P(j) simply by k. Now you need to prove a new existence statement P(j + 1); the new number whose existence you need to prove may or may not be equal to k from P(j). Therefore, it is unreasonable to try to prove that j + 1 ≤ k² ≤ 2j + 2 always holds for that particular k.

However, we can break the inductive step into two cases. From P(j) we know that j ≤ k². Case 1 is when j < k²; then P(j + 1) is obvious for the same k. Case 2 is when j = k²; then clearly you need to find a new k' such that j + 1 ≤ k'² ≤ 2j + 2. Can you do this?

There is also a direct proof of P(n) for all n. Fix an n and let m = max {i | i² < n}. Then m² < n (which is the same thing as m² ≤ n - 1), but (m + 1)² ≥ n. We need to show that (m + 1)² ≤ 2n. We have

m² + 2m + 1 = m² + 2m - 1 + 2 ≤ (since 2m - 1 ≤ m² by 1) 2m² + 2 ≤ (since m² ≤ n - 1) 2n - 2 + 2 = 2n.