Mathematical induction

Let us consider the sum of the first n positive odd numbers. These are , , , , · · · , n − . The first odd number which is equal to . The first two odd numbers are and and their sum is .

Writing these as follows helps us to see a pattern. = + = + + = + + + = + + + + = Combinatorics and Mathematical Induction and so on. We note that the right hand side of the expressions are the perfect squares , , , , · · · . This pattern compels us to make the conjecture that the sum of the first n odd numbers is equal to n .

Symbolically, we express this as, + + + · · · + ( n − ) = n . However we have only made a conjecture. In order to prove the conjecture we shall use the Principle of Mathematical Induction. Mathematical Induction is a method or technique of proving mathematical results or theorems of the above kind.

This technique relies upon making conjectures by observing all possible cases of a specific result. It is well suited for proving results in algebra or in other disciplines of mathematics where results or theorems are stated in terms of n , n being a positive integer. The process of Mathematical Induction may be compared to that of climbing an infinite staircase. In order to ensure that we complete the climb, it is sufficient to ensure the following.

(a) We can climb the first step. (b) Once we have reached a particular step of the staircase, we can climb to the next step. Being sure of (a) and (b) will enable us to climb all the steps in the staircase. Similarly, when we apply this method to prove a mathematical statement P ( n ) , the process of induction involves the following steps.

Figure . Step : Verify that the statement is true for n = , that is, verify that P( ) is true. This is akin to climbing the first step of the staircase and is referred to as the initial step . Step : Verify that the statement is true for n = k + whenever it is true for n = k , where k is a positive integer.

This means that we need to prove that P ( k + ) is true whenever P ( k ) is true. This is referred to as the inductive step . Step : If steps and have been established then the statement P ( n ) is true for all positive integers n . One of the interesting method of proof in Mathematics is by the Mathematical induction.

We shall illustrate the method through problems. As an illustration of the process let us revisit a well known result through an example below: . Mathematical induction Example . By the principle of mathematical induction, prove that, for all integers n ≥ , + + + · · · + n = n ( n + ) .

Let, P ( n ) := + + + · · · + n = n ( n + ) . Substituting the value of n = , in the statement we get, P ( ) = ( + ) = .