Geometric Series $\sum_{k=0}^{\log_{2}n}\frac{n}{2^k}$

Question

I am trying to figure out how to solve this summation:

$$\sum_{k=0}^{\log_{2}n}\frac{n}{2^k}$$.

(k and n are positive real integers)

I recognize that this is a geometric series if we do this:

$$\sum_{k=0}^{\log_{2}n}n\cdot 2^{-k}$$

Im confused on where to solve it because of the $\log_{2}n$.

Answer 1

$$S=n\sum_{k=0}^{-1+\log_2 n} 2^{-k} = \frac{2^{-(\log_2 n)}-1}{1/2-1} = n \frac{1/n-1}{-1/2}=2(n-1).$$ and $$S=n\sum_{k=0}^{\log_2 n} 2^{-k} = n \frac{2^{-(\log_2 n)-1}-1}{1/2-1} = n \frac{1/(2n)-1}{-1/2}=2n-1.$$ So $\log_2 n$ not being an integer, we may assert that $$2n-2 <S_n <2n-1.$$ I guess nothing better than this could be done.

Answer 2

For any natural $m$,

$$\sum_{k=0}^m\frac n{2^k}=2n\left(1-\frac1{2^{m+1}}\right).$$

Now up to you to figure out what $m$ is (read the comments by lulu and Barry Cipra).

Answer 3

Hint: According to rules when using the sigma-symbol $\sum$ we have for real $a\geq 0$: \begin{align*} \sum_{k=0}^a f(k)&=\sum_{k=0}^{\lfloor a\rfloor} f(k)\\ &=f(0)+f(1)+\cdots+f\left(\lfloor a\rfloor\right) \end{align*} where $\lfloor a\rfloor$ means the greatest integer less or equal to $a$. See for instance chapter 2: Sums , section 2.1 Notation in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.

We obtain \begin{align*} \color{blue}{\sum_{k=0}^{\log_{2}n}n\cdot 2^{-k}}&=n\sum_{k=0}^{\lfloor \log_{2}n \rfloor}2^{-k}\\ &=n\cdot\frac{1-2^{-\left(\lfloor\log_{2}n\rfloor +1\right)}}{1-\frac{1}{2}}\\ &\,\,\color{blue}{=n\left(2-2^{-\lfloor\log_{2}n\rfloor}\right)}\tag{1} \end{align*}

In the special case $n=2^N$we have $$\lfloor \log_{2}n \rfloor=\lfloor \log_{2}2^N \rfloor=\lfloor N\rfloor=N$$ and obtain from (1): \begin{align*} \sum_{k=0}^{\log_{2}2^N}2^N\cdot 2^{-k}=2^N\sum_{k=0}^{N} 2^{-k}=2^N\left(2-2^{-N}\right)=2^{N+1}-1 \end{align*}