How to Prove Recurrence Relations by Induction?

[needhelp83]

Prove the following recurrence by induction
T(n) = 2T(n/2) + n lg n = Θ ( n lg^2 n ), T(1) = 1

This to me looks scary and I was wondering if anybody had a heads up on how to solve for this

 

[CEL]

Suppose T(n) is true. From that supposition show that T(n+1) is true. That is the proof by induction.

 

[Fightfish]

Suppose T(n) is true. From that supposition show that T(n+1) is true. That is the proof by induction.

Not forgetting to prove T(1) to be true first as well.

 

[CEL]

Not forgetting to prove T(1) to be true first as well.

T(1) is assumed to be 1, by the hypothesis.