Induction
Contents
Induction¶
What happens if we want to know something is true for an infinite number of values? We already saw that first order logic can let us work with some concepts related to infinite sets. It doesn’t give us everything we need.
Proof by Induction allows you to prove something is true for an infinite set.
The basic concept behind Proof by Induction is that we can prove a small subset of values are true by testing. We can’t prove test and infinite amount of things. We then prove and implication that the small subset we tested implies additional items. If we can create an implies that covers all possible values, then we can conclude that a statement is true for an infinite amount of values.
Mathematical Induction¶
We claim that the sum of the first \(n\) odd numbers is always each to \(n^2\). We can generate the \(i\)th odd number using the following formula.
\( \begin{align*} \text{oddNum}(i) =2i+1 \end{align*} \)
Since we are computer scientists, we will index starting at zero. The zero-th even number is 0. The zero-th odd number is 1. The odd number is just one larger than the even number. The \(i\)-th even number is just \(2i\). To find the \(i\)-th odd number we just add one.
To sum up the first \(n\) odd numbers, we just need a summation. Since we are indexing starting at \(0\), the first \(n\) numbers are in the range \(0\cdots(n-1)\).
\( \begin{align*} \sum_{i=0}^{n-1} \text{oddNum}(i) =& n^2 \end{align*} \)
We can test this on a few simple cases.
\( \begin{align*} \sum_{i=0}^{1-1} \text{oddNum}(i) =& 1 \\ \sum_{i=0}^{2-1} \text{oddNum}(i) =& 1+3=4 \\ \sum_{i=0}^{3-1} \text{oddNum}(i) =& 1+3+5=9 \\ \sum_{i=0}^{4-1} \text{oddNum}(i) =& 1+3+5+7=16 \end{align*} \)
That appears to be a sequence of squares.
\( \begin{align*} (1)^2 =& 1 \\ (2)^2 =& 4 \\ (3)^2 =& 9 \\ (4)^2 =& 16 \end{align*} \)
It looks like the formula is correct. How can we be sure? How can we know that when \(n=637982\) the formula won’t stop working? Maybe it is only value what \(n < 10,000\) or \(n < 199,999,872,334\). We could test up to a point, but there are infinite values.
The best we can do with testing is to say
\( \begin{align} \forall n \in \mathbb{N} \left( 1 \le n \le 4\right) \implies \left( \sum_{i=0}^{n-1} \text{oddNum}(i) = n^2 \right) \end{align} \)
We can define a fixed range and test it.
What if we could provide some evidence that knowing the function works in \(\forall n \in \mathbb{N} \left( 1 \le n \le 4\right)\) would imply it was also true for \(\forall n \in \mathbb{N} \left( 1 \le n \le 5\right)\). We won’t have to test \(5\), we could just imply the larger range.
More generally, what if we could imply an infinite chain we won’t need to test and infinite number of times.
\( \begin{align*} \left( \forall n \in \mathbb{N} \left( 1 \le n \le 4\right) \implies (\cdots) \right) \implies& \left( \forall n \in \mathbb{N} \left( 1 \le n \le 5\right) \implies (\cdots) \right) \\ \implies & \left( \forall n \in \mathbb{N} \left( 1 \le n \le 6\right) \implies (\cdots) \right) \\ \implies & \left( \forall n \in \mathbb{N} \left( 1 \le n \le 7\right) \implies (\cdots) \right) \\ \implies & \left( \forall n \in \mathbb{N} \left( 1 \le n \le 8\right) \implies (\cdots) \right) \\ \implies & \cdots \end{align*} \)
If we could make this sequence go on forever, then we can prove an infinite sequence. Think of this as a sequence of dominos. We need them all to fall down. We have to prove by experimentation that the first few actually fall over. We also prove that when one domino falls, it will always hint the next one. Since we know the dominos start falls and every one must hit the next one, we know they will all fall down.
To put this more formally, we need to prove a sequence of facts are true. We can call them \(S_1\), \(S_2\), \(S_3\), etc. These are statements we verify explicitly. Then we need to create an implication \(S_{k} \implies S_{k+1}\) for the remaining statements.
We want to prove:
\( \begin{align*} S_{1} \wedge S_{2} \wedge S_{3} \wedge \cdots \wedge S_{n} \wedge \left( \forall k \in \mathbb{N}_{\ge n} \left( S_{k} \implies S_{k+1} \right) \right) \end{align*} \)
The initial dominos are the cases we prove explicitly. The fact that each domino will hit the next one is proven by \(\forall k \in \mathbb{N}_{\ge n} \left( S_{k} \implies S_{k+1} \right)\).
How can we go about proving this statement. It is a for all statement, so we need to create a constant that could be any value in the range. That way at the end of our proof, we know it is true for any constant by \(\forall I\). To prove the implication, we need to assume the left hand and prove the right. If we can do that, we know the implication holds by \(\implies I\).
We have already shown for cases for our summation formula.
\( \begin{align*} S_{1} =& \sum_{i=0}^{1-1} \text{oddNum}(i) = 1^2 \\ S_{2} =& \sum_{i=0}^{2-1} \text{oddNum}(i) = 2^2 \\ S_{3} =& \sum_{i=0}^{3-1} \text{oddNum}(i) = 3^{2} \\ S_{4} =& \sum_{i=0}^{4-1} \text{oddNum}(i) = 4^{2} \end{align*} \)
We can make the induction template explicit for this situation.
\( \begin{align*} S_{1} \wedge S_{2} \wedge S_{3} \wedge S_{4} \wedge \left( \forall k \in \mathbb{N}_{\ge 4} \left( S_{k} \implies S_{k+1} \right) \right) \end{align*} \)
We need to prove the implies hold for all values. So, we need an to start with an assumption that could be true for any value.
We assume their exists a range of numbers \(1 \le k \le m\) such that our formal holds. We know one range for a face \(1 \le k \le 4\), but if we fix the value at \(4\) we are no longer doing a for all. We need to talk about any range that could be justified. We give the variable \(m\). As long as these is some end to this range and it holds for the hold range, we are happy.
We assume that
\( \begin{align} \forall k \in \mathbb{N} \left( (1 \le k \le m) \implies \left( \sum_{i=0}^{k-1} \text{oddNum}(i) = k^2 \right) \right) \end{align} \)
Now, we need to create the implies \(\left( S_{k} \implies S_{k+1} \right)\). We need to use this assumption to prove that \(S_{k+1}\) will still be true. A number outside the range.
The last value in the range is some constant \(m\). We need to see what happens with \(m+1\).
What happens to the formal when we plug in \(m+1\)?
\( \begin{align*} \sum_{i=0}^{(m+1)-1} \text{oddNum}(i) =& \sum_{i=0}^{(m+1)-1} 2i+1 \\ =& \sum_{i=0}^{m} 2i+1 \end{align*} \)
This sum goes from \(i=0\) to \(m\). It is just a summation, we can break it apart into multiple parts.
\( \begin{align*} \sum_{i=0}^{m} 2i+1 =& \left( \sum_{i=0}^{m-1} 2i+1 \right) + 2m+1 \end{align*} \)
We assumed this smaller sum did evaluate correctly. We claim what because of our assumption we know that
\( \begin{align*} \sum_{i=0}^{m} 2i+1 =& \left( \sum_{i=0}^{m-1} 2i+1 \right) + 2m+1 \\ =& m^2 + 2m+1 \end{align*} \)
This is just true because we assumed the formula worked in the range \((1 \le k \le m)\).
We can factor the formula.
\( \begin{align} m^2 + 2m + 1 =& (m+1)^2 \end{align} \)
This tells us that if the formula holds at constant \(m\) it also holds at \(m+1\). We know it holds at \(4\), so it must hold at \(5\). If it must hold at \(5\) then it must hold at \(6\). This goes on forever.
We now know this formula is always true.
The process we used is called induction. We did not complete the induction in a formal manner yet. Since the basic principles of induction are well known, we can formalize the process.
Induction in Racket Code¶
We will be using induction on Racket functions. This means our formal methodology is designed around programming. It will look different from induction in other fields.
Let’s rewrite the summation above as a recursive function. It would be hard to deal with the \(n-1\) in the summation, so this shifts the values in the addition. We also add a base case of 0 for any inputs below 1.
;Sum the first n odd numbers
;1 is considered the 0th odd number
;input-contract: (int? n)
;output-contract: (int? (sumOdd n))
(define (sumOdd n)
(if (<= n 0)
0 ;Base Case
(+ (- (* 2 n) 1)
(sumOdd (- n 1)))
);End If
);End of Define
We can test the function, but this is not a proof.
;Tests
(sumOdd 1) ; Returns 1
(sumOdd 2) ; Returns 4
(sumOdd 3) ; Returns 9
(sumOdd 4) ; Returns 16
We want to prove by Induction that (sumOdd n) evaluates to \(n^2\). This combination of code and algebraic notation is common. We are confirming that a function we designed is the same as a target expression.
A proof by induction starts with an argument. There is something we want to prove. We need to start this at the beginning. This allows our reader to understand the purpose of the proof.
Next, we need to write one or more Base Cases. A Base Case is a case we are proving for an explicit value. These are our initial starting values. This proof is normally completed using Equational Reasoning. At the end of our proof, we provide a conclusion to summarize what we justified.
;Proof By Induction
;Argument: (sumOdd n) = n^2 for all integers n >= 1
;Base Case
;We prove that (sumOdd 1) = 1^2
;1. (sumOdd 1) ;Premise
;2. (if (<= 1 0) 0 (+ (- (* 2 1) 1) (sumOdd (- 1 1)))) ;Apply Definition of sumOdd
;3. (if #f 0 (+ (- (* 2 1) 1) (sumOdd (- 1 1)))) ;Evaluate Less Than Equal To
;4. (+ (- (* 2 1) 1) (sumOdd (- 1 1))) ;Evaluate If
;5. (+ (- 2 1) (sumOdd (- 1 1))) ;Evaluate Multiplication
;6. (+ 1 (sumOdd 0)) ;Evaluate Subtractions
;7. (+ 1 (if (<= 0 0) 0 (+ (- (* 2 0) 1) (sumOdd (- 0 1))))) ;Apply Definition of sumOdd
;8. (+ 1 (if #t 0 (+ (- (* 2 0) 1) (sumOdd (- 0 1))))) ;Evaluate Less Than Equal To
;9. (+ 1 0) ;Evaluate If
;10. 1 ;Evaluate Addition
;Conclusion: The function evaluates to 1, which is 1^2=1
After our Base Case(s), we have our Inductive Case(s). As we saw in the previous section, these proofs require assumptions. We start by explaining our Inductive Hypothesis. What are we assuming is true in this proof?
After the assumption has been established, we again use Equational Reasoning to write our proof. There are a few new additions to Equational Reasoning here. First, evaluations may be symbolic. We can state that (- (+ k 1) 1) evaluates to k.
The most important new rule is by IH. This is short for by inductive hypothesis. It means that this line is only correct because we assumed it would be earlier in the proof. This assumption needs to make sense in relation to our base case.
Lastly, we often want to use some algebraic rules. If all programming constructs have been evaluated, we can rewrite the formula algebraically. This can only be done once the racket code has been evaluated to the point at which it represents a simple math expression.
There are three common algebraic rules at will appear frequently. Any algebraic rule can be used. The most common three are:
Expand - multiply out values to make the expression longer
Simplify - Simplify common terms (\(2x+3x=5x)\)
Factor - Factor out a multiplicative value
The formal inductive case is given below. At the end of the proof, we provide a conclusion for the inductive case, then a final conclusion for the entire proof.
;Inductive Case
;Inductive Hypothesis: Assume the following:
;For any integer m in the range 1 <= m <= k we know that
;(sumOdd m) will return m^2
;We show this IH causes (sumOdd (+ k 1)) to return (k+1)^2
;1. (sumOdd (+ k 1)) ;Premise
;2. (if (<= (+ k 1) 0) 0 (+ (- (* 2 (+ k 1)) 1) (sumOdd (- (+ k 1) 1)))) ;Apply Definition of sumOdd
;3. (if #f 0 (+ (- (* 2 (+ k 1)) 1) (sumOdd (- (+ k 1) 1)))) ;Evaluate Less Than Equal To
;4. (+ (- (* 2 (+ k 1)) 1) (sumOdd (- (+ k 1) 1))) ;Evaluate If
;5. (+ (- (* 2 (+ k 1)) 1) (sumOdd k)) ;Evaluate Subtraction
;6. (+ (- (* 2 (+ k 1)) 1) (* k k)) ;By IH
;7. 2(k+1)-1 + k*k ;Rewrite Algebraically
;8. 2k+2-1+k^2 ;Expand
;9. k^2+2k+1 ;Simplify
;10. (k+1)^2 ;Factor
;Conclusion: If the IH is true then (sumOdd (+ k 1)) will return (k+1)^2
;By Induction, we have show that (sumOdd n) = n^2 for all integers n >= 1
Examples¶
Example 1¶
In this example, we will show that a function \(f(n)\) evaluates to \(\frac{1}{2}\left( n(n+1) \right)\).
The function \(f\) is defined in Racket.
(define (f n)
(if (= n 1)
1
(+ n (f (- n 1)))
)
)
We can define the target expression as well.
(define (expected n)
(* (/ 1 2) (* n (+ n 1)))
)
We compare a few small values.
(equal? (f 1) (expected 1)) ;#t
(equal? (f 2) (expected 2)) ;#t
(equal? (f 3) (expected 3)) ;#t
(equal? (f 4) (expected 4)) ;#t
(equal? (f 5) (expected 5)) ;#t
The function \(f\) here is computing the sum of all numbers from \(1\) to \(n\).
\( \begin{align*} \text{(f 5)} =& 1+2+3+4+5+6+7 = 28 \end{align*} \)
This is a sequence that appears often when we are iterating over loops. The following Python code uses two loops to print a triangle.
def dots(n):
for i in range(0,n+1):
for j in range(0,i):
print("*",end="")
print()
dots(7)
It produces the following output.
*
**
***
****
*****
******
*******
The number of dots printed is (f n).
We prove by induction that (f n) evaluates to \(\frac{1}{2}\left( n(n+1) \right)\) for all natural numbers.
;Proof by Induction
;Argument: (f n) = 1/2(n(n+1)) for all integers n >= 1
;Base Case
;We prove that (f 1) = 1/2 * (1 * (1+1) )
;1. (f 1) ;Premise
;2. (if (= 1 1) 1 (+ 1 (f (- 1 1)))) ;Apply Definition of f
;3. (if #t 1 (+ 1 (f (- 1 1)))) ;Evaluate Equals
;4. 1 ;Evaluate If
;Conclusion the function returns 1, which is the same as 1/2*(1*(1+1))=1/2*2=1
;Inductive Case
;Inductive Hypothesis:
;Assume for any integer m in range 1 <= m <= k
;we know that (f m) = 1/2*(m*(m+1))
;We show this IH causes (f (+ k 1)) to return 1/2*((k+1)(k+2))
;1. (f (+ k 1)) ;Premise
;2. (if (= (+ k 1) n) 1 (+ (+ k 1) (f (- (+ k 1) 1))) ;Apply Def of f
;3. (if #f 1 (+ (+ k 1) (f (- (+ k 1) 1))) ;Evaluate Equals
;4. (+ (+ k 1) (f (- (+ k 1) 1)) ;Evaluate If
;5. (+ (+ k 1) (f k)) ;Evaluate Subtraction
;6. (+ (+ k 1) (* (/ 1 2) (* k (+ k 1))) ;by IH
;7. (k+1) + 1/2*(k*(k+1)) ;Algebraic Rewrite
;8. 2(k+1)/2 + 1/2*(k*(k+1)) ;Common Demoninator
;9. 1/2*( 2k+2 ) + 1/2*( k^2+k ) ;Expand
;10. 1/2* ( k^3+3k+2 ) ;Simplifiy
;11. 1/2* ( (k+1)(k+2) ) ;Factor
;Conclusion: If the IH is true then (f (+ k 1)) will return 1/2((k+1)(k+2))
;By Induction, we have show that (f n) = 1/2(n(n+1)) for all integers n >= 1
Example 2¶
We prove that for all integers \(A \ge 0\) and \(B \ge 0\) the following function will add.
(define (add a b)
(if (= b 0)
a
(+ 1 (add a (- b 1)))
)
)
We can start with a sanity check test.
(add 8 9) ;Returns 17
The inductive proof is given below. This proof as one interesting property not seen before. There are two inputs to the function. Only one of these inputs ever changes. The function never changes \(a\). We can take this into account during out proof.
;Proof by Induction
;Argument: (add a b) = a+b for all integers a >= 0, b >= 0
;For this entire proof, let x be a constant integer x >= 0
;Base Case
;We prove that (add x 0) = x
;1. (add x 0) ;Premise
;2. (if (= 0 0) x (+ 1 (add x (- 0 1)))) ;Apply Definition of add
;3. (if #t x (+ 1 (add x (- 0 1)))) ;Evaluate Equals
;4. x ;Evaluate If
;Conclusion the function returns x, which is the same as x+0
;Inductive Case
;Inductive Hypothesis:
;Assume for any integer m in range 1 <= m <= k
;we know that (add x m) = x+m
;We show this IH causes (add x (+ k 1)) to return x+k+1
;1. (add x (+ k 1)) ;Premise
;2. (if (= (+ k 1) 0) x (+ 1 (add x (- (+ k 1) 1)))) ;Apply Definition of add
;3. (if #f x (+ 1 (add x (- (+ k 1) 1)))) ;Evaluate Equals
;4. (+ 1 (add x (- (+ k 1) 1))) ;Evaluate If
;5. (+ 1 (add x k)) ;Evaluate Subtraction
;6. (+ 1 (+ x k)) ;By IH
;7. x+k+1 ;Algebraic Rewrite
;Conclusion: If the IH is true then (add x (+ k 1)) will return x+k+1
;By Induction, we have show that (add a b) = a+b for all integers a >= 0, b >= 0