video, solve by iterative substitution, finding pattern and extending to base case. Sometimes that gives the solution directy, other times the solutions give rise to Mathematical series. Sometimes this doesn't work .., but there are other methods, like conjecture a pattern and proving it by induction

They are often used in Analysis of algorithms

Solution methods

More solution methods to recurrence equations (and funny tie), List of methods:

• Repeated substitution (and use Mathematical series)
• Master theorem
• Change of variable: example
• Guess and Proof by induction, example
• Linear homogeneous, Linear recurrence equation
• Linear algebra, in particular Diagonalization

Examples: Josephus problem