$\left \lfloor{\log(n-1)}\right \rfloor$ = $\left \lfloor{\log(n)}\right \rfloor$ for n odd

Question

I have been trying to prove the worst case for the binary-search algorithm. During the proof I came to this equality: $\left \lfloor{\log(n-1)}\right \rfloor$ = $\left \lfloor{\log(n)}\right \rfloor$ for n odd(here lg means logarithm with base 2). Can anyone help me with proving this equality ?

Answer 1

$\lfloor \log_2(n) \rfloor = k$ means that

$k\leq \log_2(n) < k+1$

It follow that

$2^k \leq n < 2^{k+1}$

But $n$ is odd, $n \neq 2^k$, hence $2^k < n$,and as both are integers, $2^k \leq n-1$ hence

$2^k \leq n-1 < 2^{k+1}$

So $k< \log_2(n-1) <k+1$ and we have the result