The Catalan numbers $C_n$ count many combinatorial objects, including:

• Ways to parenthesize a product of $n+1$ factors
• Binary trees with $n$ internal nodes
• Paths in a grid that don't cross the diagonal

They satisfy the recurrence: $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i} \text{ for } n \geq 1$ with $C_0 = 1$.

This is a non-linear recurrence. The closed form (derivable using generating functions) is: $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!}$

The first few values are: $1, 1, 2, 5, 14, 42, 132, 429, \ldots$

Many algorithms use divide-and-conquer, leading to recurrences of the form $T(n) = aT(n/b) + f(n)$.

Merge Sort: Divides array in half, recursively sorts each half, then merges. $T(n) = 2T(n/2) + \Theta(n)$ Solution: $T(n) = \Theta(n \log n)$

Binary Search: Divides search space in half at each step. $T(n) = T(n/2) + \Theta(1)$ Solution: $T(n) = \Theta(\log n)$

Karatsuba Multiplication: Multiplies two $n$-digit numbers. $T(n) = 3T(n/2) + \Theta(n)$ Solution: $T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$

How many $n$-bit binary strings contain no consecutive 1's?

Let $a_n$ be this count. Such a string either:

1. Ends in 0: the first $n-1$ bits form any valid $(n-1)$-bit string, giving $a_{n-1}$ strings
2. Ends in 01: the first $n-2$ bits form any valid $(n-2)$-bit string, giving $a_{n-2}$ strings

Therefore: $a_n = a_{n-1} + a_{n-2}$ with $a_1 = 2$ (0 and 1) and $a_2 = 3$ (00, 01, 10).

This is the Fibonacci recurrence with different initial conditions! The solution involves the same characteristic roots: $a_n = \frac{2+\phi}{\sqrt{5}} \phi^n + \frac{2-\phi}{\sqrt{5}} \hat{\phi}^n$

where $\phi = \frac{1+\sqrt{5}}{2}$ and $\hat{\phi} = \frac{1-\sqrt{5}}{2}$.

In the Josephus problem, $n$ people stand in a circle, and every second person is eliminated until one remains. If $J(n)$ is the position of the survivor, then: $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + 1$ with $J(1) = 1$.

For $n = 2^m + \ell$ where $0 \leq \ell < 2^m$, the solution is: $J(n) = 2\ell + 1$

This can be proven by induction using the recurrence.