|Aug19-12, 02:20 AM||#1|
what is mathematical induction? explain with an example.
|Aug19-12, 04:43 AM||#2|
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.
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:
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:
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.
|Aug19-12, 05:22 PM||#3|
|Aug19-12, 11:56 PM||#4|
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
|Aug21-12, 09:04 AM||#5|
|Similar Threads for: mathematical induction|
|Mathematical Induction||Calculus & Beyond Homework||9|
|Difference between Strong Induction and Mathematical Induction?||Calculus & Beyond Homework||5|
|Mathematical Induction||Set Theory, Logic, Probability, Statistics||2|
|mathematical induction||Math & Science Software||24|