Formule to Remember

1. $$\sum_{i=1}^{log_2n}x = 2^1 + 2^2 + ... 2^{log(n)} $$Taking 2 common we get $$\sum_{i=1}^{log_2n}x = 2(2^0 + 2^1 + ... 2^{log(n-1)}) $$ Now, we know the sum of 2^0 till 2^n-1 = 2^n, thus $$\sum_{i=1}^{log_2n}x = 2(2^{log(n-1)+1}-1) $$ example, let's say n = 8 Thus, log n = 3 summation from 0 to log(n-1) = 1 + 2 + 4 = 7 i.e. 2^3 -1 = 7 $$\sum_{i=1}^{log_2n}x = 2(n-1) $$