I need to prove by induction the theorem that says we can construct a round robin tournament:
Given a tournament with $2^k$ teams. We label the teams $t_1, t_2, …, t_{2^k}$. It is possible to construct $2^k -1$ rounds of $2^{k-1}$ games where each team plays with each other team only once.
I have come up with the base case:
For $k=1$, we have 2 teams. There will be $2^1 – 1 = 1$ round, witg $2^{1-1} = 1$ game. This game is $\{t_1, t_2\}$.
However, I can't come up with the inductive step. I do know the algorithm, described here.
Best Answer
Now you assume you have a tournament schedule with $2^k$ teams with $2^k-1$ roundsand show how to make a tournament with $2^{k+1}$ teams in $2^{k+1}-1$ rounds. Take your $2^{k+1}$ teams, split them into two groups of $2^k$ and play the tournament that you know exists. Then play each team in one group against each team in the other group. You can just start with $j vs j+2^k$ and rotate the upper teams around the lower teams.