Find a closed-form solution for the following recurrence relation, and prove that it is correct:

where a and b are positive constants. Assume n is a power of 2.

A complete answer contains three parts, and all three are marked:

1. Working (2 marks) — unroll the recurrence level by level and show how the total is evaluated: how many levels there are, what each level contributes, and what the base cases contribute.
2. Verification by induction (2 marks) — check your formula at n = 1, then show that if it is correct for n/2, the recurrence makes it correct for n.
3. The closed form (2 marks) — stated on a single line at the bottom of your answer.

Type your answer as plain text: write powers as n^2, products as 4n or 4*n, and logarithms as log_x(n) for base x. You may draft on the paper provided, but only what you type into Moodle is marked.