How do I find a closed form for this sequence?

Question

I want to find a closed form for $$\sum_{i=0,1,...}{\left\lfloor\frac{n}{2^i}\right\rfloor}$$

e.g.

1: 1
2: 2 + ⌊2/2⌋ = 3
3: 3 + ⌊3/2⌋ = 4
4: 4 + ⌊4/2⌋ + ⌊4/4⌋ = 7
5: 5 + ⌊5/2⌋ + ⌊5/4⌋ = 8
...
16: 16 + ⌊16/2⌋ + ⌊16/4⌋ + ⌊16/8⌋ + ⌊16/16⌋ = 31

For powers of 2 it is simply 2n-1, but for values in-between it is slightly smaller. Is there a closed form for this? How would I find it?

Answer 1

Assume that $2^{m-1}\le n<2^m$, so that the usual binary representation of $n$ has $m$ bits. Let that binary representation be $(b_mb_{m-1}\ldots b_1)_2$, where $b_m=1$, and note that

$$n=\sum_{k=1}^mb_k2^{k-1}\;.$$

Clearly $\left\lfloor\frac{n}{2^i}\right\rfloor=0$ when $i\ge m$, and $$\left\lfloor\frac{n}{2^i}\right\rfloor=(b_m\ldots b_{i+1})_2$$ when $0\le i<m$, so the number in question is

$$f(n)=\sum_{k=1}^m(b_m\ldots b_k)_2\;.\tag{1}$$

Fix $k\in\{1,\ldots,m\}$; $b_k$ appears in exactly $k$ terms of $(1)$, moving one place to the right in each additional division by $2$, so it contributes

$$b_k\sum_{i=0}^{k-1}2^i=b_k(2^k-1)$$

to the sum. Thus,

$$f(n)=\sum_{b_k=1}(2^k-1)\;.$$

Let $\beta(n)$ be the number of $1$ bits in $(b_m\ldots b_1)_2$; clearly

$$f(n)=\sum_{b_k=1}2^k-\beta(n)=2\sum_{k=1}^mb_k2^{k-1}-\beta(n)=2n-\beta(n)\;.$$

Answer 2

As already noted, representation in binary is key. So write $$n = \sum_{j=0}^ln_j2^j\quad \text{with}\quad n_j ∈ \{0, 1\}.$$ Then the sum takes the form $$s_n = \sum_{i=0}^∞\left\lfloor\sum_{j=0}^ln_j2^{j-i}\right\rfloor$$ For $i ≥ j$ the summands are integral and all other can be estimated by $$\sum_{j=0}^{i-1}n_j2^j ≤ \sum_{j=0}^{i-1}2^j < 2^i,$$ so after division by $2^i$ their integral part vanishes. For $i > l$ the whole inner sum vanishes. Then we get $$s_n = \sum_{i=0}^l\sum_{j=i}^ln_j2^{j-i} = \sum_{j=0}^l\left(n_j2^j\sum_{i=0}^j2^{-i}\right) = \sum_{j=0}^ln_j2^j(2-2^{-j})\\=2n - \sum_{j=0}^ln_j =: 2n - \mathrm{bitcount}(n)$$