Using the master method in Section 4.5, you can show that the solution to the recurrence is . Show that a substitution proof with the assumption fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Let us assume for all , where and are positive constants.

We cannot proceed further with this.

Now, let us assume for all , where and are positive constants.

Hence, our assumption is correct.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.