#Algorithms How to solve this series?

Question

$n/2+n/4+n/8+....+4+2+1 = n−1$

How this evaluates to $n-1?$

Answer 1

Just try to look at this way :

$1+2+4+.....+n/4+n/2$

first of all get no of terms(Kth term) :(IT is a GP series so formula $a.r^{k-1}=k^{th}$ term )

so $1.2^{k-1}=n/2$

$k=\log_2 n$

sum$=\frac{a(r^{k-1})}{r-1}$

put values You will get : $2^{\log n}-1 = n – 1.$

Comments

Thanks brother! You've been real help. :)