A short discussion on methods for solving Recurrences

This topic is typically addressed during the courses of Discreet Mathematics or Mathematics for Computer Science. I've added here a very generical road map for solving recurrences.

First things first. You have a problem to be algorithmically solved. After writing your algorithm, you analyse its complexity. For divide and conquer, for example, we typically have recurrence functions - you express the runtime in terms of the runtime of the subproblems. For brute force, on the other hand, the running time is directly affected by the size search space or the number of all possible solutions.

For solving recurrences you can use one (or more than one) of the following approaches: substitution, iteration, iteration with visual trees and master method (this one for the order of growth only). Let's see an example and try to obtain the closed form of a recurrence:

A very strict proof would require an informed guess using Iteration, followed by the proof of the obtained closed form by induction. Now, just some terminology about this particular recurrence.

Solving the same recurrence but with visual trees. Drawing your way to the solution.

The master method will not give you the closed form but can help you to have a biased guess.

I will try to post some questions that you can use to prepare for the optional retake and the final. Stay tuned.