Wednesday 30 March 2011

Mathematical Induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (non-negative integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.
- Stolen from http://en.wikipedia.org/wiki/Mathematical_induction

In my own words. Mathematical Induction is the concept of having a ladder that goes on to infinite. If you know that you can reach the first rung. Then odds are you are able to reach the next rung. If you can reach the "n-th rung", then you can touch the "n+1-th rung". 

I will show how this can prove various equations to show that they are true for all values of your variable.

Ex.

We will prove by Mathematical Induction that the equation 

1+2+...+n = [n(n+1)]/2   is true for all n > 0.

So to start. Let p(n) be the propostion => 1+2+...+n=[n(n+1)]/2

Our objective is to show that p(1) is true(the first value that n can be), and that the conditional statement p(k) implies p(k+1) also denoted as p(k) -> p(k+1), is true for all k > 0.

So we first need to show that the proposition p(n) is true for the very first value of n. In this case 1.
This step is called the Basis step. 

Basis Step: verifying that p(1) is true. As seen by inspection p(1) is true for

1 = [1(1+1)]/2 = 1(2)/2 = 2/2 = 1

Since the basis step is true we move onto the next step called the Inductive step. This is where all the nitty gritty algebra comes into play.

Inductive step: In this step, we assume that p(k) holds for an arbitrary positive integer k. That is we assume that 

1+2+...+k = k(k+1)/2

under this assumption, it must be shown that p(k+1) is true.

To show that p(k+1) is true we first must find what p(k+1) is. 

p(k+1) => 1+2+...+(k+1) = ((k+1)[(k+1)+1]) / 2 = [(k+1)(k+2) ]/2

(k+1)(k+2) / 2 is the equation that we will need to show for our next step . The next step we call the Inductive Hypothesis.

Inductive Hypothesis: This was the hypothesis that if any value of n is true then n+1 must also be true. To show this we write the proposition p(k) as the following.

1+2+...+k+(k+1) = k(k+1)/2 + (k+1)             (we added (k+1) to both sides of this equation)
                                                                     
The idea in this step is to show that the left side can equal the same answer we determined in the Inductive step. 

So as the following working with the left side of the equation.

=   k(k+1)/2  + (k+1) 
=  [  k(k+1) + 2(k+1) ] / 2   (By adding the fractions, the 2 came from the base difference of 1 and 2)


=  [k^2 + k + 2k + 2 ] / 2  (Textbook feels it's unnecessary to skip this step, i find it confusing without)


= [ k^2 + 3k +2 ] / 2 ( By factoring we get)

= [ (k+1)(k+2) ] / 2  (which hopefully looks familiar)

The answer is the same as the Inductive step. Thus proving the hypothesis correct.

So by Mathematical Induction we know that p(n) is true for all positive integers n. That is we have proven that

1+2+...+n = [ n(n+1) ] / 2   for all n>0.   

8 comments:

  1. i like to read these and see how far i can get before i cant understand anymore.

    ReplyDelete
  2. ^thats exactly what i do. CHALLENGE ACCEPTED

    ReplyDelete
  3. this post wouldve been a 10/10 if the only words in it were "Mathematical induction is gay"

    ReplyDelete
  4. I'm your 100th follower!!!! thanks for the info on induction too!

    ReplyDelete