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