Recurrences formulas

Recurrence relations and generating functions. 12 formulas for GATE CS Discrete Mathematics, each with when to use it. Each is explained in the topic notes.

All 12 Recurrences formulas

CATALAN NUMBERS AND DERANGEMENTS

C_{n} = \frac{1}{n + 1} (n 2 n), D_{n} = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}

For $n \geq 0$ ; for example $C_{3} = \frac{1}{4} (3 6) = 5$ and $D_{4} = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 9$ .

CHARACTERISTIC EQUATION

r^{k} = c_{1} r^{k - 1} + c_{2} r^{k - 2} + \dots + c_{k}

For $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ ; it has degree $k$ , so $k$ roots over the complex numbers counted with multiplicity. Since $c_{k} \neq = 0$ , no root is 0.

GENERAL SOLUTION, DISTINCT ROOTS

a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n} + \dots + α_{k} r_{k}^{n}

When all $k$ roots $r_{i}$ are distinct (real or complex); the constants $α_{i}$ come from the $k$ initial conditions.

CONTRIBUTION OF A REPEATED ROOT

a_{n} = (α_{0} + α_{1} n + \dots + α_{m - 1} n^{m - 1}) r^{n}

A root $r$ of multiplicity $m$ contributes this term; add the contributions of all roots.

FIBONACCI AND LUCAS CLOSED FORMS

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}, L_{n} = φ^{n} + ψ^{n}, φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

Roots of $r^{2} = r + 1$ ; $F_{0} = 0, F_{1} = 1$ and $L_{0} = 2, L_{1} = 1$ .

FIRST-ORDER LINEAR RECURRENCE

a_{n} = c a_{n - 1} + d \Rightarrow a_{n} = c^{n} a_{0} + d \frac{c ^{n} - 1}{c - 1} (c \neq = 1), a_{n} = a_{0} + n d (c = 1)

For $n \geq 1$ with constants $c$ and $d$ . Example: $a_{n} = 2 a_{n - 1} + 1$ , $a_{0} = 0$ gives $2^{n} - 1$ .

GEOMETRIC SERIES

\frac{1}{1 - x} = n \geq 0 \sum x^{n}, \frac{1}{1 - a x} = n \geq 0 \sum a^{n} x^{n}

Coefficients $1, 1, 1, \dots$ and $1, a, a^{2}, \dots$ ; so $1/ (1 + x)$ gives $(- 1)^{n}$ .

LINEAR SEQUENCES

\frac{1}{( 1 - x ) ^{2}} = n \geq 0 \sum (n + 1) x^{n}, \frac{x}{( 1 - x ) ^{2}} = n \geq 0 \sum n x^{n}

Coefficients $1, 2, 3, \dots$ and $0, 1, 2, 3, \dots$ .

NEGATIVE BINOMIAL SERIES

\frac{1}{( 1 - x ) ^{k}} = n \geq 0 \sum (k - 1 n + k - 1) x^{n}, \frac{1}{( 1 - a x ) ^{k}} = n \geq 0 \sum (k - 1 n + k - 1) a^{n} x^{n}

For integer $k \geq 1$ ; $[x^{n}] (1 - x)^{- k}$ counts solutions of $y_{1} + \dots + y_{k} = n$ in non-negative integers.

FINITE SERIES

(1 + x)^{m} = k = 0 \sum m (k m) x^{k}, \frac{1 - x ^{m + 1}}{1 - x} = 1 + x + \dots + x^{m}

For integer $m \geq 0$ ; the second gives a bounded choice of $0$ to $m$ items.

FIBONACCI AND LUCAS GENERATING FUNCTIONS

n \geq 0 \sum F_{n} x^{n} = \frac{x}{1 - x - x ^{2}}, n \geq 0 \sum L_{n} x^{n} = \frac{2 - x}{1 - x - x ^{2}}

With $F_{0} = 0, F_{1} = 1$ and $L_{0} = 2, L_{1} = 1$ .

NON-NEGATIVE INTEGER SOLUTIONS

# {(y_{1}, \dots, y_{k}) : y_{1} + \dots + y_{k} = n, y_{i} \geq 0} = (k - 1 n + k - 1)

For $k \geq 1$ ; the coefficient of $x^{n}$ in $(1 - x)^{- k}$ , i.e. $n$ identical objects into $k$ distinct boxes. With every $y_{i} \geq 1$ the count is $(k - 1 n - 1)$ (for $n \geq k$ ; zero if $n < k$ ).

Where this was asked: 2018 (1), 2022 (1), 2023 (1). See the 3 previous-year questions on Recurrences. This shows what was asked, not what will be asked.

KEEP GOING

Recurrences: the notes and 3 solved previous-year questions