Proof by induction. Imagine that we are going to prove by induction that:

Question

(1/sqrt(1)) + (1/sqrt(2)) + (1/sqrt(3)) + ... + (1/sqrt(n)) >= sqrt(n), for all n E Z^+

Assume by the inductive step that:

(1/sqrt(1)) + (1/sqrt(2)) + (1/sqrt(3)) + ... + (1/sqrt(k)) >= sqrt(k), for some k E Z^+

Which of the following is a correct way of ending this proof?

a. (1/sqrt(1)) + (1/sqrt(2)) + ... + (1/sqrt(k)) >= sqrt(k) + (1/sqrt(k+1)) = sqrt(k+1) +1 >= sqrt(k+1)

b. (1/sqrt(1)) + (1/sqrt(2)) + ... + (1/sqrt(k)) >= sqrt(k+1) + (1/sqrt(k+1)) + (1/sqrt(k+1)) >= sqrt(k+1)

c. (1/sqrt(1)) + (1/sqrt(2)) + ... + (1/sqrt(k+1)) >= sqrt(k) + (1/sqrt(k+1)) = (sqrt(k)sqrt(k+1)+1)/sqrt(k+1)) >= (sqrt(k)sqrt(k)+1)/sqrt(k+1)) >= ((k+1)/sqrt(k+1)) = sqrt(k+1)

d. (1/sqrt(1)) + (1/sqrt(2)) + ... + (1/sqrt(k+1)) >= sqrt(k) + (1/sqrt(k)) = ((sqrt(k)sqrt(k+1))/sqrt(k)) >= ((k+1)/(sqrt(k+1))) = sqrt(k+1)

Answer 1

Sorry none of these are very good...

First Note that if X>y then A-x < A-y ****1

and

1/X < 1/Y ****2

Let S be the kth partial sum: 1/sqrt(1) + 1/sqrt(2) + .... + 1/sqrt(k)

The Induction hypothesis says that S > sqrt(k)

Then sqrt(k+1) - 1/sqrt(k+1) - S <= sqrt(k+1) - 1/sqrt(k+1) - sqrt(k) ****

= [sqrt(k+1) - sqrt(k)] - 1/sqrt(k+1)

= [(k+1)- k]/ [(sqrt(k+1)+sqrt(k)] - 1/sqrt(k+1) <--rationalizes numerator

= 1/[sqrt(k+1)+sqrt(k)] - 1/[sqrt(k+1)]

<=0 is negative by footnote 2

Therefore:

sqrt(k+1) - 1/sqrt(k+1) - S < 0

sqrt(k+1) < 1 /sqrt(k+1) + 2 which completes the proof