# Mathematical induction

1. Aug 19, 2012

### akshayacse

what is mathematical induction? explain with an example.

2. Aug 19, 2012

### PhysicoRaj

Mathematical Induction is a concept used to prove a given statement to be true for all positive integers. It is generally described with an example of effect of sequential falling of plates arranged parallel, up to a long distance. If one falls over the next, the whole sequence undergoes the same effect.
Theoretically it is done in three main steps:
1) Proving the statement to be true for the value 1
and hence showing the either sides of equation to be equal.
2) Proving for (k+1) value and implying on k-->(k+1)
3) Showing that the implication and the true value concludes the statement to be true for all n belonging to natural numbers.
An example:
Mathematical induction can be used to prove that the following statement, which we will call P(n), holds for all natural numbers n.
1+2+3+..........+n = n(n+1)/2
P(n) gives a formula for the sum of the natural numbers less than or equal to number n. The proof that P(n) is true for each natural number n proceeds as follows.
Show that the statement holds for n = 1.
P(1) amounts to the statement:
1=1.(1+1)/2
In the left-hand side of the equation, the only term is 1, and so the left-hand side is simply equal to 1.
In the right-hand side of the equation, 1·(1 + 1)/2 = 1.
The two sides are equal, so the statement is true for n = 1. Thus it has been shown that P(1) holds.
Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:
1+2+...........+k+(k+1) = (k+1)[(k+1)+1]/2

Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:
[k(k+1)/]+(k+1)

Algebraically it is equal to (k+1)[(k+1)+1]/2
thereby showing that indeed P(k + 1) holds.

Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that P(n) holds for all natural n.

Last edited: Aug 19, 2012
3. Aug 19, 2012

### student34

Why do we have to turn k into n? Why can't we just use k the whole time since that is what we use in the original question?

4. Aug 19, 2012

### Bacle2

Well, it is a purely technical issue: the property holds for the natural number 1

(tho this is not always necessary), and we denote that it is satisfied by the natural

number n=k, and we want this last to imply that the property holds also for the

proposition P(k+1), which is indexed by the natural number n=k+1.

Look up too, the well-ordering principle , which is equivalent to induction

--we use the fact that in standard induction, the propositions are indexed by the

natural numbers with their standard ordering. You may also want to look up

transfinite induction , which generalizes standard induction to well-ordered sets

5. Aug 21, 2012

### PhysicoRaj

P(n) is the general form. The proof is given to show both for values of 1 (sometimes it is also proved for 0) and any other natural number k and k+1, the statement holds true, which for the sake of convenience you can do with n+1 and n.