Solving Recurrence Relations

This topic revisits Algebra techniques but applies them to combinatorial counts (tiling, string arrangements).

Linear Homogeneous

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2}

. Characteristic equation:

r^{2} - c_{1} r - c_{2} = 0

. Solution:

a_{n} = A r_{1}^{n} + B r_{2}^{n}

Recurrences like

T (n) = 2 T (n /2) + n

arise in algorithms (Merge Sort).

Using power series

A (x) = \sum a_{n} x^{n}

to solve recurrences.

a_{n + 1} = 2 a_{n} + 1 ⟹ \frac{A ( x ) - a _{0}}{x} = 2 A (x) + \frac{1}{1 - x}

Exercise (Problem 1)

Solve

a_{n} = 3 a_{n - 1} + 4 a_{n - 2}

with

a_{0} = 0, a_{1} = 5

Exercise (Problem 2)

Find the number of ways to tile a

2 \times n

rectangle with

1 \times 2

dominoes (Fibonacci).

Exercise (Problem 3)

Solve

a_{n} = a_{n - 1} + 2 n - 1

with

a_{0} = 0