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\).
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\):
The number \(1\) is in \(S\). This is proved explicitly in the base case of the proof.
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
The number \(1\) is a natural number.
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
\(P(1)\) holds and
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.
Base Case - show \(P(1)\).
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.
One greater than any term in \(a\) is divisible by \(3\).
\(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}\).
\(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}\).
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.
Any term in \(a\) is divisible by \(13\).
\(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\).
Definition of the factorial symbol#
\(Definition \,\, by \,\, induction\)
Base Case
Let \(0! := 1\).
Induction Step
Let \((k + 1)! := (k + 1) \times k!\)
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.
\(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.
\(Claim\)
Mathematical induction holds iff the well-ordering principle holds.
Variations on the induction principle#
\(Induction \,\, Principle \,\, variation\)
Let \(P(n)\) be an assertion involving the variable \(n\).
If
\(P(n_0)\) holds for an integer \(n_0\) and
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
\(P(0)\) holds and
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.
\(Example\)
\(Claim\)
Every two successive terms of the Fibonacci sequence are relatively prime.
\(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\)
Resources#
https://courses.grainger.illinois.edu/cs173/fa2017/B-lecture/Lectures/InductionNotes.pdf
https://jeffe.cs.illinois.edu/teaching/algorithms/notes/98-induction.pdf
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)
#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\)
where
is the golden ratio and
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)