# Maths – Induction (part 1)

September 10, 2009 Leave a comment

[ ** A** = for all.

**= there exists ]**

*E*** **

## 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:
n Є N, n Є X => (n+1) Є N*A*

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:
n Є N, if*A**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 ** A**n Є 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

= 0Therefore, 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 ^{2}+3n+2**. Then fractionise this to get:

**(n+1)(n+2)**.