Mathematical Induction:It is a technique for proving a statement, a theorem, or a formula that is asserted about every natural number.
Before we take an example on mathematical induction I would also like to provide you a link on Mathematical reasoning.
Example of mathematical induction:
Mathematical induction is used to prove that the following statement holds for all natural numbers n.
Let us call the statement as P(n)
Show that the statement holds for n = 0.
P(0) amounts to the statement:
P(0) amounts to the statement:
On the left-hand side of the equation, 0 is the only term, and so the left-hand side is equal to 0.
On the right-hand side of the equation, 0·(0 + 1)/2 = 0.
The two sides are equal, so the statement is true for n = 0. So, it has been shown that P(0) holds.
On the right-hand side of the equation, 0·(0 + 1)/2 = 0.
The two sides are equal, so the statement is true for n = 0. So, it has been shown that P(0) holds.
Inductive step: Prove that if P(n) holds, then P(n + 1) also holds.
Imagine P(n) holds (for some unspecific value of n). It must be proved that P(n + 1) holds, i.e,
According to the induction hypothesis that P(n) holds, we can rewrite the left-hand side as follows:
Algebraically:
Hence P(n + 1) holds.
We have proved both the basis and the inductive step, therefore,it has been proved by mathematical induction that P(n) holds for all natural n
No comments:
Post a Comment