Friday, February 15, 2013

Mathematical Induction


Mathematical Induction is a method used to prove a statement, theorem or even a formula that is about every natural numbers. And to prove that a formula or a rule is true for every natural number, we use a method of proof which is called the principle of Mathematical-Induction.
Proof by Mathematical Induction basically follows two steps, the basis step and the inductive step. To show that for all n, P(n) holds good the basis step would be to prove P(0) holds and in the Inductive step it is assumed that P(n) holds  and then prove that P(n+1) also holds.

Let us put this in simpler terms, when a statement to be proved is given Mathematical Induction Proof follows the following steps,
In step 1, to show it is true for n=1,n=2, n=3…
Here we are trying to show that it is true for some specific values of n. One point to remember here whatever number of values we try to show it is true, it is not necessary that it would be true for all values.
In step2, an assumption is made that it is true for n= k
In the previous step we have already shown that it is true for one or more values and hence to assume that it is true for a value ‘k’ is logical
In step3, using the above assumption to prove that it is true for n=k+1 and hence for n=1
In step 3, we prove that it is true for n=1 which proves that the statement is true for all values.

In this Mathematical Induction Tutorial let us consider an example for a better understanding:
To prove, 1+3+5+…. +(2n-1)=n^2
Step1: The given statement is true for n=k; so, 1+3+5+…+(2k-1)=k^2
Step2: Assuming the statement is true for n=k+1; to prove the assumption we add (2k+1) on the both
             Sides of the induction statement; 1+3+5+…+(2k-1)+(2k+1)=k^2+(2k+1)
              So, we get, 1+3+5+…+(2k-1)+(2k+1)=(k+1)^2
Step3: To complete the proof of mathematical induction we need to show that it is true for n=1
1=1^2, hence the given induction statement is true for all natural numbers

The Principle of Strong Mathematical Induction: For all integers n, let P(n) be a predicate and let ‘a’ and ‘b’ be two fixed integers given a<=b.
Basis step: If P(a), P(a+1)…P(b) are all true
Inductive step: For any integer k greater than b, if P(i) is true for all integers ‘i’ given by a<=iThen P(n) is true for all integers n >=a

No comments:

Post a Comment