Thread: Induction question, help greatly appreciated :)

for a you have your base case(s) already since T(0) is of degree 0 and T(1) is of degree 1. Now you might as well use the strong principle, that is assume that the statement is true for all k between 2 and n. Then use the recurrence relation to show that it is true for T(n+1) and you are done. It is the same for b).