Prove that $\lfloor\log_2n\rfloor$ is $\Theta(\log_2n)$

Question

Having a little trouble getting started on this proof. Any advice on how to deal with this floor function is appreciated.

Prove that $\lfloor\log_2n\rfloor$ is $\Theta(\log_2n)$.

Here's what i have so far: By definition of $\Theta(g(n))$ we will need to find three positive real numbers, $A, B$, and $k\ge r$ such that the following is true:

$A\log_2n\le\lfloor\log_2n\rfloor\le B\log_2n$, $\forall n\ge k$ Where $(n,k)\in\mathbb Z$

Let $A=\frac12$, $B=2$, and $k=2$

$\frac12log_2n\le\lfloor\log_2n\rfloor \le2\log_2n$, $\forall n\ge2$

Therfore $\lfloor\log_2n\rfloor$ is $\Theta(\log_2n)$

Answer 1

By definition of the floor function $$\log_2n\le\lfloor\log_2n\rfloor<\log_2n+1$$ So we can take $A=1$ immediately. Then prove $x+1\le2x$ for $x\ge1$ and substitute $x=\log_2n$; this shows that $B=2$ and $k=2$ works. Hence we can conclude $\lfloor\log_2n\rfloor=\Theta(\log_2n)$.