A proof from the book

We shall prove the following identity:

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

with perhaps the most beautiful proof I have ever found.

Assume that we play a tournament with $2^k$ players, in which every game is a knock-out game between $2$ players. So in the first round there are $2^{k-1}$ games to be played, one for every $2$ people. Then in the second round only half of the players remains (i.e. $2^{k-1}$), so there are another $2^{k-2}$ games to be played, and so forth. Right up to the semi final and final, which are just $2^1$ and $2^0 = 1$ games, respectively. So the total amount of games played in the tournament is: $1 + 2 + 4 + 8 + .. + 2^{k-1}$. Another way to see how many games total there are played is the following: in every game, exactly $1$ player gets eliminated. There is only one winner, so the other $2^k - 1$ players must get elimated somewhere. So the total amount of games played must equal $2^k - 1$. Kablam.