Solve $n + n/2 + n/4 + n/8 + \dots$ up to $\log n$ terms
This looks like Harmonic series. But I couldn't find a formula to calculate the sum of the series up to $\log n$ terms. Can anyone solve it please.
Solve $n + n/2 + n/4 + n/8 + \dots$ up to $\log n$ terms
This looks like Harmonic series. But I couldn't find a formula to calculate the sum of the series up to $\log n$ terms. Can anyone solve it please.
It's $n$ times the geometric series $1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots \frac{1}{2^{\log n - 1}}$. Do you know how to find the value of a geometric sum?
I'll start by making some simplifications. Since you didn't specify the base for your log function, I'll assume that it is some integer $b>1$. Also, since it wasn't completely clear what you meant by "up to $\log n$ terms", I'll assume that we want $\log n$ to be an integer. Neither of these assumptions are necessary; they just make calculations easier.
Since $\log_bn$, the number of terms, is assumed to be an integer, we must have $n=b^k$ for some integer $k>0$. Then your expression will be $ b^k(\underbrace{1+\frac{1}{2}+\frac{1}{4}+\cdots + \frac{1}{2^{k-1}}}_{k\text{ terms}})=b^k\left(\frac{1-(1/2^k)}{1-(1/2)}\right)=2b^k\left(1-\frac{1}{2^k}\right) $ by the formula for the sum of a geometric series. Now since we assumed $n=b^k$ we'll see that your sum will be $ 2b^k\left(1-\frac{1}{2^k}\right)=2n\left(1-\frac{1}{2^{\log_bn}}\right)=2n\left(1-\frac{1}{n^{\log_b2}}\right) $ using the useful and frequently-forgotten identity $a^{\log_bc}=c^{\log_ba}$. As a reality check, if $b=2$ and $k=4$ (so $n=2^4=16$) we'll have the sum $ 16\left(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\right)=30=32\left(1-\frac{1}{16}\right)=2\cdot16\left(1-\frac{1}{16^{\log_22}}\right) $
Let us assume that $n=2^k$ and let your sum be $S=\sum_{i=0}^k n 2^{-k}$. Then $S$ denotes the number of nodes in a complete balanced binary tree of height $k$ with $n$ leaves. Such a tree has $2^{k+1}-1$ nodes, which can be easily shown by induction. Thus in your case we have $S=2n-1$.