Inductin is fairly simple.
Prove that the statement $P(n)$ holds for all $n \geq c$, $c \in \mathbb{N}$

  • Best case: Prove $P(c)$
  • Induction Hypothesis: Assume $P(k)$ holds for some $k \geq c$, $k \in \mathbb{N}$
  • Induction Step: Prove $P(k)$ implies $P(k + 1)$

Examples

\[ \textrm{Prove that } S(n) = \sum_{i=0}^{n-1}{(2i + 1)} = n^2 \textrm{ for all } n \geq 1\\ \\ \textrm{Recursive definition:}\\ S(1) = \sum_{i=0}^{0}{(2i + 1)} = 2*0+1 = 1\\ \\ S(n + 1) = \sum_{i=0}^{n}{(2i + 1)} = \sum_{i=0}^{n-1}{(2i + 1)} + (2n + 1) = S(n) + 2n + 1 \\ \\ S(1) = 1\\ S(n + 1) = S(n) + 2n + 1\\ \\ \textrm{ Proof: }\\ \textrm{Base case: } S(1) = 1 = 1^2\\ \textrm{Induction Hypothesis: } S(k) = k^2\\ \\ \textrm{Induction Step:}\\ \begin{aligned} S(k + 1) &= S(k) + 2k + 1\\ &= k^2 + 2k + 1 \textrm{ (by IH) }\\ &= (k + 1)^2\\ \end{aligned} \]
\[ \textrm{Prove that } \sum^{n}_{i=0}{F(n)} = F(n + 2) - 1 \textrm{ for all } n \geq 0\\ \\ \textrm{Recursive Definition:}\\ \\ S(0) = F(0) = 0\\ S(n + 1) = S(n) + F(n + 1)\\ \\ \textrm{Proof:}\\ \textrm{Base case: } S(0) = F(2) - 1 = 1 - 1 = 0\\ \textrm{Induction Hypothesis: }\\ \\ \begin{aligned} S(k) &= F(k + 2) - 1\\ S(k + 1) &= S(k) + F(k + 1)\\ &= F(k + 2) - 1 + F(k + 1)\\ &= F(k + 1) + F(k + 2) - 1\\ &= F(k + 3) - 1 \textrm{ (By definition of F)} \end{aligned} \]
\[ \textrm{For every } n \in \mathbb{N}, n^3 - n \textrm{ is divisible by 3}\\ \textrm{Best case: } 0^3 - 0 = 0\\ \textrm{Induction Hypothesis: } k^3 - k = 3p, p \in \mathbb{N}\\ \textrm{Induction Step:}\\ \\ \begin{aligned} (k + 1)^3 - (k + 1) &= (k^3 + 3k^2 + 3k + 1) - (k + 1)\\ &= (k^3 - k) + 3k^2 + 3k + 1 - 1\\ &= 3p + 3(k^2 + k)\\ &= 3(p + k^2 + k)\\ \end{aligned} \]
\[ \textrm{For every } n \in \mathbb{N}, n \geq 10, n^3 \lt 2^n\\ \textrm{Best case: } 1000 \lt 1024\\ \textrm{Induction Hypothesis: }\\ k^2 \lt 2^k, \textrm{ for } k \geq 10\\ \\ \begin{aligned} (k + 1)^3 &= k^3 + 3k^2 + 3k + 1\\ k^3 + 3k^2 + 3k + 1 &\lt k^3 + 3k^2 + 3k * k + 1 * k^2\\ 3k + 1 &\lt 4k^2\\ k^3 + 7k^2 &\lt k^3 + k^3\\ k^3 + 7k^2 &\lt 2k^3\\ k^3 + 7k^2 &\lt 2k^3 \lt 2(2^k)\\ k^3 + 7k^2 &\lt 2(2^k)\\ k^3 + 7k^2 &\lt 2^{k+1}\\ \end{aligned} \]

Strong Induction

Prove that statement $P(n)$ holds for all $n \geq a$, $a \in \mathbb{N}$

  • Best cases: Prove $P(a), P(a + 1), P(a + 2), …, P(b)$
  • Induction Hypothesis: Assume that for some $k \in \mathbb{N}, P(a), P(a + 1), …, P(k)$ all hold
  • Induction Step: Prove that if IH is true, then $P(k + 1)$ is true

Examples

Given currency with only coins worth 3 or 5, show that we can pay any value larger or equal to 8.

Base cases:

  • $8 = 5 + 3$
  • $9 = 3 * 3$
  • $10 = 2 * 5$

Induction Hypothesis:

For $k \geq 10$, $k \in \mathbb{N}$, we can pay $i$ for every $i \in {8, 9, …, k}$

\[ \textrm{By IH, we can pay } k - 2\\ \textrm{Using the coin value 3 we pay } k + 1 \]