# CSE 21Math for Algorithms

## Formulating Recurrences

(We focus on counting problems here.) To define a recurrence, you have to figure out how to illustrate a problem T(n) in terms of the same problem(s) for smaller inputs, e.g. T(n - 1), T(n - 2). There are a few ways to go about this.

1. Define T(n) = ... directly.

• Think about the "inductive case": what does the T(n) setting add to whatever you had before? Or: how do you get to T(n)? I often motivate my thinking by "building up" from the T(n - 1) scenario to the T(n) scenario, even if there's ultimately something else to do.
• Sometimes, there'll be multiple options (different blocks) or cases ("use" or "don't use" n), which'll require multiple recursive calls.
• If T(n) introduces elements to count which are independent of the ones that already exist (handshakes), add those elements directly.
• If T(n) introduces C elements for each of some set of elements that already exist (colored tiles), add C * the relevant recursive call.
• Just count all the elements that should be included in T(n), e.g. all valid length-n strings. Define a single term for each group of elements, making sure not to double-count, until you've exactly covered all the elements. Then sum up the terms. And you're done!

2. Work up from base cases.

• If you need somewhere to start, define base cases (presumably, you have to do this anyway). Write out the first X and try to figure out how the latest base case can be derived from the one(s) before it.

back