In this tutorial, I will introduce proofs using math induction as well as Big-O proofs. Proof by math induction is a common way to prove theorems in computer science. The idea behind math induction is that it is impossible to verify that all the terms in a set are valid for a given theorem. Therefore, math induction is used to say that if the theorem holds up to an arbitrary value n, then it also holds for the n+1 term. Think about it like a domino effect. Thus it is also important that the set of elements in the domain are ordered.
As with any proof, inductive proofs start with the theorem. For this first proof, let's use the theorem: 2n < n!, for all n >= 4, where n is in the set of natural numbers.
The next step is to verify the base case(s). When this step is reached, it is sometimes necessary to verify more than one base case. When only one base case is necessary, this is called weak induction. When more than one base case is necessary, it is called strong induction. A prime example of when to use strong induction is for recursive sequences with multiple base cases or terms of multiple preceding terms in the definition. The theorem 2n < n! only requires weak induction, however.
16 < 24, so this inequality holds for n = 4.
The next step is to state the inductive assumption and hypothesis. The inductive assumption is the point in the proof where we assume that the inequality holds true up to some arbitrary value k. The inductive hypothesis states that if the inductive assumption holds, then the theorem can be proven true for the k+1 case.
I have assumed that the theorem holds true from n = 4, where n is a natural number, up to some arbitrary value k, where k is a natural number (ie., 2k < k!). I will now prove true for the k+1 case (ie., 2k+1 < (k+1)!).
The next step is to actually prove true for the k+1 case.
By the inductive assumption, we know that 2k < k!
I will now multiply both sides by 2, to get: 2 * 2k < 2* k!
By the rules of exponents, we can simplify this to: 2k+1 < 2 * k!
Because we know that the smallest value in the truth set is k = 4, k must be greater than 2. Therefore, k+1 must also be greater than 2. So the following inequality must also be true: 2k+1 < (k+1) * k!
By the definition of a factorial, we can simplify: 2k+1 < (k+1)!
We have assumed that the theorem 2n < n! holds true from n = 4 up to some arbitrary value k, and have proven true for k+1. Therefore, by the principle of math induction, the theorem holds true.
is less than 2n, where n is in the set of natural numbers.
Because we have two base cases, we will need to verify these both in our first step. Since there is a recurrence, we will verify a single case of that as well.
0 < 1, so the inequality holds.
1 < 2, so the inequality holds.
1 < 4, so the inequality holds.
I have assumed the theorem is true from n = 0, where n is a natural number, up to some arbitrary value k, where k is a natural number (ie., fk < 2k). I will now prove true for the k+1 case (ie., fk+1 < 2k+1).
Since (1+1/2) < 2, we know that 2k(1+1/2) < 2k(2), meaning that fk + fk-1 < 2k(2) by transitivity.
I have assumed that the theorem fn < 2n from n = 0, where n is a natural number, up to k, which is also a natural number, and proven true for k+1. Therefore, by the principle of math induction, the theorem holds for all natural numbers.
Given functions f(n) and g(n), f(x) is O(g(n)) if and only if there exist constants C and k in the set of positive integers such that the following inequality holds: |f(x)| <= C * |g(x)|, for all x >= k, where x is in the set of positive integers.
Theorem: f(n) = 2n is Big-O g(n) = n!
To prove that 2n is O(n!), we need to show that there exist constants C and k in the set of positive integers such that |2x| <= C * |x!|, for all x >= k, where x is in the set of positive integers.
Theorem: 2n < n!, for all n >= 4, where n is in the set of natural numbers.
Conclusion: We have assumed that the theorem 2n < n! holds true from n = 4 up to some arbitrary value k, and have proven true for k+1. Therefore, by the principle of math induction, the theorem holds true.
|2x| <= 1 * |x!|, for all x >= 4, where x is a positive integer. We have proven that this inequality holds using induction. Therefore, we have satisfied the definition that f(n) is O(g(n)).
Thanks for the tutorial. Proof by induction is something I always meant to read up on but never had. It isn't in the school maths curriculum in Scotland, and all the maths classes I did at uni were geared towards calculus or numerical methods.
Proof by induction is part of Advanced Higher Math curriculum.
Sounds like a good thing. Did they introduce it with the switch from Revised Higher to Higher Still? I was in the last year of Revised Higher. If it was in the curriculum back then, I don't remember my teacher ever mentioning it in class.
This so helpful TY very much but would you use proof by contradiction to prove n! is not O(2^n)?
I would just use direct proof. Because 2^n is O(n!) and the induction proof shows that n! > 2^n starting at n = 4, n! cannot be 2^n.