Proving that $\lfloor n\rfloor -\left\lfloor\frac{n}{2^{k+1}}\right\rfloor=\lfloor n\rfloor$

Question

How can I prove this? $$\lfloor n\rfloor -\left\lfloor\frac{n}{2^{k+1}}\right\rfloor=\lfloor n\rfloor$$

I considered the base case, $k=0$

$$\lfloor n\rfloor -\left\lfloor\frac{n}{2}\right\rfloor=\lfloor n\rfloor -0=\lfloor n\rfloor$$

But this is only valid if $n<1$. Then if $k\longrightarrow \infty $, the problem is changing only if $n$ is small enough so that $\left\lfloor\frac{n}{2}\right\rfloor=0$. So I am not sure how to prove that.

Any hints appreciated.

Thanks

Answer 1

The required condition is that $$\left\lfloor\frac{n}{2^{k+1}}\right\rfloor=0$$

This is only true if

$$0\leq n<2^{k+1}\iff k > \log_2\left(\frac{n}{2}\right)$$

Answer 2

This is in general false becasue $n$ and $k$ are independent of each other. However, if you meant $$\lfloor n \rfloor-\lfloor\frac{n}{2^{n+1}}\rfloor=\lfloor n \rfloor$$ for $n \ge 0$ then this is true.

It is just a matter of proving that $$\lfloor\frac{n}{2^{n+1}}\rfloor = 0.$$ To see that it must hold, notice that the number within the brackets must be between $0$ and $1$. Then notice that it is true for $n=0$, and that the exponential function is always increasing and faster so than the linear function.

Answer 3

If we have that $ \lfloor n \rfloor - \left \lfloor \frac{n}{2^{k + 1}} \right\rfloor = \lfloor n \rfloor $ then it must be that $\left \lfloor \frac{n}{2^{k + 1}} \right \rfloor = 0$ which means that $n < 2^{k + 1}$ which holds when $\lg n < k + 1$, or $\lg n - 1 < k$. Therefore if $k > \lg n - 1$ then $\left \lfloor \frac{n}{2^{k + 1}} \right\rfloor = 0$.