A tournament starts with n teams. In the first round, all teams are divided into pairs if n is even, and the winner in each pair passes to the next round assuming no ties. If n is odd, then one random team passes to the next round without playing. The second round proceeds similarly. At the end only one team is left - the winner. Find the total number of games played in tournament.
Assume n > 1. I tried for small n values. It looks like n-1 is the answer. Assuming it is true for every x < n . How could I go about the induction step. I am more interested in any alternate formal proof to the number of losing teams argument.
An inductive argument: Suppose the result holds for $x<n$. If $n$ is even, compare with the situation for $x=n-1$. There is one extra game in the first round, but all later rounds have the same number of games as in the $x=n-1$ case. Thus the total number of games is $(n-2) + 1 = n-1$. If $n=2k+1$ is odd, there are $k$ games played in the first round and the second round starts with $k+1$ players. By the induction hypothesis for $x=k+1<2k+1=n$, this takes $(k+1)-1=k$ games. So in total there are $2k = n-1$ games.