Solving the recurrence relation $T(n) = T(n/2) + 2\log_2n + 1; T(1) = 1$

Question

The hypothesis is given as $$T(n)=(\log_2n + 1)^2 $$

I've already proven the base case T(1) and now I'm stuck on the inductive step. I'm still wrapping my head around induction and I'm not entirely sure what my end goal is.

$$T(2n)=T(n) + 2\log_22n + 1\\=(\log_2n + 1)^2 + 2\log_22n + 1 $$

This is what I have for my inductive step, and then my algebra goes downhill.

EDIT: I should mention that the question specifically asks the RR be solved using induction.

Answer 1

Various hints:

• You have an error in $T(2n)=T(n) + 2\log_2n + 1$. You should be considering $$T(2n)=T(n) + 2\log_2(2n) + 1$$
• You may want to use $$\log_2(n) + 1 = \log_2(n) +\log_2(2) = \log_2(2n)$$
• You may want to factorise an expression which is quadratic in $\log_2(2n)$