There are $2^{63}$ different outcomes of a $64$ team single-elimination tournament such as the NCAA basketball ...

Question

There are $2^{63}$ different outcomes of a $64$ team single-elimination tournament such as the NCAA basketball tournament. Prove that a single-elimination tournament with $2^n$ teams has $2^{2^n-1}$ different outcomes. Hint: Use induction. Basis step: When n = 1, 2 n = 21 = 2 teams. 2^(2^1-1) = 21 = 2 outcomes. Therefore, P(1) is true. Induction Hypothesis: Suppose P(K) is true for some positive integer K. Then a tournament with 2k teams has 2^(2^k-1) different outcomes. We want to show P(K+1) is also true. This is all I have right now.

Answer 1

Hint: think of the rounds of the tournament. After you play the first round, you have a tournament with one fewer round. How many results are there in the first round?

Aside: Induction is the wrong tool here. As one team is eliminated each game, a tournament with $2^n$ teams must have $2^n-1$ games. Each game has two results, so there are $2^{2^n-1}$ sets of results. This does not require the number of teams to be a power of $2$.