CPM Homework Help : PC Problem 8-153

Prove that for any positive integer n, $\displaystyle \sum_ { j = 1 } ^ { n } \frac { 1 } { \sqrt { j } } \geq \sqrt { n }$ . Hint: $\sqrt { n } \sqrt { n + 1 } > n$ (why?)

Hint:

$\sqrt { n } \sqrt { n + 1 } > \sqrt { n }\sqrt { n }=\sqrt { n ^2}=n$

Step 1:

$\frac{1}{\sqrt{1}}\geq \sqrt{1}$

Step 2:

Assume $\displaystyle \sum _{j=1}^{k}\frac{1}{\sqrt{j}}\geq \sqrt{k}$ for some integer $k$ .

Step 3:

$\displaystyle \sum _{j=1}^{k+1}\frac{1}{\sqrt{j}}=$

$\displaystyle \sum _{j=1}^{k}\frac{1}{\sqrt{j}}+\frac{1}{\sqrt{k+1}}\geq$

$\sqrt{k}+\frac{1}{\sqrt{k+1}}=$

$\frac{\sqrt{k}\sqrt{k+1}+1}{\sqrt{k+1}}\geq$

$\frac{k+1}{\sqrt{k+1}}= {\sqrt{k+1}}$

So the induction step is true.

Step 4:

Hence, by mathematical induction we have proven that

$\displaystyle \sum _{j=1}^{n}\frac{1}{\sqrt{j}}\geq \sqrt{x}n$

for any positive integer $n$ .