Function and Floor Properties Call a function $f : x \mapsto \lfloor x / 2\rfloor$. Let $x_0 = n$, then $x_1 = \lfloor n / 2 \rfloor$ and $x_2 = \lfloor \lfloor n / 2 \rfloor \rfloor / 2 \rfloor$.... $x_k = f(x_{k-1}).$
How do we prove that $x_k = \left\lfloor \frac{n}{2^k} \right\rfloor$?
My best guess is induction but I'm not sure where to begin. I started off with using the floor definition but it got messy.
 A: Hint:
Consider $n$ expressed in binary, and for any natural number $m$, compare it to $\left\lfloor \frac{n}{2^m} \right\rfloor$ expressed in binary. Note the last $m$ binary digits are removed. Thus, after applying the $\left\lfloor \frac{n}{2} \right\rfloor$ operation $k$ times, you've removed the last $k$ binary digits, so it'll be the same as the result of $\left\lfloor \frac{n}{2^k} \right\rfloor$.
A: Induction is a good idea.
Note if $x_k = [\frac n{2^k}]$ then 
$x_k \le \frac n{2^k} < x_k + 1$ so 
$\frac {x_k}2 \le \frac n{2^{k+1}} < \frac {x_k}2 + \frac 12$
Now if $x_k$ is even than $\frac {x_k}2$ is an integer and
$\frac {x_k}2 \le \frac n{2^{k+1}} < \frac {x_k}2 + \frac 12<\frac {x_k}2+1$
And $x_{k+1} = [\frac {x_k}2] = \frac {x_k}2$ and $[\frac n{2^{k+1}}] = [\frac {x_k}2]=x_{k+1}$
And if $x_k$ is odd then $\frac {x_k}2 \pm \frac 12$ are integesr.
$\frac {x_k}2-\frac 12 <\frac {x_k}2 \le \frac n{2^{k+1}} < \frac {x_k}2 + \frac 12$
And both $x_{k+1} = [\frac {x_k}2] = \frac {x_k}2-\frac 12 $ and $[\frac n{2^{k+1}}] =\frac {x_k}2-\frac 12 =  [\frac {x_k}2] =x_{k+1}$
