# Thread: Does this proof contain an error

1. ## Does this proof contain an error

You will notice in the final step that 11.4.2 was used as a justification for $\log_2 n = k$
however, from the first line we recall that $2^k < n < 2^{k+1}$ which means that we should not be able to
use 11.4.2 as a justification.

Is my book wrong?

2. ## Re: Does this proof contain an error

Originally Posted by mdm508

You will notice in the final step that 11.4.2 was used as a justification for $\log_2 n = k$
however, from the first line we recall that $2^k < n < 2^{k+1}$ which means that we should not be able to
use 11.4.2 as a justification.

Is my book wrong?
What is 11.4.2?

3. ## Re: Does this proof contain an error

Originally Posted by mdm508
You will notice in the final step that 11.4.2 was used as a justification for $\log_2 n = k$
however, from the first line we recall that $2^k < n < 2^{k+1}$ which means that we should not be able to
use 11.4.2 as a justification.
Why not? It appears to be a simple application of 11.4.2, what's wrong with that?

Originally Posted by Plato
What is 11.4.2?
There are two image attachments - open the first then click on "Next" and you'll see the second image.

4. ## Re: Does this proof contain an error

Originally Posted by Plato
What is 11.4.2?

5. ## Re: Does this proof contain an error

Originally Posted by ChipB
Why not? It appears to be a simple application of 11.4.2, what's wrong with that?
There are two image attachments - open the first then click on "Next" and you'll see the second image.
Thank you and Skeeter both. Yet for some reason that usual trick still does work for me.
I do see the objection. The inequality is less-than or equal in 11.4.2 but in the one on which it is used.
However, it is true that if $2^k<x<2^{k+1}$ then $k<\log_2(x)<k+1$; the log function is monotone.
The because the is no integer between integers $k~\&~k+1$ we get $\left\lfloor\log_2(x)\right\rfloor=k$.

6. ## Re: Does this proof contain an error

Originally Posted by Plato
the log function is monotone.
I am not familiar with this concept. Would you mind fleshing this out for me? I looked on wikipedia and they define monotone with more concepts I don't know.
Usually to be able to apply the floor function and get k, we need something of the form
$k \le x < k + 1~ \text{if the former is the case we know that} floor(x) = k$.
Clearly that is not the case here. I understand your saying there is something special about the log function that allows us to obtain k. Could you explain what that something is.

7. ## Re: Does this proof contain an error

Originally Posted by mdm508
I am not familiar with this concept. Would you mind fleshing this out for me? I looked on wikipedia and they define monotone with more concepts I don't know.
Monotone, simply means to preserve order. Non-increasing or non-decreasing function.

Originally Posted by mdm508
Usually to be able to apply the floor function and get k, we need something of the form
$k \le x < k + 1~ \text{if the former is the case we know that} floor(x) = k$. Clearly that is not the case here. I understand your saying there is something special about the log function that allows us to obtain k. Could you explain what that something is.
This really is not special to the log function. It has everything to do with the floor function. We prove that for any real number $t$ there is a unique integer $\left\lfloor t \right\rfloor$ that has the property that $\Large{\left\lfloor t \right\rfloor\le t<\left\lfloor t \right\rfloor+1}$.

There are nine integers from $2^3=8$ to $2^4=16$
\begin{align*}\text{If }{2^k}& < t < {2^{k + 1}}\\{\log _2}({2^k}) &< {\log _2}(t) < {\log _2}({2^{k + 1}})\\k &\le \left\lfloor {{{\log }_2}(t)} \right\rfloor < k + 1\\k &= \left\lfloor {{{\log }_2}(t)} \right\rfloor \end{align*}

8. ## Re: Does this proof contain an error

Originally Posted by Plato
\begin{align*}{\log _2}({2^k}) &< {\log _2}(t) < {\log _2}({2^{k + 1}})\\k &\le \left\lfloor {{{\log }_2}(t)} \right\rfloor < k + 1\end{align*}
how are we allowed to switch from $<~\text{to }\le$

9. ## Re: Does this proof contain an error

Originally Posted by mdm508
how are we allowed to switch from $<~\text{to }\le$
Face it, you are just not ready to do this level of proof.

10. ## Re: Does this proof contain an error

Originally Posted by Plato
Face it, you are just not ready to do this level of proof.
Your right! I need to really go back and learn all my algebra all over again. I'm just worried cause i have an algorithms course coming which is very proof heavy. And it worries me i can't do a one as basic as this

11. ## Re: Does this proof contain an error

Originally Posted by Plato
The because the is no integer between integers $k~\&~k+1 we get \left\lfloor\log_2(x)\right\rfloor=k$.
However, i think this is the answer to why we are able to switch from < to <=.

12. ## Re: Does this proof contain an error

thought about it some more, you can switch from < to <= because of a simple mathematical fact,
if something is < then its surely less than or equal. 2 < 6 and its also true that 2 <= 6. So we can apply the theorem with no problems.

Why didn't you just say this? I realized I want to react more strongly to this. You have no business assessing my mathematical capabilities. Furthermore, it is not helpful to me developing my skills. It only served to make me feel discouraged.