Proof by induction
Proof by induction for statements about integers, divisibility, inequalities, summations and derivatives: establish a base case, assume the result for n=k, then use the inductive hypothesis to prove n=k+1, often by comparing successive cases, splitting a sum, or using the product rule.
Proof by induction is used to prove statements that are true for all integers n greater than some starting value.
It is helpful to use the notation P(n) to represent the statement for an arbitrary integer n. This saves us writing the statement every time. Make sure you define
Our goal in a proof by induction is to show that
Therefore, by induction
so P(n) is true for all n∈Z+.
It is critical when writing proofs by induction to have a rigorous conclusion. You must show to the examiner grading your work that you understand induction. Your conclusion should clearly show:
You have shown the base case is true
You understand that the statement is true for n=k+1 IF it is true for n=k.
Evidence of understanding the implication is critical for earning the final mark. For example, if you say:
We have shown that the statement is true for n=k and for n=k+1 you will NOT earn the final mark.
Another common mistake is to write:
We have shown that if n=k is true then n=k+1 is true.
This does not mention the statement, and incorrectly states that n is literally equal to k and to k+1, which is impossible.
How induction works
Divisibility
We say that an integer a is divisible by b if a=kb for some integer k. In other words ba=k is an integer.
We write "a is divisible by b"
To write "a is not divisible by b" we write
Induction with divisibility
We can prove that an expression is always divisible by some integer D using induction. The easiest way to do this is to subtract the n=k case from the n=k+1 case, and show that the difference is divisible by D.
Example: Prove that 4n−1 is divisible by 3 for all n∈Z+.
Base case
The smallest number in Z+ is n=1, so we verify:
which is divisible by 3.
Assumption
Next, we assume the statement is true for n=k:
Inductive step
Now consider the statement in the case n=k+1:
We assumed earlier that 4k−1=3A, which means 4k=3A+1. We can substitute this in:
Since 4A+1 is an integer, this means 4k+1−1 is a multiple of 3.
Conclusion
We showed the statement is true in the base case n=1, and that if it is true for n=k, then it is also true for n=k+1. Hence, by induction, 4n−1 is divisible by 3 for all n∈Z+.
Induction with inequalities
Induction can be used to prove that an inequality holds. These require very careful "chains" of inequalities.
Example: Prove that 2n>n2 for n∈Z, where n≥5.
Base case
The base case is n=5, and we can verify that
So the statement is true for n=5.
Assumption
Next, assume the statement is true for n=k:
and attempt to show that it is then true for n=k+1:
Inductive step
What we want to show is that 2k+1 is greater than (k+1)2=k2+2k+1. One way to do this is to consider the difference:
In the previous step we assumed 2k>k2, so
We want to show that the difference is positive, and since the difference is quadratic we now have a quadratic inequality to solve:
First solve for the roots:
Since the quadratic is concave up, it is negative between the roots, and positive outside the roots. But since n=5>1+√2 is the base case, this quadratic is always positive. Hence
Conclusion
So if the statement is true for n=k, then it is also true for n=k+1. Having verified it is true for n=5, we can conclude by induction that the statement is true for all n∈Z where n≥5.
Induction with summation
Induction can be used to proved statements involving summations with ∑ . The key is splitting the sum, which has the form
into
and use the inductive hypothesis for r=1∑kf(r).
Induction with derivatives
Induction can be used to prove statements involving the nth derivative of a function. Almost always, the product rule will be the key technique.
Nice work completing Proof by induction, here's a quick recap of what we covered:
Skills covered
Exercises checked off