A proof by induction is a type of proof where you try to state something general from a smaller context. In an inductive proof, you start by assuming that something is true for a given value. Then, you want to show that if it holds for a certain value, then it has to hold for the following value as well. If this is true for an arbitrary value, it must be true for all values.
Here are three steps which are very useful to follow in order to construct an inductive proof:
Rule
Note! The key to proofs by induction is to insert your assumption from Item 2 into Item 3. This is the critical element of these proofs!
Example 1
Series by Induction
Show that
| (1) |
| (2) |
| (3) |
Now you have to use the assumption to write a clean expression for the first terms:
Example 2
Divisibility by Induction
Show that is divisible by 2
If something is divisible by 2, it has 2 as a factor. In other words, it must be possible to write it as , where is an integer.
| (4) |
| (5) |
Now using the assumption, gives the following:
Example 3
Derivatives by Induction
Let . Show that .
Here means that is differentiated times.
| (6) |
| (7) |
Now you need to use the assumption by writing as :