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.