Tutor HuntResources Maths Resources
What Is Proof By Induction?
This article describes what "proof by induction" is and gives an example.
Date : 18/11/2021
Often, we want to prove a result holds for all positive integers n. For example, how do we prove that the sum of numbers from 1 to n is n(n+1)/2?
First, we prove it firsthand for the first case, n=1. (or sometimes, the first couple of cases)
Then, we ASSUME the result holds for some specific but arbitrary n. (or possibly a few adjacent values of n, i.e. n-1, n-2, ...) This is known as weak induction. Alternatively, we can assume the result holds for all values up to n. That would be known as strong induction.
We then prove that, under this assumption, the result holds for n+1. Then since we know the result holds for the base cases, we have proven that the result holds for all values of n, by induction.
Let`s look at an example. How do we prove that the sum of numbers from 1 to n is n(n+1)/2?
The result clearly holds for n=1.
Next, we assume the result holds for n, i.e. the sum of the integers from 1 to n is n(n+1)/2 for this specific n.
Next, the sum of the integers from 1 to n+1 is n(n+1)/2 + (n+1), which is of course equal to (n+1)(n+2)/2.
Therefore, we have proven the results by induction!
This resource was uploaded by: John