<s>[INST] The sequence 1 + (1+1) + (1+1+2) + (1+1+2+4) + (1+1+2+4+8) + .. 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]$?
 [/INST] 
$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$.
</s>