This is IMO 1968-6. Pierre.

It immediately comes from base 2 representation. Indeed, suppose $n=\overline{a_{n}...a_2a_1a_0}$ (actually, we know that it containes at most $n-1$ digit for $n\geq 1$). And we have $\left[\frac{n+2^{k-1}}{2^{k}}\right]=\left[\frac{n}{2^{k}}+\frac{1}{2}\right]=\overline{a_{n-1}...a_{k}}+a_{k-1}$ . Therefore the whole sum is $\sum a_k(2^k-1)+\sum a_{k-1}= \sum a_k2^k=n$.

Thank you for your nice solution!

keira_khtn wrote: Let $ n$ be a natural number. Prove that \[ \left\lfloor \frac {n + 2^0}{2^1} \right\rfloor + \left\lfloor \frac {n + 2^1}{2^2} \right\rfloor + \cdots + \left\lfloor \frac {n + 2^{n - 1}}{2^n}\right\rfloor = n. \]

I'll complete Johan Gunardi's hint. First a lemma: $ \left\lfloor \alpha + \frac{1}{2} \right\rfloor = \left\lfloor 2\alpha \right\rfloor - \left\lfloor \alpha \right\rfloor$ Let $ \alpha = n + \delta$ where $ n \in \mathbb{Z}, \delta \in [0;1)$. Then it's equivalent to proving: $ \left\lfloor \delta + \frac{1}{2} \right\rfloor + \left\lfloor \delta \right\rfloor = \left\lfloor 2\delta\right\rfloor$ $ \iff$ $ \left\lfloor \delta + \frac{1}{2} \right\rfloor = \left\lfloor 2\delta\right\rfloor$. (Which is true by taking the two cases $ \delta < \frac{1}{2}$ and $ \delta \ge \frac{1}{2}$) We want to prove that: $ \sum_{k=1}^n\left\lfloor \frac {n}{2^k}+\frac{1}{2} \right\rfloor = n$ But by the lemma: $ \sum_{k=1}^n\left\lfloor \frac {n}{2^k}+\frac{1}{2} \right\rfloor = \sum_{k=1}^n\left\lfloor \frac {n}{2^{k-1}} \right\rfloor - \left\lfloor \frac {n}{2^k} \right\rfloor = \left\lfloor n \right\rfloor - \left\lfloor \frac {n}{2^n} \right\rfloor = n$ so it is obviously true

You can also use Hermite's Identity to prove this!

manjil wrote: You can also use Hermite's Identity to prove this! Could you explain a bit further?

By Hermite's Identity, we have $ \lfloor x \rfloor + \left\lfloor x+\frac12 \right\rfloor = \lfloor 2x \rfloor$. Hence $ \left\lfloor x+\frac12 \right\rfloor=\lfloor 2x \rfloor- \lfloor x \rfloor$.

cosinator wrote: Here is a rather contrived proof (but still a proof nonetheless): Consider the binary representation of $ n$: $ n = 2^{u_0} + 2^{u_1} + \cdots + 2^{u_t}$. Then it is easy to see that $ \left\lfloor\frac {n + 2^{k - 1}}{2^k}\right\rfloor = 2^{u_i - k} + 2^{u_{i + 1} - k} + \cdots + 2^{u_t - k} + (0)\text{ if }u_{i - 1} < k - 1\text{ and } + (1)\text{ if }u_{i - 1} = k - 1$ for $ u_i\ge k$. Thus, the sum in question is equivalent to $ (2^{u_0 - 1} + 2^{u_0 - 2} + \cdots + 1) + (2^{u_1 - 1} + 2^{u_1 - 2} + \cdots + 1) + \cdots + (2^{u_t - 1} + 2^{u_t - 2} + \cdots + 1) + t + 1$ $ = 2^{u_0} - 1 + 2^{u_1} - 1 + \cdots + 2^{u_t} - 1 + t + 1$ $ = n$

The given sum is equal to the sum $ \sum \left\lfloor\frac {n}{2^k}\right\rfloor +$ sum of digits of $n$ in binary. If we compare $ \sum \frac {n}{2^k} - \sum \left\lfloor\frac {n}{2^k}\right\rfloor $ it is clear the error equals the sum of these digits. If the digit represents $2^x$ then its contribution to the error is going to be $\frac{1}{2}$ for $k=x+1$,$\frac{1}{4}$ for $k=x+2$ and so on.

Can somebody check if this solution works?

I think yours works haha since I decided to use induction as well.

By Hermite's Identity, $$\left\lfloor\frac{n}{2^i}\right\rfloor+\left\lfloor\frac{n}{2^i}+\frac{1}{2}\right\rfloor=\left\lfloor\frac{n}{2^{i-1}}\right\rfloor.$$Hence, $$\sum_{i=1}^{\infty}\left\lfloor\frac{n}{2^i}+\frac{1}{2}\right\rfloor=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{2^{i-1}}\right\rfloor-\left\lfloor\frac{n}{2^i}\right\rfloor=\left\lfloor\frac{n}{2^{1-1}}\right\rfloor=n.$$$\square$

Quite nice. The core of this problem is in the following: Lemma: For positive, real $n$, we have $$\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n+1}{2}\right\rfloor=\left\lfloor{n}\right\rfloor.$$Proof: Assume $\lfloor{n}\rfloor$ is even (the case for odd is similar). We have $n=2m+\text{fractional n}$, with $m$ an integer. Thus, we get $\left\lfloor\frac{n}{2}\right\rfloor=m$ after some computation. $$n+1=2m+1+\text{fractional n} \rightarrow\left\lfloor\frac{n+1}{2}\right\rfloor=m+\left\lfloor\frac{1+\text{\text{fractional} n}}{2}\right\rfloor=m.$$The required result follows. $\square$ Our problem now reduces as $\sum_{k=1}^n \left\lfloor{n}\right\rfloor-\left\lfloor\frac{n}{2^n}\right\rfloor=n$, as needed. $\blacksquare$

Note that $[x]+[x+1/2]=[2x]$ for all $x>0.$ This follows from casework on fractional part. Then LHS is $[n]-[n/2^n]=n.$ Q.E.D.

Here is a better version of superagh's solution. (In my opinion, his induction hypothesis application does not seem valid enough, as you cannot mix $k$ and $m$ just like that, as the initial statement has only one variable and not two.) We use strong induction on $n$. For $n=1$ we have only one summand and it is $\left\lfloor \frac{1+2^0}{2^1}\right \rfloor = 1$. Now assume the required equality holds for all positive integers less than $n$ and write $n=2^k+m$ where $0 \leq m \leq 2^{k}-1$. Since $\left\lfloor \frac{2^k + m + 2^s}{2^{s+1}} \right\rfloor = 2^{k-s-1} + \left\lfloor \frac{m+2^s}{2^{s+1}} \right\rfloor$ for $s\leq k-1$ and $\left\lfloor \frac{2^k + m + 2^k}{2^{k+1}} \right \rfloor= 1$, on the left we have $\left\lfloor \frac{m+2^0}{2^1} \right\rfloor + \left\lfloor \frac{m+2^1}{2^2} \right\rfloor + \left\lfloor \frac{m+2^2}{2^3} \right\rfloor + \cdots + \left\lfloor \frac{m+2^{n-1}}{2^n} \right\rfloor + 2^{k-1} + 2^{k-2} + \cdots + 1 + 1 = \left\lfloor \frac{m+2^0}{2^1} \right\rfloor + \left\lfloor \frac{m+2^1}{2^2} \right\rfloor + \left\lfloor \frac{m+2^2}{2^3} \right\rfloor + \cdots + \left\lfloor \frac{m+2^{n-1}}{2^n} \right\rfloor + 2^k$, while on the right we have $2^k + m$. Since $\left\lfloor \frac{m+2^s}{2^{s+1}} \right\rfloor = 0$ for $s\geq k$ (as $m < 2^k$), we reduce to proving $$ \left\lfloor \frac{m+2^0}{2^1} \right\rfloor + \left\lfloor \frac{m+2^1}{2^2} \right\rfloor + \left\lfloor \frac{m+2^2}{2^3} \right\rfloor + \cdots + \left\lfloor \frac{m+2^{k-1}}{2^k} \right\rfloor = m. $$For if $m \geq k$, then on the left we can add the $0$ summands $\left\lfloor \frac{m+2^{s-1}}{2^s}\right \rfloor$, $s=k+1,\ldots,m$ and to desire an equality which follows from the induction hypothesis as $m < 2^k < n$. Now suppose $m\leq k-1$. Then $\left\lfloor \frac{m + 2^{s-1}}{2^s} \right \rfloor = \left \lfloor \frac{m}{2^s} + \frac{1}{2} \right \rfloor = 0$ for $s\geq m+1$ since $\frac{m}{2^{m+1}} < \frac{1}{2} \Leftrightarrow 2^m > m$ (by a simple induction on $m$). So we may remove the $0$ summands $\left\lfloor \frac{m+2^{s-1}}{2^s}\right \rfloor$, $s=m+1,\ldots,k-1$ and to desire an equality which follows from the induction hypothesis as $m < 2^k < n$.

Simplify the problem into the following: \[\left \lfloor \frac{n}{2} + \frac{1}{2} \right \rfloor + \left \lfloor \frac{n}{4} + \frac{1}{2} \right \rfloor + \left \lfloor \frac{n}{8} + \frac{1}{2} \right \rfloor + \left \lfloor \frac{n}{16} + \frac{1}{2} \right \rfloor + \cdots.\]Now we use the identity that $\lfloor x \rfloor + \lfloor x + 1/2 \rfloor = \lfloor 2x \rfloor$, and rearranging we find $\lfloor x + 1/2 \rfloor = \lfloor 2x \rfloor - \lfloor x \rfloor$. Hence our initial sum becomes the following: \[\left(\lfloor n \rfloor - \left \lfloor \frac{n}{2} \right \rfloor \right)+ \left(\left \lfloor \frac{n}{2} \right \rfloor - \left \lfloor \frac{n}{4} \right \rfloor \right) + \left(\left \lfloor \frac{n}{4} \right \rfloor - \left \lfloor \frac{n}{8} \right \rfloor \right) + \cdots = \lfloor n \rfloor = n, \]as desired. $\blacksquare$