proof by induction: logarithms

Question

The Question: " An algorithm is known to have a complexity $T_{N}=O\left(\frac{N}{2}(\lg N)^2\right)$ with an additional correction proportional to $N \lg N$ where the lg designates the binary logarithm here.

(a) The recurrence relation is $T_{2N}= 2 ( T_{N} + N\lg N)$ and starts with $T_N=0$ for $N=2.$ Write down a table from which you derive a hypothesis for the exact $T_N.$

(b) Prove your hypothesis by induction."

i have this problem at my Algorithms exam, i tried it several hours but what i found for $T_N$ did not go along with the basic formula provided, what i got for $T_N$ is $T_{N}= N(\lg N)^2 + N\lg N$, these logarithms is base 2 of course.

i hope you can help me

Answer 1

Hint 1:

Since you can only calculate $T_N$ when $N$ is a power of $2$, define $$a_n = T_{2^n}$$Then your recursion becomes $a_{n+1} = 2(a_n +n2^n)$.

Hint 2:

Then consider defining $b_n = \dfrac{a_n}{2^n}$, so $a_n = 2^nb_n$.