Mathematical induction

[akshayacse]

Main Question or Discussion Point

what is mathematical induction? explain with an example.

 

[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.

 

[student34]

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.

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?

 

[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

 

[PhysicoRaj]

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?

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.