prove it $\displaystyle\sum _{ i=1 }^{ \infty }{\biggl\lfloor \frac{n}{2^{i}}+\frac{1}{2}\biggr\rfloor}=n$

Question

I found this problem in a list. I would like to know if the statement is correct and if anyone could give me a hint on how to solve it.

Consider an integer $n\geqslant 1$ and integers i , $1\leq i \leq n$. For each $k = 0, 1, 2, \dots$ find the number of i's that are divisible by $2^k$ but not by $2^{k+1}$. So prove $$\displaystyle\sum _{ i=1 }^{ \infty }{\biggl\lfloor \frac{n}{2^{i}}+\frac{1}{2}\biggr\rfloor}=n$$

Answer 1

Here's a proof that is way too long but doesn't involve that clever idea.

Let $n =\sum_{k=0}^d b_k2^k $ where $b_d = 1$ so $2^d \le n \le 2^{d+1}-1 $.

$\begin{array}\\ \dfrac{2^{i-1}+n}{2^i} &\le \dfrac{2^{i-1}+2^{d+1}-1}{2^i}\\ &\lt 1\\ \end{array} $

if $2^{i-1}+2^{d+1}-1 \lt 2^i $ or $2^{d+1} \lt 2^{i-1}+1 $ or $d+1 \le i-1 $ or $i \ge d+1 $.

Then

$\begin{array}\\ s(n) &=\sum _{ i=1 }^{ \infty }{\left\lfloor \dfrac{n}{2^{i}}+\dfrac{1}{2}\right\rfloor}\\ &=\sum _{ i=1 }^{ \infty }{\left\lfloor \dfrac{2^{i-1}+n}{2^i}\right\rfloor}\\ &=\sum _{ i=1 }^{d+1}{\left\lfloor \dfrac{2^{i-1}+n}{2^i}\right\rfloor}\\ &=\sum _{ i=1 }^{d+1}{\left\lfloor \dfrac{2^{i-1}+\sum_{k=0}^d b_k2^k}{2^i}\right\rfloor}\\ &=\left\lfloor \dfrac{2^{d}+\sum_{k=0}^d b_k2^k}{2^{d+1}}\right\rfloor +\left\lfloor \dfrac{2^{d-1}+\sum_{k=0}^d b_k2^k}{2^d}\right\rfloor+\sum _{ i=1 }^{d-1}{\left\lfloor \dfrac{2^{i-1} +\sum_{k=0}^d b_k2^k}{2^i}\right\rfloor}\\ &=\left\lfloor \dfrac{2^{d}+2^d+\sum_{k=0}^{d-1} b_k2^k}{2^{d+1}}\right\rfloor +\left\lfloor \dfrac{2^{d-1}+2^d+\sum_{k=0}^{d-1} b_k2^k}{2^d}\right\rfloor+\sum _{ i=1 }^{d-1}{\left\lfloor \dfrac{2^{i-1} +\sum_{k=0}^d b_k2^k}{2^i}\right\rfloor}\\ &=\left\lfloor 1+\dfrac{\sum_{k=0}^{d-1} b_k2^k}{2^{d+1}}\right\rfloor +\left\lfloor 1+ \dfrac{2^{d-1}+\sum_{k=0}^{d-1} b_k2^k}{2^d}\right\rfloor+\sum _{ i=1 }^{d-1}{\left\lfloor \dfrac{2^{i-1} +\sum_{k=0}^d b_k2^k}{2^i}\right\rfloor}\\ &=1 + 1+b_{d-1} +\sum _{ i=1 }^{d-1}{\left\lfloor \dfrac{2^{i-1} +\sum_{k=i-1}^d b_k2^k}{2^i}\right\rfloor}\\ &=2+b_{d-1} +\sum _{ i=1 }^{d-1}{\left\lfloor \dfrac{2^{i-1} +b_{i-1}2^{i-1}+\sum_{k=i}^d b_k2^k}{2^i}\right\rfloor}\\ &=2+b_{d-1} +\sum _{ i=1 }^{d-1}\left\lfloor \dfrac{2^{i-1} +b_{i-1}2^{i-1}}{2^i}\right\rfloor +\sum _{ i=1 }^{d-1}\sum_{k=i}^d b_k2^{k-i}\\ &=2+b_{d-1} +\sum _{ i=1 }^{d-1} b_{i-1} +\sum _{ i=1 }^{d-1}\sum_{k=i}^d b_k2^{k-i}\\ &=1+b_{d-1}+\sum _{ i=0 }^{d-2} b_{i} +\sum _{ i=1 }^{d}\sum_{k=i}^d b_k2^{k-i}\\ &=\sum _{ i=0 }^{d} b_{i} +\sum _{ i=1 }^{d}\sum_{k=i}^d b_k2^{k-i}\\ &=\sum _{ i=0 }^{d} b_{i} +\sum _{ k=1 }^{d}\sum_{i=1}^k b_k2^{k-i}\\ &=\sum _{ i=0 }^{d} b_{i} +\sum _{ k=1 }^{d}b_k\sum_{i=1}^k 2^{k-i}\\ &=\sum _{ i=0 }^{d} b_{i} +\sum _{ k=1 }^{d}b_k\sum_{i=0}^{k-1} 2^i\\ &=\sum _{ i=0 }^{d} b_{i} +\sum _{ k=1 }^{d}b_k(2^k-1)\\ &=\sum _{ k=0 }^{d}b_k2^k\\ &=n\\\end{array} $

Oy.

Answer 2

Hint:

$$\lfloor 2y\rfloor-\lfloor y\rfloor=\lfloor y+1/2\rfloor$$, take $y=x/2^i$ to write $$\lfloor x/2^i+1/2\rfloor=\lfloor x/2^{i-1}\rfloor -\lfloor x/2^i\rfloor.$$ Next perform telescopic summation.

Answer 3

$$[2y]−[y]=[y+1/2]$$ is a very nice trick to solve this question. The solution is so clean and beautiful.

But I am thinking, if I did not see this identity before. It is hard for me to reach this solution. I try to work out a trickless solution using M.I. concept.

Name the question as T(n).

Prove T(1) is true: obvious.

Assume T(k) is true for all k <=2m where m is any integer >=1.

Prove T(2m): First term of summation =m, Show other terms = T(m) = m. Then summation = m+m = 2m.

Prove T(2m+1): First term of summation = m+1, Show other terms = T(m) = m. Then summation = m+1+m = 2m+1.

Then T(n) is true for all integer n>=1.

Answer 4

Here's one way to do it inductively:

The statement is clearly true for $n=0$. Assume that the statement is now true for $n$.

We claim that it's enough to show that $n+2^i+1$ has only ones in its binary expansion for exactly one $i$.

This follows from the fact that the given floor only increases when taking $n\mapsto n+1$ if $n/2^i+1/2$ ends in only ones in the decimal part of the binary expansion. One can verify that this is equivalent to the above condition.

As an example, for $n=10=1010_2$, this occurs when $i=2$.

To prove this is true in general, notice that this is just the same as adding $1$ to the $i$th digit of $n+1$ in binary; in fact, it's clear that once we hit the first zero (from the right) in its expansion, that we have found such an $i$ that works.

To finish, note that $i$ is also unique since adding $1$ to a digit to the right of the $i$th digit results in that digit becoming $0$, and adding $1$ to the left of the $i$th digit results in the $i$th digit still being $0$, which completes the inductive step.