The substitution method for solving recurrences entails two steps:

  • Guess the form of the solution.
  • Use mathematical induction to find the constants and show that the solution works.