In a standard elimination tournament, a player wins $\$100k$ when he/she wins a match in the $k$th round (e.g. first round win earns \$100, second round win earns $\$200$, etc.). 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.
So, my thinking was you'd be adding the tournament money at the current node (which is the level times 100) + the cost of running the two tournaments under. Therefore, you'd have the recursion
$$a_n=2a_{n/2}+100\log_2(n)$$
Is this thinking correct? I'm having trouble finding a closed form solution to this recursion due to the log n term. I'd appreciate any help!
Your recursion is not correct. If there are $n$ players there are $\frac n2$ matches in the first round, so it should be $$a_n=2a_{\frac n2}+100\cdot \frac n2$$