# A Recurrence Relation Problem

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 presume that$n$is a power of$2$, not$2n$, and edited the question suitably. – Srivatsan Nov 16 '11 at 17:16 ## 3 Answers 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$

-
But the amount awarded for winning a game depends on the round. – Gerry Myerson Nov 16 '11 at 5:41
+1 for the suggestion, but I think the problem is a little bit more complicated than that. – Patrick Da Silva Nov 16 '11 at 5:44
@GerryMyerson: I missed the $k$ in the problem. Fixed. – Ross Millikan Nov 16 '11 at 6:02
I find the notation very confusing (you talk of both $n$ as a power of $2$ and of $2^n$)... and the recurrence $D(n) = 2D(n/2) + 100n$ doesn't make sense; the last term should be $100r$ since it's the $r$th round. It should probably be $E(r) = 2E(r-1) + 100r$ and not what you have. – ShreevatsaR Nov 16 '11 at 6:33
@ShreevatsaR: I agree. See what you think now. – Ross Millikan Nov 16 '11 at 13:43

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).$$

-
$T(n+1)$ has two tournaments of size $2^n$ so there needs to be a coefficient of $2$ on the $T(n)$. Between us we'll get it right. – Ross Millikan Nov 16 '11 at 6:08
I think it's fine now. Uh yeah, forgot the two, that's a typo, thanks. – Patrick Da Silva Nov 16 '11 at 6:24