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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: