# Mathematical Induction on sports

I have just started with mathematical induction please help me to understand in easy way : There are $n$ players in a match. How do I prove that total number of knockout matches will be $n-1$ to decide the winner.Or help me to understand following attachment.

• "knockout matches" implies to me an elimination tournament system. In which case the number of knockout matches will be $log_2(n)$ – Q the Platypus Apr 1 '16 at 3:33
• @QthePlatypus that is not true. in any tournament, if there is one winner, then $n-1$ players must be eliminated, and since no two players can be eliminated in the same match, there must be $n-1$ elimination matches – ASKASK Apr 1 '16 at 4:00

I have no idea how mathmatical induction comes into play here.

To answer your question though, if you consider $n$ player it will take $n-1$ matches for a tournament in elimnation style (only the winner keeps playing) because one person looses the tournament per match played.

If just one person wins you need the other $n-1$ to loose one match and therefore it takes $n-1$ matches to be played in total.

Maybe you could do it the following way:

$A(n)$: For a elimination tournament with $n$ players you need $n-1$ matches ; $n \in \mathbb{N}$ and $n \geq 2$

Induction Base: we show $A(2)$ which is trivial because 2 players need to play 1 match and therefore $A(2)$ holds.

Induction step: we consider $A(n)$ holds for one $n \in \mathbb{N}$. Now we look at the case $A(n+1)$ - The torunament follows the same rounds as in $A(n)$ - the new player will need to loose one match before he drops out, if he never does one of the other $n$ players will loose it - for both cases we need to have one more match. Therefore the ammount of matches is $(n-1)+1=n$

But this seems way too inconsistent for me - i am curious if there is a better way too show it through mathmatical induction although the idea above makes a alternate proof pretty short.

• Now I have added solution form book, help me to understand this. – mnulb Apr 1 '16 at 4:14