Discrete Mathematics : Sequences

Contents

• Sequences
• Ordinary Mathematical Induction
• Strong Mathematical Induction
• Recursion
• More Induction Problems

Sequences

Types of sequences

• Finite sequence: $a_m, a_{m + 1}, a_{m+2}, \ldots, a_n$
  e.g.: $1^1, 2^2, 3^2, \ldots, 100^2$
• Infinite sequence: $a_m, a_{m + 1}, a_{m+2}, \ldots$
  e.g.: $\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \ldots$

Recursive and non-recursive definitions

• Closed-form formula: $a_k = f(k)$
  e.g.: $a_k = \frac{k}{k + 1}$
• Recursive formula: $a_k = g(k, a_{k-1}, \ldots, a_{k - c})$
  e.g.: $a_k = a_{k-1} + (k-1) a_{k-2}$

Growth of sequences

• Increasing sequence
  e.g.: $2, 3, 5, 7, 11, 13, 17, \ldots$
• Decreasing sequence
  e.g.: $\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \ldots$
• Oscillating sequence
  e.g.: $1, -1, 1, -1, \ldots$

Term and sequence

• Compute $a_k$ given $a_1, a_2, a_3, \ldots$
  e.g.: Compute $a_k$ given $\frac{1}{n}, \frac{2}{n+1}, \frac{3}{n+2}, \ldots$
• Compute $a_1, a_2, a_3, \ldots$ given $a_k$
  e.g.: Compute $a_1, a_2, a_3, \ldots$ given $a_k = \frac{k}{k + 1}$

Sum and product definition

• Summation form:
\begin{align*} \sum_{k = m}^{n} a_k = a_{m} + a_{m + 1} + a_{m + 2} + \cdots + a_{n} \end{align*} where, $k = $ index, $m = $ lower limit, $n = $ upper limit
e.g.: $\sum_{k = m}^{n} \frac{(-1)^k}{k + 1}$
• Product form:
\begin{align*} \prod_{k = m}^{n} a_k = a_{m} \cdot a_{m + 1} \cdot a_{m + 2} \cdot \cdots \cdot a_{n} \end{align*} where, $k = $ index, $m = $ lower limit, $n = $ upper limit
e.g.: $\prod_{k = m}^{n} \frac{k}{k + 1}$

Sum and product properties

• Suppose $a_m, a_{m + 1}, a_{m + 2}, \ldots$ and $b_m, b_{m + 1}, b_{m + 2}, \ldots$ are sequences of real numbers and $c$ is any real number
• Sum properties
  • $\sum_{k = m}^{n} a_k = \sum_{k = m}^{i} a_k + \sum_{k = i + 1}^{n} a_k$ for $m \le i < n$
    where, $i$ is between $m$ and $n - 1$ (inclusive)
  • $c \cdot \sum_{k = m}^{n} a_k = \sum_{k = m}^{n} (c \cdot a_k)$
  • $\sum_{k = m}^{n} a_k + \sum_{k = m}^{n} b_k = \sum_{k = m}^{n} (a_k + b_k)$
• Product properties
  • $\left( \prod_{k = m}^{n} a_k \right) \cdot \left( \prod_{k = m}^{n} b_k \right) = \prod_{k = m}^{n} (a_k \cdot b_k)$

Factorial function

• The factorial of a whole number $n$, denoted by $n!$, is defined as follows: \begin{align*} n! &= \left. \begin{cases} 1 & \text{if } n = 0,\\ n \cdot (n - 1) \cdot \cdots \cdot 3 \cdot 2 \cdot 1 & \text{if } n > 0. \end{cases} \right\}\\ n! &= \left. \begin{cases} 1 & \text{if } n = 0,\\ n \cdot (n - 1)! & \text{if } n > 0. \end{cases} \right\} \end{align*}

Ordinary Mathematical Induction

• Mathematical induction is aesthetically beautiful and insanely powerful proof technique
• Mathematical induction is probably the greatest of all proof techniques and probably the simplest

Core idea

Template

Proof

• Basis step.
  Show that $P(a)$ is true.
• Induction step.
  Assume $P(k)$ is true for some integer $k \ge a$.
  (This supposition is called the inductive hypothesis.)
  Now, prove that $P(k + 1)$ is true.

Why does the template work?

Proof

• Basis step.
  $P(a)$
• Induction step.
  $\forall k \ge a, P(k) \rightarrow P(k+1)$.

Why does the proof work?

1. $P(a)$ (base case)
   $P(a) \rightarrow P(a + 1)$ (inductive hypothesis)
   $\therefore P(a + 1)$
2. $P(a + 1)$ (conclusion from argument 1)
   $P(a+1) \rightarrow P(a + 2)$ (inductive hypothesis)
   $\therefore P(a + 2)$
3. $P(a + 2)$ (conclusion from argument 2)
   $P(a+2) \rightarrow P(a + 3)$ (inductive hypothesis)
   $\therefore P(a + 3)$
4. so on... $P(a+4), P(a+5), \ldots$

$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

Pattern

• $1 = \frac{1 \cdot 2}{2}$
• $1 + 2 = \frac{2 \cdot 3}{2}$
• $1 + 2 + 3 = \frac{3 \cdot 4}{2}$
• $1 + 2 + 3 + 4 = \frac{4 \cdot 5}{2}$
• $1 + 2 + 3 + 4 + 5 = \frac{5 \cdot 6}{2}$
• $1 + 2 + 3 + 4 + 5 + 6 = \frac{6 \cdot 7}{2}$
• $1 + 2 + 3 + 4 + 5 + 6 + 7 = \frac{7 \cdot 8}{2}$
• $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = \frac{8 \cdot 9}{2}$
• $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = \frac{9 \cdot 10}{2}$
• $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = \frac{10 \cdot 11}{2}$
• $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 = \frac{11 \cdot 12}{2}$

Proof

Let $P(n)$ denote $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$.

• Basis step. $P(1)$ is true because $1 = 1(1+1)/2$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$.
  Now, we want to show that $P(k + 1)$ is true. That is,
  Assume $P(k)$: $1+2+\cdots+k = \frac{k(k+1)}{2}$ for some $k \ge 1$
  Prove $P(k+1)$: $1+2+\cdots+(k+1) = \frac{(k+1)(k+2)}{2}$ \begin{align*} & \text{LHS of } P(k+1) \\ &= (1 + 2 + \cdots + k) + (k + 1) \\ &= \frac{k(k + 1)}{2} + (k + 1) && (\because P(k) \text{ is true}) \\ &= \frac{(k+1)(k+2)}{2} && (\because \text{distributive law}) \\ &= \text{RHS of } P(k + 1) \end{align*}

$\left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \cdots \left( 1 - \frac{1}{n} \right) = \frac{1}{n}$

Proof

Let $P(n)$ denote $\left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \cdots \left( 1 - \frac{1}{n} \right) = \frac{1}{n}$.

• Basis step. $P(2)$ is true. (How?)
• Induction step.
  Assume $P(k)$: $\left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \cdots \left( 1 - \frac{1}{k} \right) = \frac{1}{k}$ for some $k \ge 2$.
  Prove $P(k+1)$: $\left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \cdots \left( 1 - \frac{1}{k+1} \right) = \frac{1}{k+1}$ \begin{align*} & \text{LHS of } P(k+1) \\ &= \left[ \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \cdots \left( 1 - \frac{1}{k} \right) \right] \left( 1 - \frac{1}{k + 1} \right) \\ &= \frac{1}{k} \left( 1 - \frac{1}{k + 1} \right) && (\because P(k) \text{ is true}) \\ &= \frac{1}{k} \cdot \frac{k}{k + 1} && (\because \text{common denominator}) \\ &= \frac{1}{k+1} && (\because \text{remove common factor}) \\ &= \text{RHS of } P(k+1) \end{align*}

$\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n \cdot (n+1)} = \frac{n}{n+1}$

Proof

Let $P(n)$ denote $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n \cdot (n+1)} = \frac{n}{n+1}$.

• Basis step. $P(1)$ is true. (How?)
• Induction step.
  Assume $P(k)$: $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{k \cdot (k+1)} = \frac{k}{k+1}$ for some $k \ge 1$
  Prove $P(k + 1)$: $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{(k+1) \cdot (k+2)} = \frac{k+1}{k+2}$ \begin{align*} & \text{LHS of } P(k+1) \\ &= \left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{k \cdot (k+1)} \right) + \frac{1}{(k+1) \cdot (k+2)} \\ &= \frac{k}{k + 1} + \frac{1}{(k+1) \cdot (k+2)} && (\because P(k) \text{ is true}) \\ &= \frac{k^2 + 2k + 1}{(k+1) \cdot (k+2)} && (\because \text{common denominator}) \\ &= \frac{(k+1)^2}{(k+1) \cdot (k+2)} && (\because \text{simplify}) \\ &= \frac{k+1}{k+2} && (\because \text{remove common factor}) \\ &= \text{RHS of } P(k+1) \end{align*}

Problems for practice

For all integers $n \ge 1$:

• $1 + 3 + \cdots + (2n-1) = n^2$
• $2 + 4 + \cdots + 2n = n(n+1)$
• $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$
• $1^3 + 2^3 + \cdots + n^3 = \left( \frac{n(n+1)}{2} \right)^2$
• $1 \cdot 2 + 2 \cdot 3 + \cdots + n (n + 1) = \frac{n(n+1)(n+2)}{3}$
• $2^2 + 5^2 + 8^2 + \cdots + (3n-1)^2 = \frac{n(6n^2 + 3n - 1)}{2}$
• $\sum_{i = 1}^{n} \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}$
• $\sum_{i = 1}^{n} i(i+1)(i+2) = \frac{n(n+1)(n+2)(n+3)}{4}$
• $\underbrace{111\ldots1}_{\text{$n$ times}} = \frac{10^n - 1}{9}$

$F(0)^2 + F(1)^2 + \cdots + F(n)^2 = F(n)F(n+1)$

Proof

Let $P(n)$ denote $F(0)^2 + F(1)^2 + \cdots + F(n)^2 = F(n)F(n+1)$.

• Basis step. $P(0)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 0$.
  Now, we want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= ( F(0)^2 + F(1)^2 + \cdots + F(k)^2 ) + F(k + 1)^2 \\ &= F(k) F(k + 1) + F(k + 1)^2 && (\because P(k) \text{ is true}) \\ &= F(k + 1) (F(k) + F(k + 1)) && (\because \text{distributive law}) \\ &= F(k + 1) F(k + 2) && (\because \text{recursive definition}) \\ &= \text{RHS of } P(k+1) \end{align*}

$1 + r + r^2 + \cdots + r^n = \frac{r^{n+1}-1}{r - 1}$

Proof

Let $P(n)$ denote $1 + r + r^2 + \cdots + r^n = \frac{r^{n+1}-1}{r - 1}$.

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$.
  Now, we want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= (1 + r + r^2 + \cdots + r^k) + r^{k + 1} \\ &= \left( \frac{r^{k+1}-1}{r - 1} \right) + r^{k + 1} && (\because P(k) \text{ is true}) \\ &= \frac{(r^{k+1}-1) + r^{k + 1} (r-1)}{r - 1} && (\because \text{common denominator}) \\ &= \frac{r^{(k+1)+1}-1}{r - 1} && (\because \text{simplify}) \\ &= \text{RHS of } P(k+1) \end{align*}

$2^{2n} - 1$ is divisible by $3$

Proof

Let $P(n)$ denote $2^{2n} - 1$ is divisible by $3$.

• Basis step. $P(0)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 0$.
  Now, we want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= 2^{2(k+1)} - 1 \\ &= 2^2 \cdot 2^{2k} - 1 && (\because a^{b+c} = a^b \cdot a^c) \\ &= (3 + 1) \cdot 2^{2k} - 1 && (\because \text{rewrite}) \\ &= 3 \cdot 2^{2k} + (2^{2k} - 1) && (\because \text{distributive law}) \\ &= 3 \cdot 2^{2k} + 3r && (\because P(k) \text{ is true}) \\ &= 3 \cdot (2^{2k} + r) && (\because \text{distributive law}) \\ &= 3 \cdot \text{integer} && (\because \text{addition is closed on integers}) \\ &= \text{RHS of } P(k+1) \end{align*}

Problems for practice

For all integers $n \ge 0$:

• $5^{n} - 1$ is divisible by 4
• $7^{n} - 1$ is divisible by 6
• $9^{n} + 3$ is divisible by 4
• $3^{2n} - 1$ is divisible by 8
• $7^{n} - 2^{n}$ is divisible by 5
• $7^{n+2} + 8^{2n+1}$ is divisible by 57
• $n^3 + 2n$ is divisible by 3
• $n^{3} - 7n + 3$ is divisible by 3
• $17n^3 + 103n$ is divisible by 6

$x^{n} - y^{n}$ is divisible by $x - y$

Proof

Let $P(n)$ denote $x^{n} - y^{n}$ is divisible by $x - y$, s.t. $x \ne y$.

• Basis step. $P(0)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 0$.
  Now, we want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= x^{k + 1} - y^{k + 1} \\ &= x^{k + 1} - x \cdot y^k + x \cdot y^k- y^{k + 1} && (\because \text{subtract and add}) \\ &= x \cdot (x^k - y^k) + y^k (x - y) && (\because \text{distributive law}) \\ &= x \cdot (x - y) r + y^k (x - y) && (\because P(k) \text{ is true}) \\ &= (x-y) (xr + y^k) && (\because \text{distributive law}) \\ &= (x-y) \cdot \text{integer} && (\because +,\times, \text{expo are closed on integers}) \\ &= \text{RHS of } P(k+1) \end{align*}

$2^{n} < n!$

Proof

Let $P(n)$ denote $2^{n} < n!$.

• Basis step. $P(4)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 4$.
  Now, we want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= 2^{k+1} \\ &= 2^k \cdot 2 && (\because a^{b+c} = a^b \cdot a^c) \\ &< k! \cdot 2 && (\because P(k) \text{ is true}) \\ &< k! \cdot (k +1) && (\because 2 < (k + 1) \text{ for } k \ge 4) \\ &= (k+1)! && (\because \text{factorial recursive definition}) \\ &= \text{RHS of } P(k+1) \end{align*}

$n^2 < 2^n$

Proof

Let $P(n)$ denote $n^2 < 2^n$.

• Basis step. $P(5)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 5$.
  Now, we want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= (k+1)^2 = k^2 + 2k + 1 && (\because \text{expand}) \\ &< k^2 + 2k + k && (\because 1 < k) \\=& \; k^2 + 3k && (\because \text{simplify}) \\ &< k^2 + k^2 && (\because 3 < k) \\=& \; 2k^2 && (\because \text{simplify}) \\ &< 2 \cdot 2^k && (\because P(k) \text{ is true}) \\=& \; 2^{k + 1} && (\because a^b \cdot a^c=a^{b + c}) \\=& \; \text{RHS of } P(k+1) \end{align*}

Tiling board with L-shaped trominoes

Example

• L-shaped tromino:
  
• L-shaped trominoes cover $2^3 \times 2^3$ board with a missing square:
  
  

Proof

Let $P(n)$ denote ''A $2^n \times 2^n$ board with a square removed can be completely covered by L-shaped trominoes.''

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$.
  Now, we want to show that $P(k + 1)$ is true.
Consider $2^{k+1} \times 2^{k+1}$ board with a square removed.
Divide it into four equal quadrants.
Consider the quadrant with the missing square. We can tile this quadrant with trominoes because $P(k)$ is true.
Remaining three quadrants meet at the center. Place a tromino on the three central squares of the three quadrants.
The three quadrants can now be tiled using trominoes because $P(k)$ is true. As all four quadrants can be covered with trominoes, $P(k + 1)$ is true.

Bogus proofs

Proof

Let $P(n)$ denote ''In any collection of $n$ dogs, all of them have the same color.''

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$.
  Now, we want to show that $P(k + 1)$ is true.
  Consider a set of $k + 1$ dogs, say, $\{ d_1, d_2, \ldots, d_k, d_{k+1} \}$.
  $\{ d_1, d_2, \ldots, d_k \}$ dogs have the same color. \hfill ($\because P(k)$ is true)
  $\{ d_2, d_3, \ldots, d_{k + 1} \}$ dogs have the same color. \hfill ($\because P(k)$ is true)
  So, all $k+1$ dogs have the same color.
  That is, $P(k + 1)$ is true.

• What's wrong?

Proof

Let $P(n)$ denote ''$n$ grains of sand is not a heap.''

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$.
  Now, we want to show that $P(k + 1)$ is true.
  If $n$ grains of sand is not a heap of sand, then $n + 1$ grains of sand is not a heap of sand either.
  Therefore, $P(k + 1)$ is true.

• What's wrong?

Proof

Let $P(n)$ denote ''$n$ atoms of matter is nonliving.''

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$.
  Now, we want to show that $P(k + 1)$ is true.
  Consider $n$ atoms of matter that is not living. Add one more atom to this collection. Adding one more atom cannot suddenly bring life to the nonliving. So, $n + 1$ atoms of matter is not living.
  Therefore, $P(k + 1)$ is true.

• What's wrong?

Strong Mathematical Induction

Equivalence

Why strong induction?

There are many propositions for which strong mathematical induction seems both simpler and more natural way of proving

Template

Proof

• Basis step.
  Show that $P(a), P(a+1), P(a + 2), \ldots, P(b)$ are true.
• Induction step.
  Assume $\{ P(a), P(a + 1), \ldots, P(k) \}$ are true for some $k \ge b$.
  (This supposition is called the inductive hypothesis.)
  Now, prove that $P(k + 1)$ is true.

$a_n = 5^n - 1$

Proof

Let $P(n)$ denote ''$a_n = 5^n - 1$.''

• Basis step. $P(0)$ and $P(1)$ are true. (How?)
• Induction step. Suppose that $P(i)$ is true for some $k \ge 1$ and any $i \in [0, k]$. We want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= a_{k + 1} \\ &= 6 a_{k} - 5 a_{k - 1} && (\because \text{recursive definition}) \\ &= 6 (5^k - 1) - 5 (5^{k - 1} - 1) && (\because P(k), P(k-1) \text{ are true}) \\ &= 5^{k + 1} - 1 && (\because \text{simplify}) \\ &= \text{RHS of } P(k+1) \end{align*}

Problems for practice

• Consider the sequence: $a_0 = 12$, $a_1 = 29$, and
  $a_k = 5 a_{k - 1} - 6 a_{k - 2}$ for all integers $k \ge 2$.
  Prove that $a_n = 5 \cdot 3^n + 7 \cdot 2^n$ for all integers $n \ge 0$.
• Consider the sequence: $a_1 = 3$, $a_2 = 5$, and
  $a_k = 3 a_{k - 1} - 2 a_{k - 2}$ for all integers $k \ge 3$.
  Prove that $a_n = 2^n + 1$ for all integers $n \ge 1$.
• Consider the sequence: $a_0 = 1$, $a_1 = 2$, $a_2 = 3$, and
  $a_k = a_{k - 1} + a_{k - 2} + a_{k - 3}$ for all integers $k \ge 3$.
  Prove that $a_n \le 3^n$ for all integers $n \ge 0$.
• Consider the sequence: $a_0 = 1$, $a_1 = 3$, and
  $a_k = 2 a_{k - 1} - a_{k - 2}$ for all integers $k \ge 2$.
  Prove that $a_n = 2n+1$ for all integers $n \ge 0$.
• Consider the sequence: $a_0 = 0$, $a_1 = 1$, and
  $a_k = 5 a_{k - 1} - 6 a_{k - 2}$ for all integers $k \ge 2$.
  Prove that $a_n = 3^n - 2^n$ for all integers $n \ge 0$.
• Consider the sequence: $a_1 = 1$, $a_2 = 8$, and
  $a_k = a_{k - 1} + 2 a_{k - 2}$ for all integers $k \ge 3$.
  Prove that $a_n = 3 \cdot 2^{n-1} + 2(-1)^n$ for all integers $n \ge 1$.

$n > 1$ is divisible by prime

Proof

Let $P(n)$ denote ''$n$ is divisible by a prime number.''

• Basis step. $P(2)$ is true. (How?)
• Induction step. Suppose that $P(i)$ is true for some $k \ge 2$ and any $i \in [2, k]$. We want to show that $P(k + 1)$ is true.
  Consider two cases:
  • Case 1: [$k + 1$ is prime.] $P(k + 1)$ is true. (How?)
  • Case 2: [$k + 1$ is not prime.] We can write $k + 1 = ab$ such that both $a,b \in [2, k]$ using the definition of a composite. This means, $k+1$ is divisible by $a$. We see that $a$ is divisible by a prime due to the inductive hypothesis. As $k + 1$ is divisible by $a$ and $a$ is divisible by a prime, $k + 1$ is divisible by a prime, due to the transitivity of divisibility. Hence, $P(k + 1)$ is true.

3-cent and 5-cent coins

Proof

Let $P(n)$ denote ''$n$ cents can be obtained using a combination of 3- and 5-cent coins.''

• Basis step. $P(8),P(9), P(10), P(11), P(12)$ are true. (How?)
• Induction step. Suppose that $P(i)$ is true for some $k \ge 12$ and any $i \in [8, k]$. We want to show that $P(k + 1)$ is true.
  $k + 1 = \underbrace{(k - 4)}_{\text{Part 1}} + \underbrace{5}_{\text{Part 2}}$
  Part 1 can be obtained by a collection of 3- and 5-cent coins because $P(k - 4)$ is true and $(k - 4) \ge 8$.
  Part 2 requires a 5-cent coin.
  Hence, $P(k + 1)$ is true.

Proof (improved)

Let $P(n)$ denote ''$n$ cents can be obtained using a combination of 3- and 5-cent coins.''

• Basis step. $P(8)$, $P(9)$, and $P(10)$ are true. (How?)
• Induction step. Suppose that $P(i)$ is true for some $k \ge 10$ and any $i \in [8, k]$. We want to show that $P(k + 1)$ is true.
  $k + 1 = \underbrace{(k - 2)}_{\text{Part 1}} + \underbrace{3}_{\text{Part 2}}$
  Part 1 can be obtained by a collection of 3- and 5-cent coins because $P(k - 2)$ is true and $(k - 2) \ge 8$.
  Part 2 requires a 3-cent coin.
  Hence, $P(k + 1)$ is true.

3-cent and 5-cent coins (Ordinary induction)

Proof (invalid)

Let $P(n)$ denote ''$n$ cents can be obtained using a combination of 3- and 5-cent coins.''

• Basis step. $P(8)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 8$. We want to show that $P(k + 1)$ is true.
$k + 1 = \underbrace{k}_{\text{Part 1}} + \underbrace{(3 + 3 - 5)}_{\text{Part 2}}$
Part 1: $P(k)$ is true as $k \ge 8$.
Part 2: Add two 3-cent coins and subtract one 5-cent coin.
Hence, $P(k + 1)$ is true.

Incorrect! What's wrong?

Proof (invalid)

Let $P(n)$ denote ''$n$ cents can be obtained using a combination of 3- and 5-cent coins.''

• Basis step. $P(8)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 8$. We want to show that $P(k + 1)$ is true.
  $k + 1 = \underbrace{k}_{\text{Part 1}} + \underbrace{(5 + 5 - 3 - 3 - 3)}_{\text{Part 2}}$
  Part 1: $P(k)$ is true as $k \ge 8$.
  Part 2: Add two 5-cent coins and subtract three 3-cent coins.
  Hence, $P(k + 1)$ is true.

Incorrect! What's wrong?

Proof

Let $P(n)$ denote ''$n$ cents can be obtained using a combination of 3- and 5-cent coins.''

• Basis step. $P(8)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 8$. We want to show that $P(k + 1)$ is true.
  Consider two cases:
  • [Case 1: There is a 5-cent coin in the set of $k$ cents.]
    $k + 1 = \underbrace{k}_{\text{Part 1}} + \underbrace{(3 + 3 - 5)}_{\text{Part 2}}$
    Part 1: $P(k)$ is true as $k \ge 8$.
    Part 2: Add two 3-cent coins and subtract one 5-cent coin.
  • [Case 2: There is no 5-cent coin in the set of $k$ cents.]
    $k + 1 = \underbrace{k}_{\text{Part 1}} + \underbrace{(5 + 5 - 3 - 3 - 3)}_{\text{Part 2}}$
    Part 1: $P(k)$ is true as $k \ge 8$.
    Part 2: Add two 5-cent coins and subtract three 3-cent coins.
  Hence, $P(k + 1)$ is true.

Problems for practice

• Any collection of $n$ people can be divided into teams of size
  • 5 and 6, for all integers $n \ge 35$
  • 4 and 7, for all integers $n \ge 18$
• Every amount of postage of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps.
• Fibonacci sequence is: $f_0 = 1$, $f_1 = 1$, and $f_n = f_{n - 1} + f_{n - 2}$ for $n \ge 2$. Prove that:
  • $f_n \le (7/4)^n$ for all $n \ge 0$.
  • $f_n \ge (3/2)^{n - 1}$ for all $n \ge 1$.
  • $f_n \ge 2^{(n - 1)/2}$ for all $n \ge 3$.
  • $f_n = (p^n - q^n) / \sqrt{5}$ for all $n \ge 1$,
    where $p = (1 + \sqrt{5}) / 2$ and $q = (1 - \sqrt{5}) / 2$.
    Hint: Note that $p$ and $q$ are the roots of $x^2 - x - 1 = 0$. So, $p^2 = p + 1$ and $q^2 = q + 1$.

Recursion

Some recursive functions

• Suppose $f(n) = n!$, where $n \in \mathbb{W}$. Then, \begin{align*} f(n) &= \begin{cases} 1 & \text{if } n = 0,\\ n \cdot f(n - 1) & \text{if } n \ge 1. \end{cases} \end{align*} Closed-form formula: $f(n) = n \cdot (n-1) \cdot \cdots \cdot 1$
• Suppose $F(n) = n$th Fibonacci number. Then, \begin{align*} F(n) &= \begin{cases} 1 & \text{if } n = 0 \text{ or } 1,\\ F(n - 1) + F(n - 2) & \text{if } n \ge 2. \end{cases} \end{align*} Closed-form formula: $F(n) =$ ?
• Suppose $C(n) = n$th Catalan number. Then, \begin{align*} C(n) &= \begin{cases} 1 & \text{if } n = 1,\\ \frac{4n-2}{n+1} \cdot C(n - 1) & \text{if } n \ge 2. \end{cases} \end{align*} Closed-form formula: $C(n) = \frac{1}{n + 1} \cdot \binom{2n}{n}$
• Suppose $M(m, n) = $ product of $m, n \in \mathbb{N}$. Then, \begin{align*} M(m, n) &= \begin{cases} m & \text{if } n = 1,\\ M(m, n - 1) + m & \text{if } n \ge 2. \end{cases} \end{align*} Closed-form formula: $M(m, n) = m \times n$
• Suppose $E(a, n) = a^n$, where $n \in \mathbb{W}$. Then, \begin{align*} E(a, n) &= \begin{cases} 1 & \text{if } n = 0,\\ E(a, n - 1) \times a & \text{if } n \ge 1. \end{cases} \end{align*} Closed-form formula: $E(a, n) = a^n$
• Suppose $O(n) = n$th odd number $\in \mathbb{N}$. Then, \begin{align*} O(n) &= \begin{cases} 1 & \text{if } n = 1,\\ O(n - 1) + 2 & \text{if } n \ge 2. \end{cases} \end{align*} Closed-form formula: $O(n) = 2n - 1$
• Recursive function for primes?

Relationship between induction and recursion

Recursion	Ordinary induction	Strong induction
Base case	Basis: $f(a)$	Basis: $f(a), f(a + 1), \ldots, f(b)$
Recursive case	Induction: Prove $f(n)$ from $f(n-1)$	Induction: Prove $f(n)$ from $f(n - 1), f(n - 2), \ldots, f(a)$

Arithmetic sequence

Definitions

• Arithmetic sequence:
  $\langle a_0, a_1, a_2, \ldots, a_n\rangle = \langle a, a + d, a + 2d, \ldots, a + nd \rangle$
• $n$th term
• Recursive definition:
  $a_n = a_{n - 1} + d$ for all integers $n \ge 1$
• Nonrecursive definition:
  $a_n = a + nd$ for all integers $n \ge 0$
• Summation
  $\sum_{i = 0}^{n} a_i = a_0 + a_1 + \cdots + a_n = (n + 1) a + d n (n + 1) / 2$

Example

Solution:

• Let $s_n = $ skydiver speed (m/sec) $n$ sec. after exiting the plane
• $s_n = s_0 + 9.8 n$ for each integer $n \ge 0$
• $s_{60} = 0 + (9.8)(60) = 588$ m/sec.

Geometric sequence

Definition

• Geometric sequence:
  $\langle a_0, a_1, a_2, \ldots, a_n\rangle = \langle a, a r, a r^2, \ldots, a r^n \rangle$
• $n$th term
  • Recursive definition:
    $a_n = r a_{n - 1}$ for all integers $n \ge 1$
  • Nonrecursive definition:
    $a_n = a r^n$ for all integers $n \ge 0$
• Summation
  $\sum_{i = 0}^{n} a_i = a_0 + a_1 + \cdots + a_n = a \left( \frac{r^{n + 1} - 1}{r - 1} \right)$

Example

Solution:

• Suppose $A_k = $ Amount in your account after $k$ years. Then, \begin{align*} A_k &= \begin{cases} 100,000 & \text{if } k = 0,\\ (1 + 3\%) \times A_{k - 1} & \text{if } k \ge 1. \end{cases} \end{align*}
• Solving the recurrence by the method of iteration, we get
  $\fbox{$A_{k} = ((1.03)^k \cdot 100,000)$ dollars}$ How?
• Homework: Prove the formula using induction
• When your kid hits 21 years, $k = 21$, therefore
  $A_{21} = ((1.03)^{21} \cdot 100,000) \approx 186,029.46$ dollars

Solution:

• Suppose $A_k = $ Amount in your account after $k$ quarters. Then, \begin{align*} A_k &= \begin{cases} 100,000 & \text{if } k = 0,\\ (1 + \frac{3}{4} \%) \times A_{k - 1} & \text{if } k \ge 1. \end{cases} \end{align*}
• Solving the recurrence by the method of iteration, we get
  $\fbox{$A_{k} = ((1.0075)^k \cdot 100,000)$ dollars}$
• Homework: Prove the formula using induction
• After 84 quarters or pay periods (21 years), $k = 84$,
  $A_{84} = ((1.0075)^{84} \cdot 100,000) \approx 187,320.2$ dollars

Towers of Hanoi

Workout

Suppose $k = 1$. Then, the 1-step solution is:

1. Move disk 1 from peg $A$ to peg $C$.

Source: http://mathforum.org/dr.math/faq/faq.tower.hanoi.html
Suppose $k = 2$. Then, the 3-step solution is:

1. Move disk 1 from peg $A$ to peg $B$.
2. Move disk 2 from peg $A$ to peg $C$.
3. Move disk 1 from peg $B$ to peg $C$.

Source: http://mathforum.org/dr.math/faq/faq.tower.hanoi.html
Suppose $k = 3$. Then, the 7-step solution is:

1. Move disk 1 from peg $A$ to peg $C$.
2. Move disk 2 from peg $A$ to peg $B$.
3. Move disk 1 from peg $C$ to peg $B$.
4. Move disk 3 from peg $A$ to peg $C$.
5. Move disk 1 from peg $B$ to peg $A$.
6. Move disk 2 from peg $B$ to peg $C$.
7. Move disk 1 from peg $A$ to peg $C$.

Suppose $k = 4$. Then, the 15-step solution is:

1. Move disk 1 from peg $A$ to peg $B$.
2. Move disk 2 from peg $A$ to peg $C$.
3. Move disk 1 from peg $B$ to peg $C$.
4. Move disk 3 from peg $A$ to peg $B$.
5. Move disk 1 from peg $C$ to peg $A$.
6. Move disk 2 from peg $C$ to peg $B$.
7. Move disk 1 from peg $A$ to peg $B$.
8. Move disk 4 from peg $A$ to peg $C$.
9. Move disk 1 from peg $B$ to peg $C$.
10. Move disk 2 from peg $B$ to peg $A$.
11. Move disk 1 from peg $C$ to peg $A$.
12. Move disk 3 from peg $B$ to peg $C$.
13. Move disk 1 from peg $A$ to peg $B$.
14. Move disk 2 from peg $A$ to peg $C$.
15. Move disk 1 from peg $B$ to peg $C$.

Solution

For any $k \ge 2$, the recursive solution is:

1. Transfer the top $k - 1$ disks from peg $A$ to peg $B$.
2. Move the bottom disk from peg $A$ to peg $C$.
3. Transfer the top $k - 1$ disks from peg $B$ to peg $C$.

Algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Towers-of-Hanoi}{$k, A, C, B$}
  \IF{$k = 1$}
    \STATE Move disk $k$ from $A$ to $C$
  \ELSIF{$k \ge 2$}
    \STATE \CALL{Towers-of-Hanoi}{$k - 1, A, B, C$}
    \STATE Move disk $k$ from $A$ to $C$
    \STATE \CALL{Towers-of-Hanoi}{$k - 1, B, C, A$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
  

• Let $M(k)$ denote the minimum number of moves required to move $k$ disks from one peg to another peg. Then \begin{align*} M(k) &= \left. \begin{cases} 1 & \text{if } k = 1,\\ 2 \cdot M(k - 1) + 1 & \text{if } k > 1. \end{cases} \right\} \end{align*}
• Solving the recurrence by the method of iteration, we get
  $\fbox{$M(k) = 2^k - 1$}$
• Homework: Prove the formula using induction

Greatest common divisor (GCD)

Definition

• The greatest common divisor (GCD) of two integers $a$ and $b$ is the largest integer that divides both $a$ and $b$.
• A simple way to compute GCD:
  1. Find the divisors of the two numbers
  2. Find the common divisors
  3. Find the greatest of the common divisors
• Examples:
  • $\text{GCD}(2, 100) = 2$
  • $\text{GCD}(3, 99) = 3$
  • $\text{GCD}(3, 4) = 1$
  • $\text{GCD}(12, 30) = 6$
  • $\text{GCD}(1071, 462) = 21$

Solution

• Recurrence relation: Suppose $a > b$. \begin{align*} \text{GCD}(a, b) &= \left. \begin{cases} a & \text{if } b = 0,\\ \text{GCD}(b, a \bmod b) & \text{if } b \ge 1. \end{cases} \right\} \end{align*}
• Example: \begin{align*} & \text{GCD}(1071, 462) \\ &= \text{GCD}(462, 1071 \bmod 462) \\ &= \text{GCD}(462, 147) && (\because 1071 = 2 \cdot 462 + 147) \\ &= \text{GCD}(147, 462 \bmod 147) \\ &= \text{GCD}(147, 21) && (\because 462 = 3 \cdot 147 + 21) \\ &= \text{GCD}(21, 147 \bmod 21) \\ &= \text{GCD}(21, 0) && (\because 147 = 7 \cdot 21 + 0) \\ &= 21 \end{align*}
• Intuition

Algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GCD}{$a, b$}
  \IF{$b = 0$} \RETURN $a$
  \ELSE \RETURN \CALL{GCD}{$b, a \bmod b$}
  \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
  

More Induction Problems

$1/1^2 + 1/2^2 + \cdots + 1/n^2$

Solution

It is difficult to solve the problem directly.
It is sometimes easier to prove a stronger result.
We prove the stronger statement that $\sum_{i=1}^n \frac{1}{i^2} < 2 - \frac{1}{n}$.
Let $P(n)$ denote $\sum_{i=1}^n \frac{1}{i^2} < 2 - \frac{1}{n}$ for $n \ge 2$.

• Basis step. $P(2)$ is true. (How?)
• Induction step. Suppose that $P(k)$ is true for some $k \ge 2$. We need to prove that $P(k + 1)$ is true.
\begin{align*} & \text{LHS of } P(k+1) \\ &= \left( \frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{k^2} \right) + \frac{1}{(k+1)^2} \\ &< \left( 2 - \frac{1}{k} \right) + \frac{1}{(k+1)^2} && (\because P(k) \text{ is true}) \\ &= 2 - \frac{(k+1)^2 - k}{k(k+1)^2} && (\because \text{taking common denominator}) \\ &= 2 - \frac{k(k+1) + 1}{k(k+1)^2} && (\because \text{simplify}) \\ &< 2 - \frac{k(k+1)}{k(k+1)^2} && (\because \text{decrease 1 in the numerator}) \\ &= 2 - \frac{1}{k+1} && (\because \text{canceling common factors}) \\ &= \text{RHS of } P(k+1) \end{align*}

$x^n + 1/x^n$

Solution

Let $P(n)$ denote $(x^n + 1/x^n) \in \mathbb{Z}$ for $n \ge 1$.

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(i)$ is true for all $i \in [1, k]$, where $k \ge 1$. We need to prove that $P(k + 1)$ is true.
  Observation: $\left( x^k + 1/x^k \right) \left( x + 1/x \right) = \left( x^{k+1} + 1/x^{k+1} \right) + \left( x^{k-1} + 1/x^{k-1} \right)$. So, we have \begin{align*} & \text{LHS of } P(k+1) \\ &= \left( x^{k+1} + 1/x^{k+1} \right) \\ &= \left( x^k + 1/x^k \right) \left( x + 1/x \right) - \left( x^{k-1} + 1/x^{k-1} \right) \\ &= \text{integer} \times \text{integer} - \text{integer} && (\because \text{inductive hypothesis}) \\ &= \text{RHS of } P(k+1) \end{align*}

Chocolate bar

Solution

Let $P(n)$ denote ''Breaking a chocolate bar with $n$ pieces into individual pieces requires $n - 1$ breaks''.

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(i)$ is true for all $i \in [1, k]$, where $k \ge 1$. We need to prove that $P(k + 1)$ is true.
Bar with $k + 1$ pieces is split into two parts using 1 break.
First part has $j$ pieces and second part has $k+1-j$ pieces. \begin{align*} & \text{#Breaks for chocolate bar with } k + 1 \text{ pieces} \\ &= 1 + \text{#Breaks for the first part } + \text{#Breaks for the second part} \\ &= 1 + (j - 1) + (k - j) && (\because P(j), P(k+1-j) \text{ are true}) \\ &= k \end{align*} Hence, $P(k + 1)$ is true.

McCarthy's 91 function

Solution

• Basis step. $M(n) = 91$ for $n \in [90, 100]$. (How?) \begin{align*} M(n) &= M(M(n + 11)) && (\because \text{By definition}) \\ &= M((n + 11) - 10) && (\because (n + 11) \ge 101) \\ &= M(n + 1) \end{align*} So, $M(n) = M(101) = 91$ for $n \in [90, 100]$.
• Induction step. Suppose that $M(i) = 91$ for some $k \le 90$ and any $i \in [k, 100]$. We want to show that $M(k - 1) = 91$. \begin{align*} M(k - 1) &= M(M(k - 1 + 11)) && (\because \text{By definition}) \\ &= M(M(k + 10)) && (\because \text{Simplify}) \\ &= M(91) && (\because \text{Inductive hypothesis, because } k < (k + 10) \le 100) \\ &=91 && (\because \text{Base case}) \end{align*}

Staircase problem

Solution

• Suppose $S_k = $ #ways of ascending a staircase with $k$ steps. Then, \begin{align*} S_k &= \begin{cases} \fbox{?} & \text{if } k \in [1, b],\\ \fbox{?} & \text{if } k \in [b + 1, n]. \end{cases} \end{align*}

Steps	Ways	#Ways
$1$	$1$	$1$
$2$	$1+1$, $2$	$2$
$3$	$1+1+1$, $1+2$, $2+1$, $3$	$4$
$4$	$1+1+1+1$, $1+1+2$, $1+2+1$, $2+1+1$, $2+2$, $1+3$, $3+1$, $4$	$8$

• Base case.
  Is $S_k = 2^{k-1}$? for $k \in [1, b]$. \begin{align*} S_k &= \begin{cases} 1 & \text{if } k = 1,\\ S_{k-1} + \cdots + S_1 + 1 & \text{if } k \in [2, b]. \end{cases} \end{align*} Solving the recurrence, we get $S_k = 2^{k-1}$ for $k \in [1, b]$.
• Recursion case.
  $S_k = S_{k - 1} + S_{k - 2} + \cdots + S_{k - b}$ for $k \in [b+1, n]$.

Continued fractions

Basics

• A continued fraction an expression of the form:
  $a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\cdots + \frac{1}{a_n}}}}$
• Formally, a continued fraction is:
  $(i)$ integer, or
  $(ii)$ integer + 1/(continued fraction)
• Example: Golden ratio $= \frac{1+\sqrt{5}}{2} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \cdots}}}$
• Given an integer $n$ and a natural number $d$,
  we can write $n = qd + r$ such that $r \in [0, d - 1]$.
• Observe that the rational number $n/d$ can be written as:
  $\frac{n}{d} = q + \frac{r}{d} = q + \frac{1}{\frac{d}{r}}$
• Every rational can be written with a positive denominator.

Proof

Let $P(d)$ denote ''Any rational with denominator $d$ has a continued fraction''.

• Basis step. $P(1)$ is true. (How?)
• Induction step. Suppose that $P(i)$ is true for all $i \in [1, d]$, for some $d \ge 1$. We need to prove that $P(d + 1)$ is true.
Consider the rational $\frac{n}{d+1}$ for some integer $n$.
Using the division theorem, we have $n = q (d+1) + r$,
where $r \in [0, d]$.
We consider two cases:
• [Case $r = 0$.] Then, $\frac{n}{d + 1} = q = $ integer.
  An integer is a continued fraction.
• [Case $r \ne 0$.] Then, $\frac{n}{d + 1} = q + \frac{r}{d+1} = q + \frac{1}{\frac{d+1}{r}}$.
  $\frac{d+1}{r}$ is a continued fraction due to inductive hypothesis because $P(r)$ is true. $\qquad (\because r \in [1, d])$
  Integer + 1/(continued fraction) is a continued fraction.
Hence, $P(d + 1)$ is true.