The sequence 1 + (1+1) + (1+1+2) + (1+1+2+4) + (1+1+2+4+8) + ..

Question

I am working on a brute-force algorithm for a hard problem where the number of operations $S[n]$ seem to grow as a function of $n$ as follows:

$$ \begin{align} S[1]& = 1\\ S[2]& = 1 + (1+1)\\ S[3]& = 1 + (1+1) + (1+1+2)\\ S[4]& = 1 + (1+1) + (1+1+2) + (1+1+2+4)\\ S[5]& = 1 + (1+1) + (1+1+2) + (1+1+2+4) + (1+1+2+4+8) \end{align} $$

Meaning, the algorithm runs $S[i]$ constant-time operations for an input containing $i$ elements.

Given the above, how would one go about deriving a formula for $S[n]$?

Answer 1

$1 + 2 + 4 + ...... + 2^k = 2^{k+1} - 1$.

So $(1+1+2+4+....... + 2^k) = 2^{k+1}$.

So $S[n] = 1 + (1+1) + (1+1+2) + (1+1+2+4) + ..... = 1 + 2^1 + 2^2 + ..... + 2^n = 2^{n+1} -1$.