Use the 'rule of sum to prove that $\sum_{k=0}^n 2^k=2^{n+1}-1$.' I'm attempting a combinatorics problem that asks to use the 'rule of sum to prove that $\sum_{k=0}^n 2^k=2^{n+1}-1$.'  The rule of sum says that 'if $S=\cup_{i=1}^t S_i$ is a union of disjoint sets $S_i$, then $|S|=\sum_{i=1}^t |S_i|$.'  
I know that if we say $K=\{0,1,2,...,n\}$, then $2^k$ will give the number of ways to build any subset of the set $\{0,1,...,k-1\}\subset K$.  Also, $2^{n+1}-1$ is the number of subset in $K$ with cardinality greater than $2$.
I feel like this is the right path, but not entirely sure?  Any hints on how to proceed would be appreciated.
 A: The set $S$ is going to be the set of games in a round-robin tournament between $2^n$ players.
In total there are $2^{n}-1$ games since we eliminate one player per round and we need to eliminate $2^n-1$ players, all except the champion.
We let $S_1$ be the set of games in the first round, $S_2$ be the set of games in the second round and so on up to $S_{n}$.
In round $1$ we have $2^{n-1}$ games, in round $2$ we have $2^{n-2}$ games and so on up to round $n$ in which we have $2^{n-n}=1$ games.
Since $S_1,S_2\dots S_n$ are disjoint sets and their union is $S$ we conclude:
$$\sum_{i=1}^{n}2^i=\sum_{i=0}^{n-1}|S_i|=|S|=2^{n}-1$$
As was desired
.
A: Your approach has a drawback, since the $2^k$ subsets built from the set $\{0,\ldots,k-1\}$ are for different $k$ not necessarily different. Note that e.g. the subset containing zero only is a subset in all sets of the considered form.
\begin{align*}
\{0\}\subset\{0,\cdots,k-1\}\qquad 1\leq k \leq n+1\tag{1}
\end{align*}
Since the so generated subsets are not disjoint, we can't apply the rule of sum.

But, we can repair this deficiency. For each $k$ with $1\leq k \leq n+1$ we consider a string of length $k$ consisting of zeros only. 
For each set $\{0,\ldots,k-1\}$ with $1\leq k \leq n+1$ we associate a string $s_k:=0\ldots 0$ of length $k$ consisting of $k$ zeros on positions $0$ to $k-1$.
We consider according to your proposal all $2^k$ subsets built from $\{0,\ldots\,k-1\}$. To each of these $2^k$ subsets we create a string of length $k$ built from $s_k$ by setting  the position $j$ in $s_k$ to $1$ if and only if  $j$ is an element in the corresponding subset. Thus instead of considering the $2^k$ subsets we take the $2^k$ strings of length $k$.
This way it is guaranteed that for different $k$ the strings are different.

To illustrate the situation let's consider the case $n=2$ and the corresponding set $K=\{0,1,2\}$
\begin{array}{cllc}
k\quad&\text{subsets}&\text{strings}&\text{nr strings}\\
1\quad&\{\emptyset, \{0\}\}&S_1=\{0,1\}&2\\
2\quad&\{\emptyset,\{0\},\{1\},\{0,1\}\}&S_2=\{00,10,01,11\}&4\\
3\quad&\{\emptyset,&S_3=\{000,&8\\
&\ \{0\},\{1\},\{2\},&\qquad\quad100,010,001,\\
&\ \{0,1\},\{0,2\},\{1,2\},&\qquad\quad110,101,011,\\
&\ \{0,1,2\}\},&\qquad\quad111\}\\
\end{array}
We observe $S_i \cap S_j=\emptyset$ for $1\leq i<j\leq 3$ and therefore with $S=\bigcup_{k=1}^{3}S_k$ we derive
\begin{align*}
\sum_{k=1}^{3}|S_k|=\sum_{k=1}^{3}2^k=2^4-2
\end{align*}

In general
  \begin{align*}
\sum_{k=1}^{n+1}|S_k|=\sum_{k=1}^{n+1}2^k=2^{n+2}-2
\end{align*}
Since one subset corresponding to $k=0$ is missing, we also consider the empty set
  $$\emptyset\subset\{0,\ldots,n\}$$ and associate to it the empty string $\varepsilon$ having length zero.
\begin{array}{cccc}
k\quad&\text{subsets}&\text{strings}&\text{nr strings}\\
0\quad&\emptyset&S_0=\{\varepsilon\}&1\\
\end{array}
  to finally get $S=\bigcup_{k=0}^{n+1}S_k$ with
  \begin{align*}
\sum_{k=0}^{n+1}|S_k|=\sum_{k=0}^{n+1}2^k=2^{n+2}-1\tag{2}
\end{align*}

Note: Observe that there is another (small) deficiency in your approach, since we derive with (2) a formula with $n+1$ instead of $n$. The reason for this is the Ansatz with $K=\{0,\ldots,n\}$ which contains $n+1$ elements. If we use instead $K=\{1,\ldots,n\}$ with the same argumentation, we could derive the claimed expression with $n$ instead of $n+1$.
