The title wouldn’t let me format correctly, so here’s a better formatting of the question: Show by induction that any solution to a recurrence of the form

T(n) ≤ 2T(n/3) + c log_{3}n

is O(n log_{3} n).

Hoping someone can help me with the correct solution. I attempted two ways to get the solution (but I think that they’re both incorrect):

## SOLUTION A, where log is log_{3}:

T(n) ≤ 2T(n/3) + c log(n)

≤ 2 * ( k(n/3)log(n/3) ) + c log(n)

= (2/3)kn(log(n)-1) + (c)log(n)

= (2/3)(kn)log(n) = (2/3)kn + (c)log(n)

= ((2/3)kn + c)log(n) – (2/3)kn

## SOLUTION B, where log is log_{3}:

T(n) ≤ 2T(n/3) + c log(n)

≤ 2 * ( k(n/3)log(n/3) ) + c log(n)

= (kn – kn/3)(log(n) – 1) + (c)log(n)

= (kn)log(n) – (kn/3)log(n) – kn + (c)log(n)

= (kn)log(n) – (2/3)kn + (c – kn/3)log(n)