Recurrence Relation

Fibonacci Sequence: $f_n = f_{n-1} + f_{n-2}$$(n \geq 2)$; $f_0 = 1$, $f_1 = 1$

The Tower of Hanoi: $H_n = 2H_{n-1} + 1$$(n \geq 2)$; $H_1 = 1$, $H_2 = 3$

DEFINITION: A linear recurrence relation of degree $k$ with constant coefficients is a recurrence relation of the form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} + F(n)$, where $n \geq k$, $\{c_i\}_{i=1}^k$ are constant real numbers, and $c_k \neq 0$.

• degree $k$: every term depends on $k$ terms preceding it
• constant coefficients: $c_1, \dots, c_k$ are independent of $n$
• linear: the right-hand side is a linear combination of $a_1, a_2, \dots, a_{n-1}$.
• linear homogeneous recurrence relation (LHRR): $F(n) = 0$
  // $f_n = f_{n-1} + f_{n-2}$
• linear nonhomogeneous recurrence relation (LNRR): $F(n) \neq 0$
  // $H_n = 2H_{n-1} + 1$
  • associated LHRR: $a_n = \sum_{i=1}^k c_i a_{n-i}$

Solving Recurrence Relation with GFs

GF-based Method: $F(n) = \left(f_l n^l + \dots + f_1 n + f_0\right)s^n = f(n)s^n$

EXAMPLE: Solve $a_n = 8a_{n-1} + 10^{n-1}$ with $a_0 = 1$ using generating function.

• $A(x)= \sum_{n=0}^\infty a_n x^n$
  $=1 + \sum_{n=1}^\infty (8a_{n-1} + 10^{n-1})x^n$
  $= 1 + 8xA(x) + \frac{x}{1-10x}$
• $A(x) = \frac{1-9x}{(1-8x)(1-10x)}$
  $= \frac{\alpha_{1,1}}{1-8x} + \frac{\alpha_{2,1}}{1-10x}$, $\alpha_{1,1}=\alpha_{2,1}=\frac{1}{2}$
• $A(x) = \frac{1}{2}\left(\frac{1}{1-8x} + \frac{1}{1-10x}\right)$
  $= \sum_{n=0}^\infty \frac{1}{2}(8^n + 10^n)x^n$
• $a_n = \frac{1}{2}(8^n + 10^n)$$(n \geq 0)$

THEOREM: Let $Q(x), P(x) \in \mathbb{R}[x]$ be polynomials with $\deg(Q) > \deg(P)$. If $Q(x) = (1 – r_1 x)^{m_1} \cdots (1 – r_t x)^{m_t}$ for distinct non-zero numbers $r_1,\dots,r_t$ and integers $m_1,\dots,m_t\geq 1$, then there exist unique coefficients $\{\alpha_{j,u}:\,j\in[t],\ u\in[m_j]\}$ s.t.

EXAMPLE: Solve $a_n = 4a_{n-1} – 4a_{n-2} + n^2$ with $a_0 = 2$, $a_1 = 5$.

• $A(x)= \sum_{n=0}^\infty a_n x^n$
  $= 2 + 5x + \sum_{n=2}^\infty (4a_{n-1} – 4a_{n-2} + n^2)x^n$
  $= 2 + 5x + 4x(A(x) – 2) – 4x^2 A(x) + \sum_{n=2}^\infty n^2 x^n$
• $y=\sum_{n=2}^\infty n^2 x^n = \frac{x^2+x}{(1-x)^3} – x$
  // $z=\sum_{n=0}^{\infty}x^n$; $y=x(xz’)’-x$
• $A(x) = \frac{1}{1-4x+4x^2}\left(2 – 4x + \frac{x^2+x}{(1-x)^3}\right)$
  $= \frac{2}{1-2x} + \boldsymbol{\frac{x^2+x}{(1-2x)^2(1-x)^3}}$
• $\boldsymbol{\frac{x^2+x}{(1-2x)^2(1-x)^3} = \frac{a}{1-2x} + \frac{b}{(1-2x)^2} + \frac{c}{1-x} + \frac{d}{(1-x)^2} + \frac{e}{(1-x)^3}}$
  // compare the numerators of both sides
  • $a=-26$, $b=6$, $c=13$, $d=5$, $d=5$
• $A(x) = \frac{2}{1-2x} + \boldsymbol{\frac{-26}{1-2x} + \frac{6}{(1-2x)^2} + \frac{13}{1-x} + \frac{5}{(1-x)^2} + \frac{2}{(1-x)^3}}$
• $a_n = n^2 + 8n + 20 + (6n – 18)2^n$
  // $(1+x)^u=\sum_{n=0}^{\infty}\binom{u}{n}x^n$

Principle of Inclusion-Exclusion

Two Sets

THEOREM: Let $S$ be a finite set. Let $A_1, A_2$ be subsets of $S$. Then

• $\boldsymbol{|S – A_1| = |S| – |A_1|}$
  $\boldsymbol{|A_1 – A_2| = |A_1| – |A_1 \cap A_2|}$
  • $S = A_1 \cup (S – A_1)$, $A_1 \cap (S – A_1) = \emptyset$;
    • $\{A_1, S – A_1\}$ is a partition of $S$
      • $|S| = |A_1| + |S – A_1|$
        • $|S – A_1| = |S| – |A_1|$
    • $A_1 – A_2 = A_1 – A_1 \cap A_2$
      • $|A_1 – A_2| = |A_1| – |A_1 \cap A_2|$
• $\boldsymbol{|A_1 \cup A_2| = |A_1| + |A_2| – |A_1 \cap A_2|}$
  • $A_1 \cup A_2 = (A_1 – A_2) \cup A_2$, $(A_1 – A_2) \cap A_2 = \emptyset$;
    • $\{A_1 – A_2, A_2\}$ is a partition of $A_1 \cup A_2$
      • $|A_1 \cup A_2| = |A_1 – A_2| + |A_2| = |A_1| – |A_1 \cap A_2| + |A_2|$
• $\boldsymbol{|A_1 \cap A_2| = |A_1| + |A_2| – |A_1 \cup A_2|}$

Three Sets

THEOREM: Let $S$ be a finite set. Let $A_1, A_2, A_3$ be subsets of $S$. Then

• $\left|\bigcup_{i=1}^3 A_i\right| = |(A_1 \cup A_2) \cup A_3| = |A_1 \cup A_2| + |A_3| – |(A_1 \cup A_2) \cap A_3|$
  • $|A_1 \cup A_2| = |A_1| + |A_2| – |A_1 \cap A_2|$
  • $|(A_1 \cup A_2) \cap A_3| = |(A_1 \cap A_3) \cup (A_2 \cap A_3)|$
    $= |A_1 \cap A_3| + |A_2 \cap A_3| – |(A_1 \cap A_3) \cap (A_2 \cap A_3)|$
    $= |A_1 \cap A_3| + |A_2 \cap A_3| – |A_1 \cap A_2 \cap A_3|$
    • $\left|\bigcup_{i=1}^3 A_i\right| = |A_1| + |A_2| – |A_1 \cap A_2| + |A_3| – (|A_1 \cap A_3| + |A_2 \cap A_3| – |A_1 \cap A_2 \cap A_3|)$
• $\left|\bigcap_{i=1}^3 A_i\right| = \sum_{t=1}^3 (-1)^{t-1} \sum_{1 \leq i_1 < \dots < i_t \leq 3} |A_{i_1} \cup \dots \cup A_{i_t}|$

$n$ Sets

THEOREM: Let $S$ be a finite set. Let $A_1, A_2, \dots, A_n \subseteq S$. Then

• $\left|\bigcup_{i=1}^n A_i\right| = \sum_{t=1}^n (-1)^{t-1} \sum_{1 \leq i_1 < \dots < i_t \leq n} |A_{i_1} \cap \dots \cap A_{i_t}|$;
• $\left|\bigcap_{i=1}^n A_i\right| = \sum_{t=1}^n (-1)^{t-1} \sum_{1 \leq i_1 < \dots < i_t \leq n} |A_{i_1} \cup \dots \cup A_{i_t}|$.

EXAMPLE: (Euler’s phi function) $\phi(n) = n\left(1 – \frac{1}{p_1}\right) \cdots \left(1 – \frac{1}{p_r}\right)$ for $n = p_1^{e_1} \cdots p_r^{e_r}$.

• $S = \{1,2, \dots, n\}$;
  $A_i = \{s \in S:\,p_i\mid s\}$, $i = 1,2, \dots, r$
  • $A = S – \bigcup_{i=1}^r A_i$
• $\left|\bigcup_{i=1}^r A_i\right| = \sum_{t=1}^r (-1)^{t-1} \sum_{1 \leq i_1 < \dots < i_t \leq n} |A_{i_1} \cap \dots \cap A_{i_t}|$
  • $|A_{i_1} \cap \dots \cap A_{i_t}| = \frac{n}{p_{i_1} \cdots p_{i_t}}$ for $t = 1,2, \dots, r$
• $|A| = |S| – \left|\bigcup_{i=1}^n A_i\right|$
  $= n – \left(\frac{n}{p_1} + \dots + \frac{n}{p_r} – \frac{n}{p_1p_2} – \dots – \frac{n}{p_{r-1}p_r} + \dots + (-1)^{r-1} \frac{n}{p_1 \cdots p_r}\right)$
  $= n – \left(\frac{n}{p_1} + \dots + \frac{n}{p_r}\right) + \left(\frac{n}{p_1p_2} + \dots + \frac{n}{p_{r-1}p_r}\right) – \dots + (-1)^r \frac{n}{p_1 \cdots p_r}$
  $= n\left(1 – \frac{1}{p_1}\right) \cdots \left(1 – \frac{1}{p_r}\right)$

Pigeonhole Principle

EXAMPLE: Connect 15 workstations $W_1, …, W_{15}$ to 10 servers $S_1, …, S_{10}$ such that any $\geq 10$ workstations have access to all servers. How many cables are needed?

• Solution 1: Connecting every workstation directly to every server. 150
• Solution 2: $S_i$ is connected to $W_i$ for every $i \in [10]$; and each of $W_{11}, W_{12}, W_{13}, W_{14}, W_{15}$ is connected to all servers.
  • This solution requires 60 lines.
  • Is this solution optimal?

Cover

DEFINITION: A cover of a finite set $A$ is a family $\{A_1, A_2, …, A_n\}$ of subsets of $A$ such that $\bigcup_{i=1}^n A_i = A$.

LEMMA: Let $\{A_1, A_2, …, A_n\}$ be a cover of a finite set $A$. Then $|A| \leq \sum_{i=1}^n |A_i|$.

• $n = 1$: $|A| = |A_1|$
• $n = 2$: $|A| = |A_1 \cup A_2| = |A_1| + |A_2| – |A_1 \cap A_2| \leq |A_1| + |A_2|$
• Suppose true when $n \leq k$ ($k \geq 2$).
• When $n = k + 1$,
  $|A| = \left|\bigcup_{i=1}^k A_i \cup A_{k+1}\right|$
  $\leq \left|\bigcup_{i=1}^k A_i\right| + |A_{k+1}|$
  $\leq \sum_{i=1}^k |A_i| + |A_{k+1}|$
  $= \sum_{i=1}^{k+1} |A_i|$

THEOREM: (simple form) Let $A$ be a set with $\geq n + 1$ elements. Let $\{A_1, A_2, \dots, A_n\}$ be a cover of $A$. Then $\exists k \in [n]$, $|A_k| \geq 2$.

• Suppose that $|A_i| \leq 1$ for every $i \in [n]$. Then $n + 1 \leq |A| \leq \sum_{i=1}^n |A_i| \leq n$.
  • If $\boldsymbol{\geq n + 1}$ objects are distributed into $\boldsymbol{n}$ boxes, then there is at least one box containing $\boldsymbol{\geq 2}$ objects.

THEOREM: (general form) Let $A$ be a set with $\geq N$ elements. Let $\{A_1, A_2, \dots, A_n\}$ be a cover of $A$. Then $\exists k \in [n]$, $|A_k| \geq \left\lceil \frac{N}{n} \right\rceil$.

• If $|A_i| < \left\lceil \frac{N}{n} \right\rceil$ for all $i \in [n]$, then $N \leq |A| \leq \sum_{i=1}^n |A_i| \boldsymbol{<} n \cdot \frac{N}{n} = N$
  • If we distribute $\boldsymbol{\geq N}$ objects into $\boldsymbol{n}$ boxes, then there is at least one box that contains $\boldsymbol{\geq \left\lceil \frac{N}{n} \right\rceil}$ objects.

EXAMPLE: Connect 15 workstations $W_1, \dots, W_{15}$ to 10 servers $S_1, \dots, S_{10}$ such that any $\geq 10$ workstations have access to all servers. How many cables are needed?

• Is Solution 2 optimal?
• Consider an optimal scheme $\boldsymbol{\Pi}$.
  • Let $A = \left\{\left(W_i, S_j\right):\,i \in [15], j \in [10], W_i\text{ is not connected to }S_j\right\}$ in $\Pi$
  • $A_t = \left\{\left(W_i, S_j\right) \in A:\,j = t\right\}$ for $t = 1,2, \dots, 10$
    • $\{A_1, A_2, \dots, A_{10}\}$ is a cover of $A$
• If there are $\boldsymbol{< 60}$ lines in $\boldsymbol{\Pi}$, then $|A| > 150 – 60 = 90$.
  • $|A| \geq 91$
  • $\exists k \in [10]$ such that $|A_k| \geq \left\lceil \frac{91}{10} \right\rceil = 10$
    • There are 10 workstations not connected to $S_k$