MATHEMATICAL INDUCTION 1/1

1. THE METHOD OF MATHEMATICAL INDUCTION

Mathematical induction is a method of proving formulas and theorems by using the natural numbers (positive integers). Many of the statements typically proven by this technique are actually formulas or theorems about the positive integers. This 3-step procedure is generally easy to follow.

The three steps are:

1. Prove that the proposition is true for a particular positive integer n (typically n=1).
2. Show that, if the proposition is true for some positive integern=k, then it can be shown to be true for n=k+1. This is usually done as follows:
2.1. Assume the proposition is true for k (n = k). This is referred to as “the induction hypothesis.”
2.2. State that the proposition is true for the value k+1 (n=k+1).
2.3. Prove the truth of the proposition for the value k+1 (n=k+1).
3. Conclude that the proposition is true for all positive integers.

2. USAGE OF MATHEMATICAL INDUCTION

When doing exercises using mathematical induction, students may question the importance of such tasks. Even though the problems generally focus on verifying the already-established truth of a statement (as opposed to a “prove or disprove” approach), this is a technique that is used to prove such an important result as the Binomial Theorem. This fact alone should require that students understand the method of mathematical induction! (And what better way to understand it than to practice it?!)

As an example, let's prove that: 2n >n.
1 First we must show that the preposition is true for n=1: 21 >1 
2 Next we assume that the proposition is true for n=k. That is, we assume 2k >k
  We must now show that they proposition is true for n=k+1. That is, we must show that
2(k+1) >k+1 .
  We have 2(k+1) = 2k*2 = 2k+2k  > k+2k > k+1
This shows that 2(k+1) >k+1.
3 Thus, the proposition is true for n=k+1 and so by mathematical induction, we may conclude that 2n >n for all positive integers n.

For another example, let us prove that 1+3+5+…+(2n-1) = n2.

1 First we must show that the preposition is true for n=1: 2*1-1 = 12 
2 Secondly, we assume the proposition is true for n=k. That is 1+3+5+…+(2k-1) = k2
  Now we must show that the statement is true for n=k+1
 That is,
1+3+5+…+(2k-1) + [2(k + 1) –1] = (k+1)2

Now,
[1+3+5+…+(2k-1)] + [2(k+1)-1]=
=k2 + 2k+2-1
=k2+2k+1
=(k+1)2
That is
1+3+5…+[2(k+1)-1] = (k+1)2
3 Thus, the proposition is true for n=k+1 , and so by mathematical induction, 1+3+5+…+2n-1 = n2 for all positive integers n .


Now try to prove this:
for n>4