Calculating recurrences is a very common problem in CS. We have an entire toolset -- dynamic programming -- built around it. Yes, if you take the simplest recu

Calculating recurrences is a very common problem in CS. We have an entire toolset -- dynamic programming -- built around it. Yes, if you take the simplest recurrence and say "calculate it" it may sound artificial. But all the tools that can be used for this example -- direct formula, repeated squaring, dynamic programming -- can be used for more complicated recurrences also.