Tuesday, November 2, 2010

Mathematical Induction

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.
0 + 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\,
Let us call the statement as P(n)
Show that the statement holds for n = 0.
P(0) amounts to the statement:
0 = \frac{0\cdot(0 + 1)}{2}\,.
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.
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,
(0 + 1 + 2 + \cdots + n )+ (n+1) = \frac{(n+1)((n+1) + 1)}{2}
According to the induction hypothesis that P(n) holds, we can rewrite  the left-hand side as follows:
\frac{n(n + 1)}{2} + (n+1)\,.
Algebraically:
\begin{align}
\frac{n(n + 1)}{2} + (n+1) & = \frac {n(n+1)+2(n+1)} 2 \\
& = \frac{(n+1)(n+2)}{2} \\
& = \frac{(n+1)((n+1) + 1)}{2}.
\end{align}
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