Intuition for Sum of Powers of Two

We want to reason about the following sum:

$$ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 $$

Normally, we know this via the partial sum of a geometric series formula,

\[S_n = \frac{lr - a}{r - 1}\]

Where $a$ is the first term, $l$ is the last term, and $r$ is the common ratio,

\[\frac{2^n \cdot 2 - 1}{2 - 1} = 2^{n+1} - 1\]

Intuition Using Binary Representation

$\sum_{i=0}^{n} 2^i$ can be thought of as the binary string of length $n+1$:

\[\texttt{a = } \underbrace{\texttt{111} \ldots \texttt{111}}_{n+1}\]

$2^{n+1}$ is the following binary string:

\[\texttt{b = } \underbrace{\texttt{100} \ldots \texttt{000}}_{n+2}\]

Since $\texttt{a = b - 1}$, we have $\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$.