Consider a tennis tournament for n players, where n = 2k, k ∈ Z+. In the first round n/2 matches are played, and the n/2 winners advance to round 2, where n/4 matches are played. This halving process continues until a winner is determined.
(a) For n = 2k, k ∈ Z+, let f(n) count the total number of matches played in the tournament. Find and solve a recurrence relation for fin) of the form
F(1) = d
F(n) = af(n/2) + c, n = 2, 4, 8, ..., where a, c, and d are constants.
(b) Show that your answer in part (a) also solves the recurrence relation
f(1) = d
f(n) = f(n/2) + (n/2), n = 2, 4, 8, ... .