Mathematical Induction

---

Programming Environment

from   numba import njit
%load_ext Cython
import numpy as np
import cProfile
from   functools import lru_cache
import sys
sys.setrecursionlimit(1_000)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 1
----> 1 from   numba import njit
      2 get_ipython().run_line_magic('load_ext', 'Cython')
      3 import numpy as np

ModuleNotFoundError: No module named 'numba'

---

Induction Principle

Construction of the sort by which a process is repeatedly applied to a base case is called inductive.

Constructing \(\mathbb{P}\)

Let \(S\) be the successor function \(S(x) = x + 1\).

\[\begin{split} \begin{align*} 2 &= S(1) \\ 3 &= S(S(1)) \\ 4 &= S(S(S(1))) \\ 5 &= S(S(S(S(1)))) \\ \vdots \\ \end{align*} \end{split}\]

We construct a set of numbers with a certain property. If we let \(S\) stand for the set of numbers for which our theorem holds, in our proof by induction we show the following facts about \(S\):

1. The number \(1\) is in \(S\). This is proved explicitly in the base case of the proof.

2. If the number \(k\) is an element of \(S\), then the number \(k + 1\) is an element of \(S\). This is the content of the inductive step of the proof.

We know that the collection of natural numbers can be defined as the smallest set such that

1. The number \(1\) is a natural number.

2. If \(k\) is a natural number, then \(k + 1\) is a natural number.

So \(S\), the collection of numbers for which the theorem holds, is identical with the set of natural numbers, thus the theorem holds for every natural number \(n\), as needed.

The use of the induction principle can take complicated forms but, at base, is the fact that the positive integers are constructed by starting somewhere and then applying a rule again and again.

\(Induction \,\, Principle\)

Let \(P(n)\) be an assertion involving the positive integer variable \(n\).
If

1. \(P(1)\) holds and

2. whenever \(P(k)\) holds so also does \(P(k + 1)\)

then \(P(n)\) holds for every positive integer \(n\).

That is, if we can prove the base case at \(n = 1\) and if we have an argument that proves the \(k + 1\) case from the \(k\) case then we have the result for all positive integers.

In the inductive step, we prove the implication if the formula holds for \(k\), then the formula holds for \(k + 1\). We prove the implication by assuming the antecedent–that the theorem holds for a fixed but unknown number \(k\), and from that assumption proving the consequent, that the theorem holds for the next number \(k + 1\). This is not the same as assuming the theorem that we are trying to prove. The theorem is a universal statement–it claims that a certain formula holds for every natural number.

The typical structure of a proof by induction is as follows.

1. Base Case - show \(P(1)\).

2. Induction Step - assume that \(P(k)\) holds (this assumption is the induction hypothesis) and deduce that \(P(k + 1)\) follows.

Then the conclusion (by the induction principle) is that \(P(n)\) holds for all positive integers \(n\).

---

Examples

\(\forall n \in \mathbb{P} \,\,[ \,\,3 \mid a_n + 1\,\, ]\)

\(Claim\) [Humphreys & Prest pp. 16]

Let \(a\) be a sequence whose terms are defined inductively as follows.

\[\begin{split} a_n := \begin{cases} a_1 &= 2 \\ a_{n + 1} &= 2a_n + 1 \\ \end{cases} \end{split}\]

\[\begin{split} \begin{align*} a_1 &= 2 \\ a_2 &= 2a_1 + 1 = 5 \\ a_3 &= 2a_2 + 1 = 11 \\ a_4 &= 2a_3 + 1 = 23 \\ a_5 &= 2a_4 + 1 = 47 \\ \vdots \\ \end{align*} \end{split}\]

One greater than any term in \(a\) is divisible by \(3\).

\[ \forall n \in \mathbb{P} \,\, [ \,\, 3 \mid a_n + 1 \,\, ] \]

\(Proof \,\, by \,\, induction\)

Base Case

\(a_1 + 1 = 2 + 1 = 3\)
\(\therefore 3 \mid a_1 + 1\).

Induction Step

Induction Hypothesis: Let it be the case that \(3 \mid a_k + 1\) for some \(k \in \mathbb{P}\).
Then there is an integer \(m\) s.t. \(3m = a_k + 1 \iff 3m - 1 = a_k\).
\(a_{k + 1} + 1 = 2a_k + 2 = 2(3m - 1) + 2 = 6m - 2 + 2 = 3(2m)\).
\(\therefore 3 \mid a_{k + 1} + 1\).

\(\therefore 3 \mid a_n + 1\) for any \(n \in \mathbb{P}\).

\(\blacksquare\)

---

\(\forall n \in \mathbb{N} \,\,\left[ \,\,0 + 1 + 2 + \dots + n = \frac{n(n + 1)}{2}\,\, \right]\)

\(Claim\) [Humphreys & Prest pp. 17]

Let \(n\) be a natural number.
The sum \(0 + 1 + 2 + \dots + n\) of the first \(n\) natural numbers is \(\frac{n(n + 1)}{2}\).

\[ \forall n \in \mathbb{N} \,\, \left[ \,\, 0 + 1 + 2 + \dots + n = \frac{n(n + 1)}{2} = \frac{1}{2} n^2 + \frac{1}{2} n \,\, \right] \]

\(Proof \,\, by \,\, induction\)

Base Case

\(n = 0 \implies [0 = \frac{0(0 + 1)}{2} \iff 0 = 0]\)
\(n = 1 \implies [0 + 1 = \frac{1(1 + 1)}{2} \iff 1 = 1]\)

Induction Step

Induction Hypothesis: Let \(1 + 2 + \dots + k = \frac{k(k + 1)}{2}\) for some \(k \in \mathbb{N}\).

\[\begin{split} \begin{align*} & \textcolor{green}{1 + 2 + \dots + k + (k + 1)} \\ = & \frac{k(k + 1)}{2} + (k + 1) \\ = & \frac{k(k + 1) + 2(k + 1)}{2} \\ = & \textcolor{green}{\frac{(k + 1)((k + 1) + 1)}{2}} \\ = & \frac{(k + 1)(k + 2)}{2} \\ = & \frac{k^2 + 3k + 2}{2} \\ = & \frac{1}{2} k^2 + \frac{1}{2} 3k + \frac{1}{2} 2 \\ = & \frac{1}{2} k^2 + \frac{1}{2} 2k + \frac{1}{2} 1 + \frac{1}{2} k + \frac{1}{2} 1 \\ = & \frac{1}{2} ( k^2 + 2k + 1 ) + \frac{1}{2} ( k + 1 ) \\ = & \textcolor{green}{\frac{1}{2} ( k + 1 )^2 + \frac{1}{2} ( k + 1 )} \\ \end{align*} \end{split}\]

Therefore the sum \(0 + 1 + 2 + \dots + n\) of the first \(n\) natural numbers is \(\frac{n(n + 1)}{2}\) for any natural number \(n\).

\(\blacksquare\)

---

\(\forall n \in \mathbb{P} \,\,[ \,\,13 \mid a_n\,\, ]\)

\(Claim\) [Humphreys & Prest pp. 17-18]

Let \(a\) be a sequence whose terms are defined as follows.

\[ a_n := 4^{2n - 1} + 3^{n + 1} \]

Any term in \(a\) is divisible by \(13\).

\[ \forall n \in \mathbb{P} \,\, [ \,\, 13 \mid a_n \,\, ] \]

\(Proof \,\, by \,\, induction\)

Base Case

\(a_1 = 4^{2(1) - 1} + 3^{(1) + 1} = 4 + 3^2 = 13\)
\(\therefore 13 \mid a_1\).

Induction Step

Induction Hypothesis: Let \(13 \mid a_k = 4^{2k - 1} + 3^{k + 1}\) for some \(k \in \mathbb{P}\).
Then there is an integer \(m\) s.t. \(13m = 4^{2k - 1} + 3^{k + 1}\).
\(a_{k + 1} = 4^{2(k + 1) - 1} + 3^{(k + 1) + 1} = 4^{2k + 1} + 3^{k + 2}\)
\(= 4^2 \cdot 4^{2k - 1} + 3 \cdot 3^{k + 1}\)
\(= 16 \cdot 4^{2k - 1} (+ 16 \cdot 3^{k + 1} - 16 \cdot 3^{k + 1}) + 3 \cdot 3^{k + 1}\)
\(= 16 (4^{2k - 1} + 3^{k + 1}) - 16 \cdot 3^{k + 1} + 3 \cdot 3^{k + 1}\)
\(= 16 (13m) - 13 \cdot 3^{k + 1}\)
\(= 13 (16m - 3^{k + 1})\)
\(\therefore 13 \mid a_{k + 1}\).

\(\therefore 13 \mid a_n\) for any \(n \in \mathbb{P}\).

\(\blacksquare\)

---

Definition of the positive powers of an integer

\(Definition \,\, by \,\, induction\)

Base Case

Let \(a^1 := a\).

Induction Step

Let \(a^{k + 1} := a^k \cdot a\).

\[\begin{split} a^n := \begin{cases} a^1 &= a \\ a^{k + 1} &= a^k \cdot a \\ \end{cases} \end{split}\]

\[\begin{split} \begin{align*} a^1 &= a \\ a^2 &= a^1 \cdot a = a \cdot a \\ a^3 &= a^2 \cdot a = (a^1 \cdot a) \cdot a = (a \cdot a) \cdot a \\ a^4 &= a^3 \cdot a = (a^2 \cdot a) \cdot a = ((a^1 \cdot a) \cdot a) \cdot a = ((a \cdot a) \cdot a) \cdot a \\ a^5 &= a^4 \cdot a = (a^3 \cdot a) \cdot a = ((a^2 \cdot a) \cdot a) \cdot a = (((a^1 \cdot a) \cdot a) \cdot a) \cdot a = (((a \cdot a) \cdot a) \cdot a) \cdot a\\ \vdots \\ \end{align*} \end{split}\]

---

Definition of the factorial symbol

\(Definition \,\, by \,\, induction\)

Base Case

Let \(0! := 1\).

Induction Step

Let \((k + 1)! := (k + 1) \times k!\)

\[\begin{split} n! := \begin{cases} 0! &= 1 \\ (k + 1)! &= (k + 1) \times k! \\ \end{cases} \end{split}\]

\[\begin{split} \begin{align*} 0! &= 1 \\ 1! &= 1 \times 0! = 1 \times 1 = 1 \\ 2! &= 2 \times 1! = 2 \times (1 \times 0!) = 2 \times (1 \times 1) = 2 \\ 3! &= 3 \times 2! = 3 \times (2 \times 1!) = 3 \times (2 \times (1 \times 0!)) = 3 \times (2 \times (1 \times 1)) = 6 \\ 4! &= 4 \times 3! = 4 \times (3 \times (2 \times 1!)) = 4 \times (3 \times (2 \times (1 \times 0!))) = 4 \times (3 \times (2 \times (1 \times 1))) = 24 \\ \vdots \\ \end{align*} \end{split}\]

---

Binomial Theorem

Definition of binomial coefficients

Let \(n\) and \(k\) be integers with \(0 \le k \le n\).
The binomial coefficients are the numbers defined as follows.

\[\begin{split} \begin{align*} \binom{n}{k} &:= \frac{n!}{k!(n - k)!} = \frac{n(n - 1) \dots (n - k + 1)}{k!} \\ \end{align*} \end{split}\]

Note that

\[ \forall n \in \mathbb{N} \,\, \left[ \,\, \binom{n}{n} = \frac{n!}{n!(n - n)!} = 1 = \frac{n!}{0!(n - 0)!} = \binom{n}{0} \,\, \right] \]

Although it is clear from its definition that \(\binom{n}{k} \in \mathbb{Q}^+\) it is not yet clear that \(\binom{n}{k} \in \mathbb{Z}\).

Binomial Theorem

\(Theorem\)

Let \(n\) be a positive integer and let \(x, y\) be any numbers.
Then

\[\begin{split} \begin{align*} (x + y)^n &= \binom{n}{0} x^n + \dots + \binom{n}{i} x^{n - i} y^i + \dots + \binom{n}{n} y^n \\ &= \sum_{k = 0}^n \binom{n}{k} x^{n - k} y^k = \sum_{k = 0}^n \binom{n}{n - k} x^k y^{n - k}\\ \end{align*} \end{split}\]

\(Cases\)

\(n = 1\)

\[\begin{split} \begin{align*} (x + y)^1 &= \binom{1}{0} x^1 y^0 + \binom{1}{1} x^0 y^1 \\ &= \frac{1!}{0!(1 - 0)!} x + \frac{1!}{1!(1 - 1)!} y \\ &= \frac{1}{1 \cdot 1} x + \frac{1}{1 \cdot 1} y \\ &= x + y \\ \end{align*} \end{split}\]

\(n = 2\)

\[\begin{split} \begin{align*} (x + y)^2 &= \binom{2}{0} x^2 y^0 + \binom{2}{1} x^1 y^1 + \binom{2}{2} x^0 y^2 \\ &= \frac{2!}{0!(2 - 0)!} x^2 + \frac{2!}{1!(2 - 1)!} xy + \frac{2!}{2!(2 - 2)!} y^2 \\ &= \frac{2}{1 \cdot 2} x^2 + \frac{2}{1 \cdot 1} xy + \frac{2}{2 \cdot 1} y^2 \\ &= x^2 + 2xy + y^2 \\ \end{align*} \end{split}\]

\(n = 3\)

\[\begin{split} \begin{align*} (x + y)^3 &= \binom{3}{0} x^3 y^0 + \binom{3}{1} x^2 y^1 + \binom{3}{2} x^1 y^2 + \binom{3}{3} x^0 y^3 \\ &= \frac{3!}{0!(3 - 0)!} x^3 + \frac{3!}{1!(3 - 1)!} x^2y + \frac{3!}{2!(3 - 2)!} xy^2 + \frac{3!}{3!(3 - 3)!} y^3 \\ &= \frac{6}{1 \cdot 6} x^3 + \frac{6}{1 \cdot 2} x^2y + \frac{6}{2 \cdot 1} xy^2 + \frac{6}{6 \cdot 1} y^3 \\ &= x^3 + 3x^2y + 3xy^2 + y^3 \\ \end{align*} \end{split}\]

\(n = 4\)

\[\begin{split} \begin{align*} (x + y)^4 &= \binom{4}{0} x^4 y^0 + \binom{4}{1} x^3 y^1 + \binom{4}{2} x^2 y^2 + \binom{4}{3} x^1 y^3 + \binom{4}{4} x^0 y^4 \\ &= \frac{4!}{0!(4 - 0)!} x^4 + \frac{4!}{1!(4 - 1)!} x^3y + \frac{4!}{2!(4 - 2)!} x^2y^2 + \frac{4!}{3!(4 - 3)!} xy^3 + \frac{4!}{4!(4 - 4)!} y^4 \\ &= \frac{24}{1 \cdot 24} x^4 + \frac{24}{1 \cdot 6} x^3y + \frac{24}{2 \cdot 2} x^2y^2 + \frac{24}{6 \cdot 1} xy^3 + \frac{24}{24 \cdot 1} y^4 \\ &= x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4 \\ \end{align*} \end{split}\]

\(Proof \,\, by \,\, induction\)

Base Case

\((x + y)^1 = \binom{1}{0} x^1 y^0 + \binom{1}{1} x^0 y^1\)

Induction Step

Induction Hypothesis: Let \((x + y)^k = \binom{k}{0} x^k + \dots + \binom{k}{i} x^{k - i} y^i + \dots + \binom{k}{k} y^k\) for some \(k \in \mathbb{P}\).
\((x + y)^{k + 1} = (x + y)(x + y)^k\)
\(= (x + y)(\binom{k}{0} x^k + \dots + \binom{k}{i - 1} x^{k - (i - 1)} y^{i - 1} + \binom{k}{i} x^{k - i} y^i + \dots + \binom{k}{k} y^k)\)
\(= \textcolor{green}{\binom{k}{0} x^{k + 1}} + \binom{k}{0} x^k y + \dots + \binom{k}{i - 1} x^{k + 2 - i} y^{i - 1} + \textcolor{green}{\binom{k}{i - 1} x^{k + 1 - i} y^i} + \textcolor{green}{\binom{k}{i} x^{k + 1 - i} y^i} + \binom{k}{i} x^{k - i} y^{i + 1} + \dots + \binom{k}{k} x y^k + \textcolor{green}{\binom{k}{k} y^{k + 1}}\)
Note that \(\binom{k}{0} x^{k + 1} = x^{k + 1} = \binom{k + 1}{0} x^{k + 1}\).
Note that \(\binom{k}{k} y^{k + 1} = y^{k + 1} = \binom{k + 1}{k + 1} y^{k + 1}\).
Note that \(\binom{k}{i - 1} x^{k + 1 - i} y^i + \binom{k}{i} x^{k + 1 - i} y^i = \left( \binom{k}{i - 1} + \binom{k}{i} \right) x^{k + 1 - i} y^i\).
It is left for us to show that \(\binom{k}{i - 1} + \binom{k}{i} = \binom{k + 1}{i}\).

\[\begin{split} \begin{align*} & \binom{k}{i - 1} + \binom{k}{i} \\ = & \frac{k!}{(i - 1)!(k + 1 - i)!} + \frac{k!}{i!(k - i)!} \\ = & \frac{k!}{(i - 1)!(k + 1 - i)(k - i)!} + \frac{k!}{i(i - 1)!(k - i)!} \\ = & \frac{k!}{(i - 1)!(k - i)!} \left( \frac{1}{(k + 1 - i)} + \frac{1}{i} \right) \\ = & \frac{k!}{(i - 1)!(k - i)!} \cdot \frac{k + 1}{i(k + 1 - i)} \\ = & \frac{(k + 1) \cdot k!}{i \cdot (i - 1)! \cdot (k + 1 - i) \cdot (k - i)!} \\ = & \frac{(k + 1)!}{i!(k + 1 - i)!} \\ = & \binom{k + 1}{i} \\ \end{align*} \end{split}\]

\(\blacksquare\)

Constructing Pascal’s Triangle

\[\begin{split} \begin{array}{c|} k \\ \hline 0 && 1 \\ 1 && 1 && 1 \\ 2 && 1 && 2 && 1 \\ 3 && 1 && 3 && 3 && 1 \\ 4 && 1 && 4 && 6 && 4 && 1 \\ 5 && 1 && 5 && 10 && 10 && 5 && 1 \\ 6 && 1 && 6 && 15 && 20 && 15 && 6 && 1 \\ \vdots && \\ \hline i= && 0 && 1 && 2 && 3 && 4 && 5 && 6 && \dots \\ \end{array} \end{split}\]

\[ \binom{k}{i - 1} + \binom{k}{i} = \binom{k + 1}{i} \]

\[\begin{split} \begin{array}{c|} k \\ \hline 0 && \binom{0}{0} \\ 1 && \binom{1}{0} && \binom{1}{1} \\ 2 && \binom{2}{0} && \binom{2}{1} && \binom{2}{2} \\ 3 && \binom{3}{0} && \binom{3}{1} && \binom{3}{2} && \binom{3}{3} \\ 4 && \binom{4}{0} && \binom{4}{1} && \binom{4}{2} && \binom{4}{3} && \binom{4}{4} \\ 5 && \binom{5}{0} && \binom{5}{1} && \binom{5}{2} && \binom{5}{3} && \binom{5}{4} && \binom{5}{5} \\ 6 && \binom{6}{0} && \binom{6}{1} && \binom{6}{2} && \binom{6}{3} && \binom{6}{4} && \binom{6}{5} && \binom{6}{6} \\ \vdots && \\ \hline i= && 0 && 1 && 2 && 3 && 4 && 5 && 6 && \dots \\ \end{array} \end{split}\]

Binomial coefficients are positive integers

\(Claim\)

Let \(n\) and \(k\) be integers with \(0 \le k \le n\).
\(\binom{n}{k} \in \mathbb{Z}\).

\[ \forall n, k \in \mathbb{Z} \,\, \left[\,\, \binom{n}{k} \in \mathbb{Z} \,\,\right] \]

---

The well-ordering principle and mathematical induction

\(Theorem\) [Humphreys & Prest 1.2.2 pp. 20]

The well-ordering principle implies the principle of mathematical induction.

\[ WellOrdering \implies Induction \]

\(Proof \,\, by \,\, contradiction\) [Humphreys & Prest pp. 21]

Let \(P(n)\) satisfy the conditions for the induction principle: so \(P(1)\) holds whenever \(P(k)\) holds and so also does \(P(k + 1)\).
Let \(S\) be the set of positive integers \(m\) for which \(P(m)\) is false.
Either \(S\) is the empty set or else \(S\) is non-empty.

Let \(S\) be non-empty.
Then the well-ordering principle says that there is a least element \(t \in S\).
\(1 \not\in S\) since \(P(1)\) holds and so \(t \gt 1 \iff t - 1 \gt 0\) (i.e., \(t - 1\) is positive).
\(P(t - 1)\) holds since \(t\) is the least element of \(S\) (the set of positive integers for which \(P(n)\) does not hold).
But since \(t = (t - 1) + 1\) it follows by our assumption on \(P\) (take \(k = t - 1\)) that \(P(t)\) does hold.
\(Contradiction!\)
\(\therefore S = \varnothing\).

\(\therefore \forall n \in \mathbb{P} \,\, [ \,\, P(n) \,\, ]\)

\(\blacksquare\)

\(Claim\)

The principle of mathematical induction implies the well-ordering principle.

\[ Induction \implies WellOrdering \]

\(Claim\)

Mathematical induction holds iff the well-ordering principle holds.

\[ Induction \iff WellOrdering \]

Variations on the induction principle

\(Induction \,\, Principle \,\, variation\)

Let \(P(n)\) be an assertion involving the variable \(n\).
If

1. \(P(n_0)\) holds for an integer \(n_0\) and

2. for each integer \(k \ge n_0\) whenever \(P(k)\) holds so also does \(P(k + 1)\)

then \(P(n)\) holds for all integers \(k \ge n_0\).

In other words, the induction need not start at \(n = 1\). For example, it may be appropriate to start with the base case at \(n = 0\).

Strong Induction

a.k.a. Complete Induction or Course of Values Induction

\(Strong \,\, Induction\)

Let \(P(n)\) be an assertion involving the integer variable \(n\).
If

1. \(P(0)\) holds and

2. for each \(k \ge 0\), from the hypothesis that \(P\) holds for all non-negative \(m \le k\), \(P(k + 1)\) holds

then \(P(n)\) holds for every natural number \(n\).

The \(0\) could be replaced by any integer \(n_0\) and the conclusion would be modified accordingly.

This variation on mathematical induction takes note of the fact that, if in an induction we have reached the stage where we have that \(P(k)\) is true then, in getting there, we also showed that \(P(k - 1), P(k - 2), \dots\) (down to the base case) are true, so it is legitimate to use all this information (not just the fact that \(P(k)\) is true) in trying to prove that \(P(k + 1)\) holds.

The image of a sequence of dominoes is sometimes used to illustrate the idea of proof by induction. Imagine a straight line of dominoes: these corresponds to the integers. They are sufficiently close together that if any one of them falls, then it will knock over the domino next to it: that corresponds to the induction step (from \(P(k)\) we get \(P(k + 1)\)). One of the dominoes is pushed over: that corresponds to the base case. In these terms, the principle of strong induction says that to knock over the \((k + 1)\) st domino we are not restricted to using just the force of the \(k\) th domino: we can also use the fact that all the previous dominoes have fallen over.

---

Fibonacci Sequence

The Fibonacci sequence is the sequence \(1, 1, 2, 3, 5, 8, 13, \dots\) where each term is the sum of the two preceding terms. Show that every two successive terms of the Fibonacci sequence are relatively prime.

The Fibonacci sequence is defined as follows.

\[\begin{split} F_n := \begin{cases} F_1 &= 1 \\ F_2 &= 1 \\ F_{n + 1} &= F_n + F_{n - 1} && n \in \{ 2, 3, \dots \} \\ \end{cases} := \begin{cases} F(0) &= 0 \\ F(1) &= 1 \\ F(n) &= F(n - 1) + F(n - 2) && n \in \{ 2, 3, \dots \} \\ \end{cases} \end{split}\]

\(Example\)

\[\begin{split} \begin{align*} & F(5) \\ = & F(4) + F(3) \\ = & F(3) + F(2) + F(2) + F(1) \\ = & F(2) + F(1) + F(1) + F(0) + F(1) + F(0) + 1 \\ = & F(1) + F(0) + 1 + 1 + 0 + 1 + 0 + 1 \\ = & 1 + 0 + 4 \\ = & 5 \\ \end{align*} \end{split}\]

\(Claim\)

Every two successive terms of the Fibonacci sequence are relatively prime.

\[ \forall n \in \mathbb{P} \,\, [\,\, gcd(F_n, F_{n + 1}) = 1 \,\,] \]

\(Proof \,\, by \,\, induction\)

Base Case

\(gcd(F_1, F_2) = gcd(1, 1) = 1\)

Induction Step

Induction Hypothesis: Let it be the case that \(gcd(F_k, F_{k + 1}) = 1\) for some positive integer \(k \ge 1\).
Let \(d\) be a common divisor of \(F_{k + 1}\) and \(F_{k + 2} = F_{k + 1} + F_k\).
Then \(d\) is also a common divisor of \(F_k\).
But \(gcd(F_k, F_{k + 1}) = 1\) and so it must be the case that \(d = 1\).

Therefore every two successive terms of the Fibonacci sequence are relatively prime.

\(\blacksquare\)

---

fibonacci = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

---

Pure Python Recursion

# 1. pure python recursion
def F01 (n : int) -> int:
# if in {0, 1} : return n
  if n < 2     : return n    #      base case
  return F01(n-1) + F01(n-2) # recursive case

%timeit F01(35) # ~ 1 s

1.1 s ± 2.36 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

cProfile.run(statement = 'F01(35)')

         29860706 function calls (4 primitive calls) in 4.769 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
29860703/1    4.769    0.000    4.769    4.769 2524435626.py:2(F01)
        1    0.000    0.000    4.769    4.769 <string>:1(<module>)
        1    0.000    0.000    4.769    4.769 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Numba-jitted Recursion

# 2. numba-jitted python recursion
@njit
def F02 (n : int) -> int:
  if n < 2 : return n        #      base case
  return F02(n-1) + F02(n-2) # recursive case

%timeit -r10 -n7 F02(35) # ~ 10 ms

41 ms ± 411 µs per loop (mean ± std. dev. of 10 runs, 7 loops each)

cProfile.run(statement = 'F02(35)')

         4 function calls in 0.047 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.047    0.047    0.047    0.047 4014199938.py:2(F02)
        1    0.000    0.000    0.047    0.047 <string>:1(<module>)
        1    0.000    0.000    0.047    0.047 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Memoized Recursion - functools

# 3. memoized python recursion - functools
@lru_cache(maxsize = None)
def F03 (n : int) -> int:
  if n < 2 : return n        #      base case
  return F03(n-1) + F03(n-2) # recursive case

%timeit -r10 -n10 fn = F03(35) # ~ 100 ns

80.4 ns ± 67.9 ns per loop (mean ± std. dev. of 10 runs, 10 loops each)

cProfile.run(statement = 'F03(35)')

         3 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Memoized Recursion - dict

# 4. memoized python recursion - dict
cache = {0: 0, 1: 1}
def F04 (n : int) -> int:
  if n in cache : return cache[n] #      base case
  cache[n] = F04(n-1) + F04(n-2)  # recursive case
  return cache[n]

%timeit -r10 -n10 F04(35) # ~ 100 ns

136 ns ± 64.4 ns per loop (mean ± std. dev. of 10 runs, 10 loops each)

cProfile.run(statement = 'F04(35)')

         4 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 2057090240.py:3(F04)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

%time F01(35) #                                pure python recursion
%time F02(35) # numba jit doesn't improve upon pure python recursion
%time F03(35) # memoized python recursion - functools performs best
%time F04(35) # memoized python recursion - dict      performs almost as well

CPU times: user 1.11 s, sys: 4.26 ms, total: 1.11 s
Wall time: 1.11 s
CPU times: user 40.8 ms, sys: 230 µs, total: 41 ms
Wall time: 41.1 ms
CPU times: user 1 µs, sys: 1 µs, total: 2 µs
Wall time: 2.62 µs
CPU times: user 2 µs, sys: 0 ns, total: 2 µs
Wall time: 2.86 µs

9227465

The memoized pure python function computes very large terms efficiently.

sys.getrecursionlimit()

1000

print(F03(int(4e2)))
print(F04(int(4e2)))

176023680645013966468226945392411250770384383304492191886725992896575345044216019675
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

# sys.setrecursionlimit(2_000)
# sys.getrecursionlimit()

# sys.setrecursionlimit(1_000)
# sys.getrecursionlimit()

---

Cython recursion

%%cython
def F05 (int n):
  if n < 2 : return n
  else     : return F05(n-1) + F05(n-2)

%timeit -r7 -n2 F05(35) # ~ 500 ms

460 ms ± 1.36 ms per loop (mean ± std. dev. of 7 runs, 2 loops each)

cProfile.run(statement = 'F05(35)')

         3 function calls in 0.476 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.476    0.476    0.476    0.476 <string>:1(<module>)
        1    0.000    0.000    0.476    0.476 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Object-oriented Memoization

# 6. memoized object-oriented recursion
class f06:

  def __init__ (self):
    self.cache = [0, 1]

  def __call__ (self, n):
    # validate the value of n
    if not (isinstance(n, int) and n >= 0):
      raise ValueError(f'Positive integer number expected, got "{n}"')
    # check for computed Fibonacci numbers
    if n < len(self.cache):
      return self.cache[n]
    else:
      # compute and cache the requested Fibonacci number
      fib_number = self(n - 1) + self(n - 2)
      self.cache.append(fib_number)
    return self.cache[n]
  
F06 = f06()

%timeit -r10 -n10 F06(35) # ~ 250 ns

255 ns ± 86.8 ns per loop (mean ± std. dev. of 10 runs, 10 loops each)

cProfile.run(statement = 'F06(35)')

         6 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 1233081411.py:7(__call__)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Pure Python Iterative

# 7. pure python iterative

# def F07 (n : int) -> int:
#   # validate the value of n
#   if not (isinstance(n, int) and n >= 0) : raise ValueError(f'Positive integer number expected, got "{n}"')
#   # base cases
#   if n in {0, 1}                         : return n
#   # compute the next Fibonacci number, remember the previous one
#   previous, fib_number = 0, 1
#   for _ in range(2, n + 1)               : previous, fib_number = fib_number, previous + fib_number
#   return fib_number

def F07 (n : int) -> int:
  x, y = 0, 1
  for i in range(1, n + 1):
    x, y = y, x + y
  return x

%timeit -r10 -n10 F07(35) # ~ 1 micro s

963 ns ± 85.6 ns per loop (mean ± std. dev. of 10 runs, 10 loops each)

cProfile.run(statement = 'F07(35)')

         4 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 693775523.py:13(F07)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Numba-jitted Iterative

# 8. numba-jitted iterative
@njit
def F08 (n : int) -> int:
  x, y = 0, 1
  for i in range(1, n + 1):
    x, y = y, x + y
  return x

%timeit -n10 -r10 F08(35) # ~ 200 ns

201 ns ± 158 ns per loop (mean ± std. dev. of 10 runs, 10 loops each)

cProfile.run(statement = 'F08(35)')

         4 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 1632023275.py:2(F08)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Cython Iterative 1

%%cython
def F09 (int n):
  cdef long i
  cdef long x = 0, y = 1
  for i in range(1, n + 1):
    x, y = y, x + y
  return x

%timeit -r7 -n2 F09(35) # ~ 300 ns

348 ns ± 305 ns per loop (mean ± std. dev. of 7 runs, 2 loops each)

cProfile.run(statement = 'F09(35)')

         3 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

---

Cython Iterative 2

%%cython
cdef extern from *:
  ctypedef int int128 '__int128_t'
def F10 (int n):
  cdef int128 i
  cdef int128 x = 0, y = 1
  for i in range(1, n + 1):
    x, y = y, x + y
  return x

%timeit -r7 -n2 F10(35) # ~ 300 ns

300 ns ± 192 ns per loop (mean ± std. dev. of 7 runs, 2 loops each)

Why does Cython Iterative 2 take longer than Cython Iterative 1?

---

#print(F01(40)) #                                pure python recursion
#print(F02(40)) # numba jit doesn't improve upon pure python recursion
print(F03(100)) # memoized python recursion - functools performs best
print(F04(100)) # memoized python recursion - dict      performs almost as well
#print(F05(100)) # Cython recursion
print(F06(100)) # memoized object-oriented
print(F07(100)) #  pure python iterative
print(F08(100)) # numba-jitted iterative
print(F09(100)) # Cython iterative 1
print(F10(100)) # Cython iterative 2

354224848179261915075
354224848179261915075
354224848179261915075
354224848179261915075
3736710778780434371
3736710778780434371
354224848179261915075

---

\(Binet \,\, Formula\)

\[ F_n = \frac{\phi^n - \psi^n}{\phi - \psi} = \frac{\phi^n - \psi^n}{\sqrt{5}} \]

where

\[ \phi = \frac{1 + \sqrt{5}}{2} \]

is the golden ratio and

\[ \psi = \frac{1 - \sqrt{5}}{2} \]

is its conjugate.

---

Fibonacci - to review

To calculate \(F(n)\) the maximum depth of the call tree is \(n\). Each function call produces two additional function calls.

\(O(2^n)\) exponential for naive recursive
\(O(n)\) linear for memoized recursive and iterative

def F12 (n : int) -> int:
  v1, v2, v3 = 1, 1, 0
  for rec in bin(n)[3:]:
    calc = v2*v2
    v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
    if rec=='1': v1, v2, v3 = v1+v2, v1, v2
  return v2

F12(80)

23416728348467685

%timeit F12(35)

516 ns ± 11.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

---

Resources

• https://math.stackexchange.com/questions/228863/recursive-vs-inductive-definition

• https://kconrad.math.uconn.edu/blurbs/proofs/induction.pdf

• https://kconrad.math.uconn.edu/blurbs/proofs/binomcoeffintegral.pdf

---

Terms

• [ w ] Base Case

• [ w ] Binet Formula

• [ w ] Binomial

• [ w ] Binomial Coefficient

• [ w ] Binomial Theorem

• [ w ] Cassini’s Identity

• [ w ] Complete Induction

• [ w ] Course of Values Induction

• [ w ] Fibonacci Sequence

• [ w ] Induction

• [ w ] Induction Hypothesis

• [ w ] Induction Step

• [ w ] Iteration

• [ w ] Iterative Method

• [ w ] Linear Difference Equation

• [ w ] Linear Recurrence Relation

• [ w ] Linear Recurrence with Constant Coefficients

• [ w ] Mathematical Induction

• [ w ] Memoization

• [ w ] Pascal’s Triangle

• [ w ] Recurrence Relation - A recurrence relation is an equation that expresses each term of a sequence as a function of the preceding ones.

• [ w ] Recursion

• [ w ] Strong Induction

---

Acknowledgements

Bressoud, David M. (1989). Factorization and Primality Testing. Springer Undergraduate Texts in Mathematics.

Crandall, Richard & Carl Pomerance. (2005). Prime Numbers: A Computational Perspective. Springer.

Davenport, Harold. (2008). The Higher Arithmetic: An Introduction to the Theory of Numbers. Cambridge University Press.

Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.

LeVeque, William J. (1996). Fundamentals of Number Theory. Dover.

[ h ] Vaughan, Robert. (2023). A Course of Elementary Number Theory. CMPSC/MATH 467 Factorization and Primality Testing. The Pennsylvania State University.

Wagstaff Jr., Samuel S. (2013). The Joy of Factoring. AMS Student Mathematical Library.

---