The Principles of Induction
Firstly, welcome to Induction. The one thing in Discrete Maths that I hear a heck of a lot of people complaining about! – So don’t worry, you’re not the only one :)
Here I shall attempt – attempt being the key word – to make induction make a lot more sense to you.
OK, so let’s say we have a set, ‘X’ of natural numbers:
- X = {1, 2, 3, 4…}
The first thing we need to understand about induction is that we have 2 cases.
- First there is the ‘base’ case which is the lowest value of say ‘n’ possible, that makes a given equation true – usually 0.
- Secondly we have the ‘step’ case. This states that if the equation is true for ‘n’, then theoretically it must be true for ‘n+1’.
We can show this relation with set theory, so:
- Base case: 0 Є X
- Step case: An Є N, n Є X => (n+1) Є N
Let’s say that we have the some function P(n). The base and step cases for this function would be:
- Base: P(0) = true
- Step: An Є N, if P(n)=true then so must P(n+1)
Induction
Let’s now have a proper example on how we do induction. Say for example you have the following summation – and you are given the answer:
n
∑ i = ( n(n+1) ) / 2
i=0
Now that we have this, we need to split up the formula:
n
L(n) = ∑ i and R(n) = ( (n(n+1) ) / 2
i=0
For this, we need to say that An Є N, then L(n)=R(n).
For this summation, the Base case is clearly 0. so is it true that L(0)=R(0)? Let’s find out:
- When i=0 in ∑ i, then it is quite obvious that ∑ i=0. Therefore L(0)=0
- In the case if R(0), we have: = ( (n(n+1)) / 2
= ( (0(0+1)) / 2
= (0(1)) / 2
= 0 / 2
= 0
Therefore, R(0)=0 as well. So: - L(0) = R(0) is true. And therefore the Base case is true.
Now we need to move onto the Step case part. This part is a little trickier to explain, so you’ll have to bear with me on this…
We know that L(n)=R(n), however, we need to prove that L(n+1)=R(n+1).
A quick way to do this, is that when we state L(n+1), change all the ‘i’ next to the ‘∑’ to ‘n+1’. So in this case we have: (better example later)
- ∑ i = ∑ (n+1)
Once this is done, we then need to move everything next to the ‘∑’ onto the right hand side. So we get this:
- before we move we have:
R(n) = (n(n+1)) / 2 - Once the ‘i’ has be moved over, then R(n) becomes R(n+1), and we have:
R(n+1) = [(n(n+1)) / 2] + (n+1)
Once we have this, it is just simple arithmetic:
(1) = [(n(n+1)) / 2] + (n+1)
(2) = [(n(n+1)) / 2] + [2(n+1) / 2] make both have same denominator.
(3) = (n(n+1) + 2(n+1)) / 2 bring both together
(4) = ((n+1)(n+2)) / 2 This step will be explained further in the sec
(5) = R(n+1) this step requires some common sense really. Go back to R(n), then sub in (n+1) into all n, from (n(n+1)) / 2. What do you get?
Exactly :) , you should hopefully end up with ((n+1)(n+2)) / 2. if not, here:
(n(n+1)) / 2
( (n+1) ((n+1)+1) ) / 2
((n+1)(n+2)) / 2
OK then, so, step (4). For this step, you need to expand the brackets. Once that is do you should have: n2+3n+2. Then fractionise this to get: (n+1)(n+2).
No comments:
Post a Comment