Using partitions and 1-1 correspondence of the set {1, 2, ... n}, prove that $\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{n+2}{4}\rfloor+\lfloor\frac{n+4}{8}\rfloor+\lfloor\frac{n+8}{16}\rfloor+ \dots=n$
Hint:
First, we look at a small case. Let n = 25. We discover that the formula works.
Now, we partition the set of positive integers from 1 to 25 according to the number of powers of 2 that divide them. Let $S_k$ be the set of positive integers from 1 to 25 that have exactly k factors of 2. We list the results in the following table:
$k$ is $0$ then $S_k$ is $\{1, 3, 5,...,25\}$ and $\#(S_k)$ is 13
$k$ is $1$ then $S_k$ is $\{2, 6, 10,...,22\}$ and $\#(S_k)$ is 6
$k$ is $2$ then $S_k$ is $\{4, 12, 20\}$ and $\#(S_k)$ is 3
$k$ is $3$ then $S_k$ is $\{8, 24\}$ and $\#(S_k)$ is 2
$k$ is $4$ then $S_k$ is $\{16\}$ and $\#(S_k)$ is 1