Maths - Induction (part 1)

[ A = for all.    E = there exists ]

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

ⁱ⁼⁰






Now that we have this, we need to split up the formula:

_n

L(n) =    ∑ i                            and                        R(n) =    ( (n(n+1) ) / 2

ⁱ⁼⁰

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: n²+3n+2. Then fractionise this to get: (n+1)(n+2).