Induction
From ZuluNotes - Free Leaving Cert Notes
Contents |
Induction
Introduction
Proof by Induction can be used to prove statements in the form P(n), where n is a Natural number. An example of such a statement is that the sum of odd numbers until the nth odd number is equal to n squared. This can be written as:
1 + 3 + 5 + 7 ... (2n - 1) = n^2
One sees that the pattern seems true on inspection. For instance, the first 3 odd numbers:
1 + 3 + 5 = 9 = 3^2
However, how do we know that this holds for all n? We cannot test the statement by inserting every natural number to infinity. But we can prove this statement by induction. There are many kinds of statement which can be proved by induction, the sum of a series is only one of them.
Regardless, let's try and prove the statement 'P(n): 1 + 3 + 5 ... (2n - 1) = n^2'
Stage 1
1. Test the statement for the number which makes the first and last terms the same.
In this case, determine whether P(n) is true for 1 (Because 1 equals to (2n - 1) when n=1) This can be written as:
P(1): 1 = 1^2
This is true.
For clarity, but not necessity, we will test P(2). So this will be the sum of 1 until (2n - 1), where n=2
P(2): 1 + ( 2(2) - 1 ) = 1 + 3 = 4 = 2^2
This is true.
Stage 2
2. Assume P(k) is True. This step is difficult to understand at first. Here are two reasonable responses to such a course of action:
'What entitles us to assume that P(k) is true, especially if we are trying to prove that P(n) is true? Is that not cheating?' 'Why would I do that?'
By assuming P(k) we are saying the following:
Imagine that P(n) were true for some number k an element of N. If we could prove that P(k+1) were true - i.e. that P(n) is true for the number after k - and we could also prove that P(n) were true for the first in the series (e.g. 1), we would know that P(n) is true for all n!
It is not cheating. Here is the reasoning again:
Assume P(k) is true. Prove P(k+1) is true. If P(k+1) is true, no matter what natural number k is, P(n) is true for the next number. All that's needed now is to prove that P(n) is true for some natural number. Let's say P(4) is proved. That means P(n) is true for (4) and (4+1) and ( (4+1) + 1 ) and so on ad infinatum.
Hopefully the following will happen: Test the statement for the first number in the series ( P(1): 1 = 1^2 ). If this is true, assume P(k) is true. If we can prove that P(k+1) is true, the statement is true for all n (an element of N). P(k+1) is proved on the basis that P(k) is true, i.e. that P(n) is true for 'some number k an element of N'. Since we have proved that P(1) is true (1 is a number which is an element of N), the statement will be true for the next number: P(2). It will be true for the next number and the next number and so on and on. This has been informally named the 'domino effect'.
Assume P(k) is true:
P(k): 1 + 3 + 5 + 7 ... (2k - 1) = k^2
Stage 3
3. To Prove: P(k+1) is True.
TO PROVE P(k+1): 1 + 3 + 5 + 7 ... ( 2(k+1) - 1) = (k+1)^2
P(k+1) = 1 + 3 + 5 ... (2k + 2 - 1)
= 1 + 3 + 5 ... (2k + 1)
Now show the term preceeding (2k + 1). Following the patten, each term progresses by 2. The term is [(2k + 1) - 2] = 2k - 1
P(k+1) = 1 + 3 + 5 ... (2k - 1) + (2k + 1)
Look at this expression. We ought to recognise one part of it. From Stage 2 we assumed that P(k) = 1 + 3 ... (2k - 1) = k^2
P(k+1)= [1 + 3 + 5 ... (2k - 1)] + (2k + 1)
= P(k) + (2k + 1)
= k^2 + 2k + 1
Now factorise
= (k + 1)^2
So we have shown that P(k+1) = (k+1)^2
This is what we intended to prove.
Therefore, assuming P(k) is true, P(k+1) is true.
Now we can conclude
Conclusion
4. P(n) is true, for all n an element of N
Afterthoughts
There are other types of statement which can be proved by induction, such as Divisibility Proofs (proving an expression is divisible by some integer for all n), or Inequality Proofs (proving an inequality is true for all n). The example above is a sum of series - the easiest type of proof by induction.
Technically Proof by Induction is Proof after Induction. Induction is the opposite of Deduction. Loosely phrased, it is guessing. For instance, if I see 10 men walk past me in an hour, and 6 men have moustaches, all the men with moustaches wear black hats, and all the men with moustaches and black hats are wearing grey ties, I might hypothesise:
All men with moustaches wear grey ties.
or
All men with moustaches and grey ties wear black hats.
or
All men wearing black hats have moustaches.
I have seen a pattern and I am proposing a hypothesis, expressing what I've seen. Although this hypothesis is true for the set of 10 men who walked past me that hour, it might not be true for all men. I might see a man, the next hour, with a moustache, a black hat, and a green tie. Another man wears a black hat and a grey tie but has no moustache. My hypothesis is wrong. Inductive reasoning is prone to such fallacy.
Deductive reasoning is much more sound. A deductive argument is presented in the form of:
Premise 1
Premise 2
...
Premise 'n'
Conclusion
On condition that the premises are true and following from each other, the conclusion is always true.
For example:
All men have moustaches
Men who have moustaches wear black hats
Men who wear black hats wear black shoes
Therefore, All men wear black shoes.
In this case, if the first premise is true, the conclusion is true.
Inductive reasoning is the reasoning we are using when we rely on 'past experience'.
It worked for me before!
However, that might not be a universal law. Superstitious bowlers/baseball players/golfers commonly use such spurious reasoning.
Last time I crossed my ring and little finger and tapped my right foot twice, I got a strike!
This 'hypothesis' could be 'proven' true 20 times by inspection, but, most likely, it will eventually be contradicted.
Also, such inductive reasoning is commonly employed by racists:
(direct quote) Once I asked a black guy for a lighter and he wouldn't give me one. Black people are pricks.
You can't prove that after induction.
FMaths 19:01, 19 March 2011 (UTC)
