# Suppose that there are n=2^k teams in an elimination tournament, where there are n/2 games in the first round, with the n/2=2^{k-1} winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.

Suppose that there are $n={2}^{k}$ teams in an elimination tournament, where there are n/2 games in the first round, with the $n/2={2}^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
Would $f\left(n\right)=f\left(n/2\right)+1$ for $n={2}^{k}$ be a recurrence relation for the question above? would I also have to say $f\left(1\right)=1?$?
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

grocbyntza
Step 1
For all recurrence relations, you will have to define the first term.
I'm not so sure about your notation with f(n)... perhaps you mean ${T}_{n}$ where n represents the nth power of 2 of the number of teams and ${T}_{n}$ is the number of rounds?
In which case, I think yes.
Step 2
So your recurrence relation would be:
${T}_{1}=0$
${T}_{n+1}={T}_{n}+1$
where:
${T}_{n}$ is the number of rounds in the tournament
${2}^{n}$ is the number of teams in the tournament.
###### Not exactly what you’re looking for?
Leila Jennings
Step 1
This is an old question, but I got a different answer so I thought I'd share it here for anyone in the future:
Each "level" of the tournament bracket has $n={2}^{k}$ teams. That means, for each level of the bracket, $\frac{n}{2}$ games are played (every two teams plays one game). So, the number of games played at a tournament is equal to the number of games played at the highest level ($\frac{n}{2}$), where there are n teams), plus the number of games played at a tournament one level smaller.
Step 2
Hence:
${T}_{1}=0$
${T}_{n}={T}_{n-1}+\frac{n}{2}$
Where ${T}_{n}$ is the number of games played in a tournament with $n={2}^{k}$ teams.