Find and solve a recurrence relation for the number of matches played in a knockout tournament with $n$ teams, where $n$ is a power of $2$
I have already found a recurrence relation based on the two parts:
$1$. There are $\frac{n}{2}$ matches played in the first round.
$2$. The next round there are $a_{n/2}$ matches played in sub tournaments.
Thus, the recurrence relation for this problem is:$$a_n=a_{n/2}+\frac{n}{2}$$With a base case of $a_2=1$
However, I am now stuck on how exactly to solve this, since it is non-homogenous in nature due to the $\frac{n}{2}$. I know that in the end, it should end up being:$$a_n=n-1$$Since that, for example, it logically takes $63$ matches to determine a champion of $64$ teams. But I don't know how that solution is derived.
You can't get rid of homogeneity, but as I said, you need to reindex because you want the sequence to be well defined for the index not a power of two.
The relation you have obtained above, can now be stated more slickly: $a_0=1$ and $a_m=a_{m-1} + 2^{m-1}$.
This does not get rid of homogeneity: you can't get rid of that. But, you have another tool: you know the answer. The best thing you can do now, is proof by induction, but that's if you don't understand the proof I am giving below anyway.
This way is much easier.Watch this:
$a_m = a_{m-1} + 2^{m-1} = a_{m-2}+2^{m-2}+2^{m-1} = a_{0} + 2^{1} + 2^2 + ... + 2^{m-1}= 1 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1$.
I just telescoped the series, and obtained your result. It goes to show that even if the relation is non-homogeneous, it can still be solved in this manner.