# Sum of power of $k$th least significant set bit

Assume $k$ and $n$ are non-negative integers and define $f(k,n)$ to be the index of the $k$th least significant set bit and define $f(k,n) = 0$ if $n$ has fewer than $k$ set bits. For example, if $k=2$ and $n=88 = 1011000 \text{ (base } 2)$, then $f(k,n)= 4$. How can you compute the asymptotics of

$$S_{n,k} = \sum_{i=0}^n 2^{f(k,i)} \, ?$$

For $k=1$ and $n = 0\dots10$, we get $1, 2, 4, 5, 9, 10, 12, 13, 21, 22, 24$.

For $k=2$ and $n = 0\dots10$, we get $1, 2, 3, 5, 6, 10, 14, 16, 17, 25, 33$

-
add comment

## 1 Answer

If in the $N$-bit number the $k$'th lest significant bit sits int the position $m$, there are exactly $k-1$ bits in the positions $0 \to m-1$, therefore, there are exactly $2^{N-m-1}* (^{m-1}_{k-1})$ such numbers, each contributing $2^{N-1}* (^{m-1}_{k-1})$ to the total.

Can you take it from here?

-
This isn't obvious to me. For fixed $k$ do you get something like $n\log^{k}{n}$? However we know it can't be more than $\sum_{i=0}^n (i+1)$ so that can't be the full solution. –  marshall Feb 14 at 11:21
add comment