We saw that the solution of is . Show that the solution of this recurrence is also . Conclude that the solution is .

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

The last step holds as long as . For example, , , and .

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