I am trying to figure out how to write the summation for 2+4+8+16+...+1024. Clearly my answer below is wrong by 1:
I tried to apply the following summation formula but I guess I did not do it properly:
Please keep in mind I am not a mathy person. This is for an algorithm analysis course.
$\endgroup$65 Answers
$\begingroup$Your summation is $$ \sum_{i=1}^{10}2^i= 2\sum_{i=1}^{10}2^{i-1}= 2\sum_{i=0}^{9}2^{i}= 2(2^{10}-1)= 2^{11}-2=2046 $$ Note the difference in the starting point between your problem and the formula you quote.
$\endgroup$$\begingroup$\begin{align} 2+4+8+\ldots+1024 &= x \\ 2+2+4+8+\ldots+1024 &= 2+ x \\ (2+2)+4+8+\ldots+1024 &= 2+x \\ 4+4+8+\ldots+1024 &= 2+x \\ (4+4)+8+\ldots+1024 &= 2+x \\ 8+8+\ldots+1024 &= 2+x \\ &\ \vdots\\ 1024+1024 &= 2+x \\ 2048 &= 2+x \\ -2+2048 &= x \end{align}
I hope this helps $\ddot\smile$
$\endgroup$1$\begingroup$The general formula for the sum of consecutive terms of a geometric series, not necessarily starting at $1$ is the following: $$\sum_{k=m}^{k=n}q^k=\frac{q^{n+1}-q^m}{q-1}.$$ Factoring $q^m$ in the sum leads to applying the base formula with last exponent $n-m$, but it's worth knowing it for its own sake.
$\endgroup$$\begingroup$"I noticed the difference in i but I am not really sure how to be able to change the summation formula to account for that, like how I can change the summation formula to consider different values of i :S "
The sumation index makes all the difference.
You can always do this:
$\sum_{i=0}^n a_i = \sum_{i=0}^k a_i + \sum_{i=k+1}^n a_i$ for any $0 < k < n$
So $\sum_{i=0}^2 2^i = 2^0 + \sum_{i=1}^n 2^i=$
$ 1 + \sum_{i=1}^n 2^i$ so $\sum_{i=1}^n 2^i = \sum_{i=0}^2 2^i - 1 = $
$(2^{n+1}-1) - 1 = 2^{n+1} - 2$.
....
and if you are really clever you can to this.
$\sum_{i=1}^n 2^i$; for each $i$ let's let $i = k+ 1$ so....
$\sum_{i=1;\text{ or } k = 0}^{i = n; \text{ or } k=n-1} (2^i=2^{k+1}) =$
$\sum_{k = 0}^{n-1} 2^{k+1} =$
$\sum_{k=0}^{n-1} 2*2^k = 2\sum_{k=0}^{n-1}2^k=$
$2(2^n - 1) = 2^{n+1} - 2$.
You can sleep on the second part.
$\endgroup$$\begingroup$\begin{align} 2+4+8+\ldots+1024 &= \\ (-1+1)+2+4+8+\ldots+1024 &= \\ -1+(1+2+4+8+\ldots+1024) &= \\ -1 + \sum_{i=0}^{10}2^i \\ \end{align}
Now you can use the formula you mentioned.
$\endgroup$
