Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
In a standard elimination tournament, a player wins $\$100k$ when she/he wins a match in the $k$th round. Develop and solve a recurrence relation for $a_n$, the total amount of money given away in a tournament with $n$ entrants, where $n$ is assumed to be a power of $2$.
I seem always to fail build recurrence relations... I hope someone could explain it to me in details.
I assume you expect $n$ to be a power of $2$, not $2n$. Each tournament of $n$ is composed of two tournaments of $n/2$ plus one game worth $\$100\log_2(n)$. So if $D(n)$ is the distribution of a tournament of $n$ players, $D(n)=2D(n/2)+100\log_2(n)$. It would be easier to think in terms of $r=\log_2 n$, the number of rounds of the tournament. Using $E$ to avoid confusion, $E(r)=2E(r-1)+100\cdot r$
Here’s a more direct way to get the recurrence relation. Let $T(n)$ be the total given away when there are $2^n$ players. Suppose that we double the number of players, from $2^n$ to $2^{n+1}$. Let $P$ and $Q$ be the players who meet in the final round. Each of them is the winner of a tournament with $2^n$ players, namely, the sub-tournaments consisting of the two brackets of the whole tournament. These sub-tournaments started in round $1$, so each of them has paid out $T(n)$ dollars, for a total of $2T(n)$ dollars. All that remains is to figure out how much is paid to the winner of the final round. The first round eliminated half of the $2^{n+1}$ players, leaving $2^n$ still in the competition. The second round eliminated half of those, leaving $2^{n-1}$ still in the running. In general, each round eliminates half of the remaining contestants, so after $k$ rounds there must be $$\frac{2^{n+1}}{2^k}=2^{n+1-k}$$ contestants. In particular, after $n$ rounds there are $2^{n+1-n}=2$ contestants, so the last round is the $(n+1)$-st round and pays out $100(n+1)$ dollars. Thus, $$T(n+1)=2T(n)+100(n+1)\;.$$
While this is a more direct route to the recurrence, it isn’t necessarily an easier solution to find: playing with small cases leads pretty directly to Patrick’s more computational solution, which in turn also has the virtue of leading quite easily to a closed form for $T(n)$.
I think Ross's answer is the beginning of things but that he had it wrong. Let me explain.
You have $2^n$ players to begin with, hence $2^{n-1}$ matches for the first round. This gives us $2^{n-1}$ winners for the first round, hence $1 \times 100 \times 2^{n-1}$ dollars given away. Then $2^{n-1}$ players go to the second round, we have $2^{n-2}$ winners and they win $2 \times 100 \times 2^{n-2}$. We are left with $2^{n-2}$ players for the third round, $2^{n-3}$ winners, and they win $3 \times 100 \times 2^{n-3}$ dollars. It is easy to see that this keeps going on by induction on $k$, the round, and that the total amount of winnings at the $k^{\text{\th}}$ round will be $k \times 100 \times 2^{n-k}$ for $k = 1, \dots, n$. Thus $$ \text{Total}(n) = \sum_{k=1}^n \, (k \times 100 \times 2^{n-k}) = 2^n \times 100 \times \left( \sum_{k=1}^n \frac{k}{2^k} \right). $$ If you compute $\text{Total}(n+1)$ a little, you obtain $$ \begin{align} \text{Total}(n+1)= 2^{n+1} \times 100 \times \left( \sum_{k=1}^{n+1} \frac k{2^k} \right) \\ = 2^{n+1} \times 100 \times \left( \sum_{k=1}^{n} \frac k{2^k} + \frac{n+1}{2^{n+1}} \right) \\ = (n+1) \times 100 + 2 \times 2^n \times 100 \times \left( \sum_{k=1}^n \frac k{2^k} \right) \\ = (n+1) \times 100 + 2 \,\, \text{Total}(n) \\ \end{align} $$ Thus a recurrence formula for $T(n)$ would be $T(n+1) = (n+1)100 + 2T(n)$.
Hope that helps,
EDIT : You also have a more explicit formula for $T(n)$ by the following. Consider the geometric sum $$ \sum_{k=1}^n x^k = \frac{x^{n+1} - 1}{x-1}. $$ Thus $$ \begin{align} \sum_{k=1}^n kx^k &= x \left( \sum_{k=1}^n kx^{k-1} \right) \\ &= x \frac{d}{dx} \left( \sum_{k=1}^n x^k \right) \\ &= x \frac {d}{dx} \left( \frac{x^{n+1} - 1}{x-1} \right) \\ &= x \left( \frac{(n+1)x^n}{x-1} - \frac{x^{n+1} - 1}{(x-1)^2} \right) \\ &= \frac x{(x-1)^2} \left( (n+1)x^n(x-1) - x^{n+1} + 1 \right) \\ &= \frac x{(x-1)^2} \left( nx^{n+1} - (n+1) x^n + 1 \right). \end{align} $$ Let $x=1/2$ and you get $$ \sum_{k=1}^n \frac{k}{2^k} = 2 \left( \frac n{2^{n+1}} - \frac{(n+1)}{2^n} + 1 \right) = \frac{2^{n+1} - n -2}{2^n}. $$ This means that $$ T(n) = 2^n \times 100 \times \left( \frac{2^{n+1} - n - 2}{2^n} \right) = 100 (2^{n+1} - n - 2). $$
