0

https://i.stack.imgur.com/pM5yf.png

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.

user101985
  • 53

1 Answers1

0

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.

Christopher K
  • 3,383
  • But if it's increasing would that not be an upper bound? It's asking to prove k/2 is a lower bound. Can you please elaborate? Thanks for the reply. – user101985 Nov 08 '13 at 02:01
  • You agree that $n=\frac{k^{2}+k}{2}$. What I'm saying is that $n>(\frac{k}{2})^{2}=\frac{k^{2}}{4}>0$, since n is increasing faster than $\frac{k^{2}}{4}$ and it is larger in the case of $k=1$. This just comes from the fact that the derivative of the difference is non-negative $\forall k\geq 1$. – Christopher K Nov 08 '13 at 02:07
  • @user101985, do you understand now? – Christopher K Nov 08 '13 at 02:13
  • Hi again Chris, I just noticed you get k^2/4 in the equation when calculating to get the (1/4(k^2+2k)) result. Where does the k^2/4 come from? Thanks again! I know the (k^2+k / 2) is from the summation from 1 to k, but once again, this is dealing with √(n). Will look forward to your response – user101985 Nov 08 '13 at 06:01
  • I did this for simplicity's sake. As I noted (albeit somewhat vaguely) in my response above, if $f(x)$ is non-decreasing, then so is $\sqrt{f(x)}$ (with the proviso, of course, that $f$ is non-negative), by the continuity of $f$. Since the positive root is precisely what we want, this works out. Simply put, $f(x)\geq g(x)\geq 0; \forall; x$ implies $\sqrt{f(x)}\geq \sqrt{g(x)}$. – Christopher K Nov 08 '13 at 22:09
  • @user101985, I have added a response. See comment above. – Christopher K Nov 08 '13 at 22:12
  • thank you again for response. I can see what you did now. Would the process to prove that k+1 is an upper bound for sqrt(n) be the same process or what would be different? Hope you can respond soon again. – user101985 Nov 12 '13 at 00:42
  • Let's see: $(k+1)^{2} - \frac{k\cdot (k+1)}{2} = \frac{1}{2}\cdot (k+1)\cdot (k+2)$. So, this function is also stricly increasing $\forall; k > \frac{-3}{2}$. So this method can also be used in this case. – Christopher K Nov 12 '13 at 00:55
  • you say it's strictly increasing for k > 3/2. What is the reason it is for strictly greater than 3/2? I see for the lower bound why it was strictly greater than 0 but why 3/2 in this case? Thank you very much for your help Chris!! – user101985 Nov 12 '13 at 00:58
  • Let's take the derivative!. $[(k+1)\cdot (k+2)]' = (k+2)+(k+1) = 2k + 3$. So, a function is increasing when it has a positive derivative, that is when k is greater than $\frac{-3}{2}$. As for my earlier comment, I made a mistake! I got the sign wrong. – Christopher K Nov 12 '13 at 01:01
  • Hi again Chris, how would that prove it is an upper bound though? That's the last thing I don't get how you can figure out after computing the interval of k. Thanks again. – user101985 Nov 12 '13 at 01:45
  • Well, let $k = 1$. Then, $k+1=2$ and $\sqrt{n} = \sqrt{1} = 1$. Now, since the first term, i.e. $k+1$ is greater in the case of $k=1$, but it is also increasing faster than $\sqrt{n}$, we can conclude that it is always larger $\forall; k\geq1$. – Christopher K Nov 12 '13 at 02:04