prove it $\displaystyle\sum _{ i=1 }^{ \infty }{\biggl\lfloor \frac{n}{2^{i}}+\frac{1}{2}\biggr\rfloor}=n$ 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$$
 A: 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.
A: $$[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.
A: 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.
A: 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.
