In addition to such techniques as direct proof, proof by contraposition, proof by contradiction, and proof by cases, there is a fifth technique that is quite useful in proving quantified statements: Proof by Induction!
Jenn, Founder Calcworkshop®, 15+ Years Experience (Licensed & Certified Teacher)
What Is Proof By Induction
Inductive proofs are similar to direct proofs in which every step must be justified, but they utilize a special three step process and employ their own special vocabulary.
Inductive Process
Steps for proof by induction:
- The Basis Step.
- The Hypothesis Step.
- And The Inductive Step.
Where our basis step is to validate our statement by proving it is true when n equals 1. Then we assume the statement is correct for n = k, and we want to show that it is also proper for when n = k+1.
The idea behind inductive proofs is this: imagine there is an infinite staircase, and you want to know whether or not you can climb and reach every step.
Staircase Analogy
If you can reach the first step (basis step), you can get the next step. And if you can ascend to the following step, then you can go to the one after it, and so on. Therefore, if it is true for the first step, then we will assume it is also appropriate for the kth step (guess). What is more, if it is correct for the kth step, it must be proper for the k+1 step (inductive).
So, the idea behind the principle of mathematical induction, sometimes referred to as the principle of induction or proof by induction, is to show a logical progression of justifiable steps.
Sometimes it’s best to walk through an example to see this proof method in action.
Example #1
Induction Proof Example — Series
That’s it!
We write our basis step, declare our hypothesis, and prove our inductive step by substituting our “guess” when algebraically appropriate.
Now, I do want to point out that some textbooks and instructors combine the second and third steps together and state that proof by induction only has two steps:
- Basis Step.
- Inductive Step.
While this is perfectly fine and reasonable, you must state your hypothesis at some point at the beginning of your proof because this process is only valid if you successfully utilize your premise. In addition, Stanford college has a handy PDF guide covering some additional caveats.
This means that you have first to assume something is true (i.e., state an assumption) before proving that the term that follows after it is also accurate.
I like to think of it this way — you can only use it if you first assume it!
While most inductive proofs are pretty straightforward there are times when the logical progression of steps isn’t always obvious. Therefore, we will have to be a bit creative.
For instance, let’s work through an example utilizing an inequality statement as seen below where we’re going to have to be a little inventive in order to use our inductive hypothesis.
Example #2
Inductive Proof Example — Inequality
Did you spot our sneaky maneuver?
By saying that (K+1) < (K+K) we were able to employ our inductive hypothesis and nicely verify our "k+1" step! Together we will look at numerous questions in detail, increasing the level of difficulty, and seeing how to masterfully wield the power of prove by mathematical induction.
Video Tutorial w/ Full Lesson & Detailed Examples
1 hr 48 min
Get access to all the courses and over 450 HD videos with your subscription
Monthly and Yearly Plans Available
Still wondering if CalcWorkshop is right for you?
Take a Tour and find out how a membership can take the struggle out of learning math.