So what I am stuck on is proving the inequality for n=k+1. I have my teacher's solution, but it doesn't quite make sense to me.
Teacher's solution:
$\sqrt 1 + \sqrt 2 + ... + \sqrt{k} + \sqrt{k+1} < \frac {4k+3}{6} \sqrt{k} +\sqrt{k+1}$ (by assumption) $< \frac {4k+1}{6} \sqrt{k+1} + \sqrt{k+1} $
So he basically added 1 to the k under the square root in the first term, making the resulting expression greater. I get that. But he also subtracted 2 from the numerator of the fraction, which should make the expression smaller.
Is there something I'm missing here? How can we be certain that changing the expression as described above results in a larger expression?
PS: My exam is in 3 days... would appreciate a quick reply :) Thanks!
Hypothesis:
$$\sum_{j=1}^k \sqrt{j} < \frac{4k+3}{6}\sqrt{k}$$
We wanted to show that
$$\sum_{j=1}^{k+1} \sqrt{j} < \frac{4(k+1)+3}{6}\sqrt{k+1}$$
From the hypothesis, we have
$$\sum_{j=1}^{k+1} \sqrt{j} < \frac{4k+3}{6}\sqrt{k}+\sqrt{k +1}$$
Hence it suffices to verify that
$$\frac{4k+3}{6}\sqrt{k}+\sqrt{k +1} < \frac{4(k+1)+3}{6}\sqrt{k+1}$$
which is equivalent to
$$\frac{4k+3}{6}\sqrt{k}< \frac{4(k+1)-3}{6}\sqrt{k+1}=\frac{4k+1}{6}\sqrt{k+1}$$
which is just
$$(4k+3)\sqrt{k} < (4k+1) \sqrt{k+1}$$
$$(4k+3)^2k < (4k+1)^2(k+1)$$
$$(4k+3)^2k < (4k+1)^2k + (4k+1)^2$$
$$2k(8k+4)< (4k+1)^2$$
$$8k < 8k+1$$
which is clearly true.