The question that I'm having trouble with is:
Prove that k/2 is a lower bound for √(n)
I'm not sure how I would start this, can someone take a look at it and help me with it? I understand the summation from 1 to k would be ((k^2 + k) / 2)
I'm just unsure how to actually prove that k/2 is a lower bound for the √(n).
Thanks in advance to anyone that can help with this.
Well, $\frac{k^{2}+k}{2}-\frac{k^{2}}{4} = \frac{1}{4}\cdot (k^{2}+2k)$. (Here, we use the fact that $\sqrt{n}$ is stricly increasing $\forall k>0$. This is an increasing function for $k\geq 1 > -1$. It should be obvious that it's true for $k=1$, since $1>\frac{1}{2}$. This completes the proof.