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