Proof by Induction (Teng Hui)
Inductive reasoning versus deductive reasoning
For inductive reasoning:
- Start with a specific conclusion (i.e. Shaq and Yao play basketball)
- Arrive at generalization (i.e. all tall players play basketball)
For deductive reasoning:
- Start with general facts (all birds have feathers)
- Specific fact (sparrow has feathers)
- Conclusion (sparrow is a bird)
False induction in math: it’s not valid to draw a conclusion by simply testing a few values
For example:
f(n) = n2 – 40n + 41 or an equation similar to it that seemingly yields prime numbers for values of n, but doesn’t work for n values beyond a few terms
Inductive proof method, to prove a formula true for a particular variable for all non-negative or positive integers:
1)Prove the equation works for n = 0 or n = 1 (base case)
2)Assume the equation works for an arbitrary integer k (inductive hypothesis)
3)Prove the statement is true for n = k + 1 (inductive step)
4)If k + 1 is valid, then the formula proves that the equation works for one value, the value after, and so on.
Here's an example:
We'll prove that for all positive integers n.
Base case. n = 1. LHS = , RHS = , so the base case holds.
Inductive hypothesis: Assume for an arbitrary positive integer n=k that
Inductive step: Prove for n=k+1 that
, plugging into the inductive hypothesis
, which proves the inductive step.
Thus, we can conclude that for all positive integers n, .
In some sense this proof technique looks like a bit of magic. Let's investigate where it can break down:
1) When the base case doesn't work.
2) When the inductive step can't be proved.
We will show the attempted proof of two false statements that illustrate both of these problems.
1) Prove that , for all positive integers n.
We can see that plugging in n=1 to both the left and right hand sides does not yield a true statement, so that is the problem in proving this statement. Interestingly enough however, for this particular example, it turns out that you CAN actually prove the inductive step:
Inductive hypothesis: Assume for an arbitrary positive integer n=k that
Inductive step: Prove for n=k+1 that
, plugging into the inductive hypothesis
, proving the inductive step.
So for this problem, we see that if the formula were true for n=k, then it would also have to be true for n=k+1. But, the problem is that there is no value of k for which the formula is true, so proving the inductive step unfortunately proves nothing about the original formula we had.
2) Prove that , for all positive integers n.
Here the base case holds, since for n=1, both the left and right hand sides equal 1.
Now let's take a look at how trying to prove the inductive step breaks down:
Inductive hypothesis: Assume for an arbitrary positive integer n=k that
Inductive step: Prove for n=k+1 that
,
At this point we are stuck, because it's impossible for us to get 3k to equal 2k+1. Most of the time, this is false. Thus, it's impossible to show in the general case that if the formula is true for k, that it is true for k+1. In this particular case, the formula is true for n=1 and n=2, but then is false otherwise.
Hopefully these two examples solidify exactly how mathematical induction works and why it properly can prove a general statement about all positive integers.