Advanced Counting
Recurrence relations from algorithms, the Master Theorem for divide-and-conquer, generating functions, and how all three fit together.
Setting up a recurrence
A recurrence relation defines a sequence $\{a_n\}$ by expressing $a_n$ in terms of previous values together with one or more initial conditions. They arise naturally when counting things by induction or analyzing algorithms.
Example. Number of bit strings of length $n$ with no two consecutive 0s.
A valid string ends in either 1 or 0. If it ends in 1, the prefix is any valid string of length $n-1$. If it ends in 0, the previous bit must be 1, so the prefix is a valid string of length $n-2$ ending in 1 ā equivalently, any valid string of length $n-1$ ending in 1, which is the count for length $n-2$.
$a_n = a_{n-1} + a_{n-2}$, $a_1 = 2$, $a_2 = 3$. (Fibonacci-like.)
Example: Tower of Hanoi. Minimum number of moves $H_n$ to transfer $n$ disks.
Move top $n-1$ disks to spare ($H_{n-1}$ moves), move biggest disk (1 move), move $n-1$ back ($H_{n-1}$ moves): $$H_n = 2H_{n-1} + 1, \quad H_1 = 1.$$ Closed form: $H_n = 2^n - 1$.
5.1 Linear Recurrences with Constant Coefficients
Identifying the type
| Recurrence | Linear? | Homog? | Constant coeff? | Degree |
|---|---|---|---|---|
| $a_n = 3a_{n-1} + 4a_{n-2} + 5a_{n-3}$ | ā | ā | ā | 3 |
| $a_n = 2na_{n-1} + a_{n-2}$ | ā | ā | ā (depends on $n$) | ā |
| $a_n = a_{n-1}^2 + a_{n-2}$ | ā (squared) | ā | ā | ā |
| $a_n = a_{n-1} + 2$ | ā | ā (constant term) | ā | 1 |
| $a_n = a_{n-1} + n$ | ā | ā (term in $n$) | ā | 1 |
| $a_n = a_{n-2}$ | ā | ā | ā | 2 |
Solving linear homogeneous recurrences ā characteristic equation
Guess $a_n = r^n$. Substituting into $a_n - c_1 a_{n-1} - \cdots - c_k a_{n-k} = 0$ gives the characteristic equation: $$r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0.$$ Let $r_1, r_2, \ldots, r_k$ be its roots (with multiplicity).
Root $r$ of multiplicity $m$: contributes $(\alpha_0 + \alpha_1 n + \cdots + \alpha_{m-1} n^{m-1}) r^n$.
Example. Solve $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 1, a_1 = 0$.
Char eq: $r^2 - 5r + 6 = 0$, roots $r = 2, 3$.
General: $a_n = \alpha\cdot 2^n + \beta\cdot 3^n$.
Initial: $\alpha + \beta = 1$, $2\alpha + 3\beta = 0$. From the first, $\beta = 1 - \alpha$; substituting: $2\alpha + 3 - 3\alpha = 0$, so $\alpha = 3, \beta = -2$. Hence $a_n = 3\cdot 2^n - 2\cdot 3^n$.
Example (repeated root). $a_n = 4a_{n-1} - 4a_{n-2}$, $a_0 = 6, a_1 = 8$.
Char: $r^2 - 4r + 4 = (r-2)^2$. Double root $r = 2$. General: $a_n = (\alpha + \beta n) 2^n$.
$\alpha = 6$. $a_1 = (6 + \beta)\cdot 2 = 8 \Rightarrow \beta = -2$. So $a_n = (6 - 2n) 2^n$.
Example (complex/negative roots). $a_n = -4a_{n-1} - 4a_{n-2}$, $a_0=0, a_1=1$.
Char: $r^2 + 4r + 4 = (r+2)^2$. Double root $r = -2$. General: $a_n = (\alpha + \beta n)(-2)^n$. $\alpha = 0$, $\beta(-2) = 1$ so $\beta = -1/2$. Hence $a_n = -\tfrac{n}{2}(-2)^n = n\cdot(-2)^{n-1}\cdot(-1) \cdot \tfrac{1}{-1}$ ā simplify: $a_n = -\tfrac{n}{2}(-2)^n$.
Non-homogeneous: $a_n = $ (linear part) $+ F(n)$
If $a_n - c_1 a_{n-1} - \cdots - c_k a_{n-k} = F(n)$, the general solution is $$a_n = a_n^{(h)} + a_n^{(p)}$$ where $a_n^{(h)}$ is the general solution of the homogeneous equation and $a_n^{(p)}$ is any particular solution.
Guessing particular solutions
| $F(n)$ | Guess for $a_n^{(p)}$ |
|---|---|
| Polynomial of degree $d$ | Polynomial of degree $d$: $p_d n^d + \cdots + p_0$ |
| $\alpha\cdot s^n$ ($s$ not a root) | $q\cdot s^n$ |
| $\alpha\cdot s^n$ ($s$ a root of multiplicity $m$) | $q\cdot n^m s^n$ |
| Polynomial $\times s^n$ | Polynomial $\times s^n$ (same degree), times $n^m$ if $s$ is a root |
Example. $a_n = 2a_{n-1} + 3^n$ with $a_1 = 5$.
Homog: $r = 2$, so $a_n^{(h)} = \alpha 2^n$.
Particular: $F(n) = 3^n$, $s = 3$ is not a root, guess $q\cdot 3^n$. Substitute: $q\cdot 3^n = 2 q\cdot 3^{n-1} + 3^n$. Divide by $3^{n-1}$: $3q = 2q + 3$, so $q = 3$.
General: $a_n = \alpha 2^n + 3\cdot 3^n = \alpha 2^n + 3^{n+1}$. Init: $a_1 = 2\alpha + 9 = 5$, $\alpha = -2$.
$a_n = -2\cdot 2^n + 3^{n+1} = 3^{n+1} - 2^{n+1}$.
Iteration method for $a_n = a_{n-1} + n^2$, $a_0 = 0$: $$a_n = \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.$$
5.2 Recurrences from Divide-and-Conquer
D&C algorithms split a problem of size $n$ into $a$ subproblems of size $n/b$, do $f(n)$ extra work for splitting/combining. Cost recurrence: $$T(n) = a\cdot T(n/b) + f(n).$$
| Algorithm | $a$ | $b$ | $f(n)$ | Recurrence |
|---|---|---|---|---|
| Binary search | 1 | 2 | $1$ | $T(n) = T(n/2) + 1$ |
| Merge sort | 2 | 2 | $n$ | $T(n) = 2T(n/2) + n$ |
| Karatsuba mult. | 3 | 2 | $n$ | $T(n) = 3T(n/2) + n$ |
| Strassen mult. | 7 | 2 | $n^2$ | $T(n) = 7T(n/2) + n^2$ |
5.3 Master Theorem
- If $f(n) = O(n^{c^* - \epsilon})$ for some $\epsilon > 0$: $T(n) = \Theta(n^{c^*})$.
- If $f(n) = \Theta(n^{c^*})$: $T(n) = \Theta(n^{c^*} \log n)$.
- If $f(n) = \Omega(n^{c^* + \epsilon})$ for some $\epsilon > 0$ AND regularity ($af(n/b) \leq c f(n)$ for some $c < 1$): $T(n) = \Theta(f(n))$.
How to apply (the algorithm in your head)
- Identify $a, b, f(n)$.
- Compute $c^* = \log_b a$.
- Compare $f(n)$ to $n^{c^*}$.
- Apply the matching case.
Merge sort. $T(n) = 2T(n/2) + n$. $a=2, b=2, c^* = \log_2 2 = 1$. $f(n) = n = n^{c^*}$. Case 2. $T(n) = \Theta(n\log n)$.
Binary search. $T(n) = T(n/2) + 1$. $a=1, b=2, c^* = 0$. $f(n) = 1 = n^0 = n^{c^*}$. Case 2. $T(n) = \Theta(\log n)$.
Example. $T(n) = 8T(n/2) + n^2$. Then $c^* = \log_2 8 = 3$, $f(n) = n^2 = O(n^{3 - 0.5})$. Case 1. $T(n) = \Theta(n^3)$.
Example. $T(n) = 5T(n/2) + 3$. Then $c^* = \log_2 5 \approx 2.32$, $f(n) = 3 = O(n^{c^* - 0.5})$. Case 1. $T(n) = \Theta(n^{\log_2 5})$.
Iteration confirmation: $f(2^k) = 5^k\cdot 7 + 3(5^{k-1} + \cdots + 1) = O(5^k) = O(n^{\log_2 5})$.
Example (Case 3). $T(n) = 2T(n/2) + n^2$. Then $a=2, b=2$, $c^* = \log_2 2 = 1$, $f(n) = n^2 = \Omega(n^{c^* + 1})$. Regularity holds since $2\cdot(n/2)^2 = n^2/2 \leq \tfrac{1}{2}f(n)$. Case 3. $T(n) = \Theta(n^2)$.
Growth of functions (Big-O hierarchy)
$$1 \ll \log\log n \ll \log n \ll n^\epsilon \ll n \ll n\log n \ll n^c \ll c^n \ll n! \ll n^n.$$
- $f(n) = O(g)$ means $f \leq c\cdot g$ for $n$ large.
- $f(n) = \Omega(g)$ means $f \geq c\cdot g$ for $n$ large.
- $f(n) = \Theta(g)$ means both.
5.4 Generating Functions
Indispensable GFs to memorize
| Sequence | Generating function |
|---|---|
| $1, 1, 1, 1, \ldots$ | $\dfrac{1}{1-x}$ |
| $1, c, c^2, c^3, \ldots$ | $\dfrac{1}{1 - cx}$ |
| $1, -1, 1, -1, \ldots$ | $\dfrac{1}{1+x}$ |
| $0, 1, 1, 1, 1, \ldots$ | $\dfrac{x}{1-x}$ |
| $1, 0, 1, 0, 1, 0, \ldots$ | $\dfrac{1}{1-x^2}$ |
| $0, 1, 2, 3, 4, \ldots$ (i.e., $a_k = k$) | $\dfrac{x}{(1-x)^2}$ |
| $\binom{m}{0}, \binom{m}{1}, \ldots, \binom{m}{m}$ | $(1+x)^m$ |
| $1, 1, 1, \ldots$ (only up to $x^m$), then 0 | $\dfrac{1-x^{m+1}}{1-x}$ |
| $a_k = \binom{n+k-1}{k}$ (multisets) | $\dfrac{1}{(1-x)^n}$ |
GF transformation rules
If $G(x) \leftrightarrow \{a_k\}$, then:
- $cG(x) \leftrightarrow \{c\cdot a_k\}$ (scalar multiply).
- $xG(x) \leftrightarrow \{0, a_0, a_1, a_2, \ldots\}$ (shift right by 1).
- $\dfrac{G(x) - a_0 - a_1 x - \cdots - a_{m-1}x^{m-1}}{x^m} \leftrightarrow \{a_m, a_{m+1}, \ldots\}$ (shift left by $m$).
- $G(x) + H(x) \leftrightarrow \{a_k + b_k\}$.
- $G(x)H(x) \leftrightarrow \left\{\sum_{j=0}^k a_j b_{k-j}\right\}$ (convolution ā central to counting problems).
- $G'(x) \leftrightarrow \{(k+1)a_{k+1}\}$ ā i.e., shifts and weights by index.
5.5 Counting with Generating Functions
The standard recipe: build a GF for each "choice," multiply them; the coefficient of $x^n$ counts the number of ways to choose a total of $n$.
Example. How many ways to distribute 8 cookies to 3 children if each child gets $\geq 2$ and $\leq 4$?
Each child's contribution: $x^2 + x^3 + x^4$. Three children: $(x^2 + x^3 + x^4)^3$. We want the coefficient of $x^8$.
Factor: $(x^2(1 + x + x^2))^3 = x^6(1+x+x^2)^3$. Need coeff of $x^8$ in this, i.e., coeff of $x^2$ in $(1+x+x^2)^3$.
$(1+x+x^2)^2 = 1 + 2x + 3x^2 + 2x^3 + x^4$. Times $(1+x+x^2)$: take coefficient of $x^2$ products: $1\cdot 3 + 2\cdot 1 + 3\cdot 1 = ?$ Let me redo: we want coeff of $x^2$ in $(1 + 2x + 3x^2 + 2x^3 + x^4)(1 + x + x^2)$: $= 1\cdot x^2 + 2x\cdot x + 3x^2\cdot 1 = 1 + 2 + 3 = 6$.
Answer: $\boxed{6}$ ways.
Example. Number of nonnegative integer solutions to $e_1 + e_2 + e_3 = 17$ with $2 \leq e_1 \leq 5, 3 \leq e_2 \leq 6, 4 \leq e_3 \leq 7$.
Wait ā the original problem says $2 < e_1 < 5$ etc. (strict). So $e_1 \in \{3, 4\}$, $e_2 \in \{4, 5\}$, $e_3 \in \{5, 6\}$. Generating function: $$(x^3 + x^4)(x^4 + x^5)(x^5 + x^6)$$ Coefficient of $x^{17}$. Total min: $3+4+5 = 12$. Max: $4+5+6 = 15$. So $x^{17}$ has coefficient 0 ā no solutions. But sometimes problems use $\leq$; for safety, verify the original.
Example. Coins of denominations 1, 2, 5 to pay $$r$, order doesn't matter.
GF: $\dfrac{1}{(1-x)(1-x^2)(1-x^5)}$. Coefficient of $x^r$ = number of ways.
Example. 10 identical balloons to 4 children, each gets $\geq 2$.
Each child: $x^2 + x^3 + x^4 + \cdots = \dfrac{x^2}{1-x}$. Four children: $\dfrac{x^8}{(1-x)^4}$. Coeff of $x^{10}$ = coeff of $x^2$ in $(1-x)^{-4} = \sum_k \binom{k+3}{3}x^k$, which is $\binom{5}{3} = 10$.
Answer: $\boxed{10}$.
5.6 Solving Recurrences with Generating Functions
Strategy:
- Let $G(x) = \sum a_n x^n$.
- Multiply the recurrence by $x^n$ and sum over $n$.
- Express in terms of $G(x)$.
- Solve algebraically for $G(x)$.
- Extract coefficients (partial fractions or known series).
Example. $a_k = 3a_{k-1}, a_0 = 2$.
Multiply by $x^k$ and sum over $k \geq 1$: $$\sum_{k\geq 1} a_k x^k \;=\; 3x \sum_{k\geq 1} a_{k-1} x^{k-1}.$$ So $G(x) - 2 = 3x\cdot G(x)$, hence $G(x)(1 - 3x) = 2$, giving $$G(x) = \frac{2}{1 - 3x} = 2\sum_k (3x)^k,$$ so $a_k = 2\cdot 3^k$.
Example. $a_n = 8a_{n-1} + 10^{n-1}$, $a_1 = 9$ (codewords with even number of 0s).
Multiply by $x^n$ and sum over $n \geq 1$: $$\sum_{n\geq 1}a_n x^n \;=\; 8x\sum_{n\geq 1}a_{n-1}x^{n-1} \;+\; \sum_{n\geq 1} 10^{n-1}x^n.$$ Setting $a_0 = 1$ (convention for the empty string with 0 zeros, which is even), the LHS is $G(x) - 1$, the first RHS term is $8xG(x)$, and the second equals $$x\sum_{n\geq 0}(10x)^n = \frac{x}{1-10x}.$$
So $G(x)(1 - 8x) = 1 + \dfrac{x}{1-10x} = \dfrac{1 - 9x}{1-10x}$, hence $$G(x) = \frac{1 - 9x}{(1 - 8x)(1 - 10x)}.$$ Partial fractions: $\dfrac{A}{1-8x} + \dfrac{B}{1-10x}$. $1 - 9x = A(1-10x) + B(1-8x)$. Setting $x = 1/10$: $1 - 9/10 = B(1 - 4/5)$, so $1/10 = B/5$, $B = 1/2$. Setting $x = 1/8$: $1 - 9/8 = A(1 - 5/4) = -A/4$, so $-1/8 = -A/4$, $A = 1/2$.
$G(x) = \tfrac{1}{2}\cdot\tfrac{1}{1-8x} + \tfrac{1}{2}\cdot\tfrac{1}{1-10x}$. Hence $$a_n = \tfrac{1}{2}(8^n + 10^n).$$ Check $a_1 = (8 + 10)/2 = 9$ ā.
Interactive ā Master Theorem applicator
Enter $a$, $b$, and the polynomial exponent $c$ in $f(n) = \Theta(n^c)$. Get the case and the asymptotic instantly.
For $T(n) = a\,T(n/b) + f(n)$ where $f(n) = \Theta(n^c)$. Try the presets, then plug in your own recurrence.
Interactive ā Generating Function Solver
Select a generating function template, specify the parameters, and expand the power series dynamically to view the sequence coefficients.
Explore rational generating functions of the form $G(x) = \sum a_n x^n$. Select a template below:
Problem Bank ā Advanced Counting
Find a recurrence for $R_n$, the number of regions a plane is divided into by $n$ lines, no two parallel, no three concurrent.
Show solution
The $n$-th line crosses each of the previous $n-1$ lines once, gaining $n$ new regions: $$R_n = R_{n-1} + n, \quad R_0 = 1.$$ By iteration: $R_n = 1 + 1 + 2 + \cdots + n = 1 + \dfrac{n(n+1)}{2}$.
Recurrence for bit strings of length $n$ containing a pair of consecutive 0s.
Show solution
Let $a_n$ = number of such strings.
Consider what the string ends with.
Easier: count complements. Let $b_n$ = bit strings of length $n$ WITHOUT consecutive 0s. We showed $b_n = b_{n-1} + b_{n-2}$, $b_1 = 2, b_2 = 3$.
Then $a_n = 2^n - b_n$.
For a direct recurrence on $a_n$: $a_n = 2a_{n-1} + $ (strings of length $n$ ending in 00, no consecutive 0s in $A[1..n-2]$) $= 2a_{n-1} + 2^{n-2} - b_{n-2}$ ā getting messy. Easier to use the complement.
Salary starts at $\$50{,}000$; each year, salary doubles previous + extra $\$10{,}000n$ (for $n$-th year). Find a recurrence for $S_n$.
Show solution
$S_n = 2 S_{n-1} + 10{,}000\cdot n$, $S_1 = 50{,}000$.
Show $a_n = -2^{n+1}$ is a solution of $a_n = 3a_{n-1} + 2^n$.
Show solution
RHS: $3\cdot(-2^n) + 2^n = -3\cdot 2^n + 2^n = -2\cdot 2^n = -2^{n+1}$ = LHS. ā
Solve: (a) $a_n = 2a_{n-1}$, $a_0 = 3$. (b) $a_n = a_{n-1}$, $a_0=2$. (c) $a_n=4a_{n-2}$, $a_0=0, a_1=4$. (d) $a_n = a_{n-2}/4$, $a_0=1, a_1=0$.
Show solution
- (a) $a_n = 3\cdot 2^n$.
- (b) $a_n = 2$ (constant).
- (c) Char: $r^2 = 4$, $r = \pm 2$. $a_n = \alpha 2^n + \beta(-2)^n$. Init: $\alpha+\beta=0$ and $2\alpha - 2\beta = 4$, so $\alpha=1, \beta=-1$. $a_n = 2^n - (-2)^n$.
- (d) Char: $r^2 = 1/4$, $r = \pm 1/2$. $a_n = \alpha(1/2)^n + \beta(-1/2)^n$. Init: $\alpha+\beta=1$, $\alpha/2 - \beta/2 = 0 \Rightarrow \alpha = \beta = 1/2$. $a_n = \tfrac{1}{2}((1/2)^n + (-1/2)^n)$.
Which of these are linear homogeneous with constant coefficients? Give the degree:
(a) $a_n = 3a_{n-1} + 4a_{n-2} + 5a_{n-3}$
(b) $a_n = 2na_{n-1} + a_{n-2}$
(c) $a_n = a_{n-1} + a_{n-4}$
(d) $a_n = a_{n-1} + 2$
(e) $a_n = a_{n-1}^2 + a_{n-2}$
(f) $a_n = a_{n-2}$
(g) $a_n = a_{n-1} + n$
Show solution
(a) ā Linear homogeneous, degree 3.
(b) ā Coefficient $2n$ depends on $n$.
(c) ā Linear homogeneous, degree 4.
(d) ā Constant term ā not homogeneous.
(e) ā Nonlinear (squared).
(f) ā Linear homogeneous, degree 2.
(g) ā Term $n$ on RHS ā not homogeneous.
Solve $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0=1, a_1=0$.
Show solution
Char: $r^2 - 5r + 6 = 0 \Rightarrow r = 2, 3$. General: $a_n = A\cdot 2^n + B\cdot 3^n$.
Init: $A+B=1$, $2A+3B = 0$. Solve: $A = 3, B = -2$.
$\boxed{a_n = 3\cdot 2^n - 2\cdot 3^n}$.
Solve $a_n = 4a_{n-1} - 4a_{n-2}$, $a_0=6, a_1=8$.
Show solution
Char: $(r-2)^2 = 0$, repeated root 2. General: $a_n = (A + Bn)\cdot 2^n$.
$A = 6$. $a_1 = (6 + B)\cdot 2 = 8 \Rightarrow B = -2$. So $a_n = (6 - 2n)2^n = 2^{n+1}(3 - n)$.
Solve $a_n = -3a_{n-1} - 3a_{n-2} - a_{n-3}$, $a_0 = 5, a_1 = -9, a_2 = 15$.
Show solution
Char: $r^3 + 3r^2 + 3r + 1 = (r+1)^3 = 0$. Triple root $r=-1$.
General: $a_n = (A + Bn + Cn^2)(-1)^n$.
$a_0 = A = 5$. $a_1 = -(5 + B + C) = -9 \Rightarrow B + C = 4$. $a_2 = (5 + 2B + 4C) = 15 \Rightarrow 2B + 4C = 10 \Rightarrow B + 2C = 5$. Then $C = 1, B = 3$.
$a_n = (5 + 3n + n^2)(-1)^n$.
Find all solutions of $a_n = 2a_{n-1} + 3^n$. With $a_1 = 5$, give the explicit solution.
Show solution
Homog: $a_n^{(h)} = A\cdot 2^n$. Particular: try $C\cdot 3^n$ since $s=3$ isn't a root. Substituting: $C\cdot 3^n = 2C\cdot 3^{n-1} + 3^n$, divide by $3^{n-1}$: $3C = 2C + 3$, $C = 3$. Particular: $3^{n+1}$.
General: $a_n = A\cdot 2^n + 3^{n+1}$.
$a_1 = 2A + 9 = 5 \Rightarrow A = -2$. So $a_n = 3^{n+1} - 2^{n+1}$.
Solve $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$.
Show solution
Char roots: 2 and 3. Homog: $A\cdot 2^n + B\cdot 3^n$.
Particular: $2^n$ part ā $s = 2$ IS a root (mult 1), so try $qn\cdot 2^n$. Polynomial part: try $p_1 n + p_2$.
$2^n$ piece: $qn\cdot 2^n = 5q(n-1)2^{n-1} - 6q(n-2)2^{n-2} + 2^n$. Divide by $2^{n-2}$: $4qn = 10q(n-1) - 6q(n-2) + 4$. Simplify: $4qn = 10qn - 10q - 6qn + 12q + 4 = 4qn + 2q + 4$. So $0 = 2q + 4$, $q = -2$.
Polynomial: $p_1 n + p_2 = 5(p_1(n-1) + p_2) - 6(p_1(n-2) + p_2) + 3n$. RHS $= -p_1 n + (7p_1 - p_2) + 3n$. Matching: $p_1 = -p_1 + 3$ so $p_1 = 3/2$, and $p_2 = 7p_1 - p_2$ so $2p_2 = 7p_1 = 21/2$, $p_2 = 21/4$.
General: $a_n = A\cdot 2^n + B\cdot 3^n - 2n\cdot 2^n + \tfrac{3n}{2} + \tfrac{21}{4}$.
$f(n) = 5f(n/2) + 3$, $f(1) = 7$. Estimate.
Show solution
$a=5, b=2, c^* = \log_2 5 \approx 2.32$. $f(n) = 3 = O(1) = O(n^{c^* - 1})$. Case 1. $f(n) = \Theta(n^{\log_2 5})$.
$f(n) = 2f(n/3) + 4$, $f(1) = 1$, big-O?
Show solution
$a=2, b=3, c^* = \log_3 2 \approx 0.63$. $f = 4 = O(1) = O(n^{c^* - 0.5})$. Case 1. $f(n) = \Theta(n^{\log_3 2})$.
$f(n) = 8f(n/2) + n^2$, $f(1)=1$.
Show solution
$a=8, b=2, c^* = 3$. $f = n^2 = O(n^{3 - 0.5})$. Case 1. $f(n) = \Theta(n^3)$.
$f(n) = 2f(\sqrt n) + 1$, $f(2) = 1$, $n = 2^{2^k}$. Find $f(16)$ and a Big-O bound.
Show solution
Substitute $n = 2^k$, $g(k) = f(2^k)$, recurrence becomes $g(k) = 2g(k/2) + 1$.
Master Theorem on $g$: $a=2, b=2, c^*=1$, $f(k) = 1$. Case 1. $g(k) = \Theta(k)$. So $f(n) = \Theta(\log n)$.
$f(16) = f(2^4) = g(4)$. $g(4) = 2g(2) + 1 = 2(2g(1) + 1) + 1 = 4g(1) + 3$. $g(1) = f(2) = 1$, so $g(4) = 7$. Thus $f(16) = 7$.
$T(0)=1, T(1)=2, T(n)=5T(n-1)-6T(n-2)$. Which is true: (A) $\Theta(2^n)$, (B) $\Theta(n\cdot 2^n)$, (C) $\Theta(3^n)$, (D) $\Theta(n\cdot 3^n)$?
Show solution
Char: $r^2 - 5r + 6 = 0$, $r = 2, 3$. $T(n) = A\cdot 2^n + B\cdot 3^n$. As $n\to\infty$, the $3^n$ term dominates (unless $B = 0$). Solve init: $A + B = 1$, $2A + 3B = 2 \Rightarrow B = 0, A = 1$. So $T(n) = 2^n$. Answer (A). $T(n) = \Theta(2^n)$.
$T(1)=10$, $T(n+1) = 2n + T(n)$. Order?
Show solution
Iterating: $T(n) = 10 + 2(1) + 2(2) + \cdots + 2(n-1) = 10 + n(n-1)$. So $T(n) = \Theta(n^2)$. (C).
Find the closed-form GF for: (a) $0,2,2,2,2,2,0,0,\ldots$ (5 twos), (b) $0,0,0,1,1,1,\ldots$, (c) $0,1,0,0,1,0,0,1,\ldots$, (d) $2,4,8,16,\ldots$, (e) $\binom{7}{0}, \binom{7}{1}, \ldots, \binom{7}{7}, 0, 0, \ldots$, (f) $2,-2,2,-2,\ldots$, (g) $1,1,0,1,1,1,\ldots$, (h) $0,0,0,1,2,3,\ldots$.
Show solution
- (a) $2x \cdot \dfrac{1 - x^5}{1 - x} = \dfrac{2x(1-x^5)}{1-x}$.
- (b) $\dfrac{x^3}{1-x}$.
- (c) $\dfrac{x}{1-x^3}$.
- (d) $\dfrac{2}{1 - 2x}$.
- (e) $(1+x)^7$.
- (f) $\dfrac{2}{1+x}$.
- (g) $\dfrac{1}{1-x} - x^2$ (everything 1 minus the term at index 2).
- (h) $\dfrac{x^4}{(1-x)^2}$ (since $\sum_{k\geq 1}k\, x^k = \tfrac{x}{(1-x)^2}$; shift by 3).
Identify $a_k$ from these GFs: (a) $(3x-4)^3$, (b) $1/(1-5x)$, (c) $x^3/(1+3x)$, (d) $x^2/(1-x)^2$, (e) $2e^{2x}$.
Show solution
- (a) $(3x-4)^3 = \sum_k \binom{3}{k}(3x)^k(-4)^{3-k}$. So $a_k = \binom{3}{k}3^k(-4)^{3-k}$ for $k=0,1,2,3$, else 0.
- (b) $a_k = 5^k$.
- (c) $\dfrac{1}{1+3x} = \sum (-3)^k x^k$. Multiply by $x^3$: $a_k = (-3)^{k-3}$ for $k\geq 3$, else 0.
- (d) $\dfrac{1}{(1-x)^2} = \sum (k+1)x^k$. Multiply by $x^2$: $a_k = k - 1$ for $k \geq 2$ (so $a_2 = 1, a_3 = 2, \ldots$). For $k = 0, 1$: $a_k = 0$.
- (e) $2e^{2x} = 2\sum_k \frac{(2x)^k}{k!} = \sum_k \frac{2^{k+1}}{k!}x^k$. So $a_k = 2^{k+1}/k!$. (This is an EGF context.)
Eight identical cookies among three distinct children, each gets between 2 and 4.
Show solution
Per child GF: $x^2 + x^3 + x^4$. Total: $(x^2+x^3+x^4)^3 = x^6(1+x+x^2)^3$. Want coeff of $x^8$ = coeff of $x^2$ in $(1+x+x^2)^3$.
$(1+x+x^2)^3 = \sum_{i+j+k=2}\binom{3}{i,j,k}$ where indices give the powers. Compute: $1\cdot x^2\cdot 1\cdot 1$ + $x\cdot x\cdot 1$ + $x^2\cdot 1\cdot 1$ ways. By multinomial: count tuples with exponents summing to 2 from three slots each in $\{0,1,2\}$. Listings: $(0,0,2), (0,1,1), (0,2,0), (1,0,1), (1,1,0), (2,0,0)$: 6 ways. So coefficient = 6.
Answer: $\boxed{6}$.
10 identical balloons to 4 children, each child gets $\geq 2$.
Show solution
Per child: $x^2 + x^3 + \cdots = x^2/(1-x)$. Product: $x^8/(1-x)^4$. Want coeff of $x^{10}$, i.e., coeff of $x^2$ in $(1-x)^{-4}$.
$(1-x)^{-4} = \sum_k \binom{k+3}{3}x^k$, so coefficient of $x^2 = \binom{5}{3} = 10$.
$a_n = 8a_{n-1} + 10^{n-1}$, $a_1 = 9$. Solve via GF.
Show solution
Already solved in theory section: $a_n = \dfrac{1}{2}(8^n + 10^n)$. Verify $a_1 = (8+10)/2 = 9$ ā.
$a_k = \binom{m}{k}$ for $k = 0, 1, \ldots, m$. GF?
Show solution
By the binomial theorem, $\sum_{k=0}^m \binom{m}{k} x^k = (1+x)^m$.
Tokens of $\$1, \$2, \$5$ for an item costing $\$r$. (a) Order doesn't matter. (b) Order matters.
Show solution
(a) Order doesn't matter. GF $= \dfrac{1}{(1-x)(1-x^2)(1-x^5)}$. Coefficient of $x^r$.
(b) Order matters. This is an ordered composition. Each "step" is a token; the GF for a single step is $x + x^2 + x^5$. A sequence of any length: $\dfrac{1}{1 - (x+x^2+x^5)}$. Coefficient of $x^r$.
- Characteristic equation turns a degree-$k$ linear homogeneous recurrence into a polynomial equation. Repeated root $r$ of multiplicity $m$ contributes $(c_0 + c_1 n + \cdots + c_{m-1}n^{m-1})r^n$.
- Non-homogeneous: general = homog + particular. Guess the form of particular based on the RHS; multiply by $n^m$ if the guessed base is a root of multiplicity $m$.
- Master Theorem: compute $c^* = \log_b a$, compare to $f(n)$.
- GF dictionary: $1/(1-x), 1/(1-x)^2, 1/(1-x)^k, (1+x)^n$ are the four you must know.
- For counting with constraints, per-object GF $\to$ multiply $\to$ coefficient of $x^n$ = answer.
- For solving recurrences via GFs, multiply recurrence by $x^n$, sum, solve algebraically, partial-fraction.