State Principle of Mathematical Induction, Solution and Principle of Mathematical Induction Proof

A proof by induction consists of –

1) The base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. 

2) The second case, the inductive step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1.

These establish that the statement holds for every natural number n.

Let’s consider a statement P(n), where n is a natural number. Then to determine the validity of P(n) for every n, we can use the following principle:

Step 1:  Check whether the given statement is true for n = 1.[Base Case]

Step 2: Assume that the given statement P(n) is also true for n = k, where k is any positive integer. [Inductive hypothesis]

Step 3:  Prove that the result is true for P(k+1) for any positive integer k.[Induction step]

If the above-mentioned conditions are satisfied, then it can be concluded that P(n) is true for all n natural numbers. Thus, this is the mathematical induction formula approach.  

 

Properties of Mathematical Induction

Property a) mentioned above is simply a statement of a fact. In these situations, where the statement is true for all the cases (assuming n≥5), then the step a) shall start from n=5 and we shall hence verify the result for n=5, i.e., P(5).

 

Property b) shows a conditional property (conditional property is the occurrence of an event B in relationship to an event A given that event A has already occurred.) as it does not confirm that the given statement is true for n=k, but if it is true for n=k then it should also be true for n=k+1.

 

Theorem

For any n ∈ N,

\[\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\]

 

Proof

Base case n = 1 : If n = 1, the left side is 1 and the right side is \[\frac{1(2)}{2} = 1\].

 

So, the theorem holds when n = 1.

 

Inductive hypothesis : Suppose the theorem holds for all values of n upto some k, k ≥ 1.

 

Inductive step : Let n = k + 1. Then our left side is

 

\[\sum_{i=1}^{k+1} i = (k+1) + \sum_{i=1}^{k} i\]

 

= \[(k+1) + \frac{k(k+1)}{2}\], by our inductive hypothesis

 

= \[\frac{2(k+1)}{2} + \frac{k(k+1)}{2}\]

 

= \[\frac{2(k+1) + k(k+1)}{2}\]

 

= \[\frac{(k+1)(k+2)}{2}\]

 

which is our right side. So, the theorem holds for n = k + 1. By the principle of mathematical induction, the theorem holds for all n ∈ N.

 

Principle of Mathematical Induction Examples

Here are two mathematical induction problems inter 1st year.

 

Prove the Following using Principle of Mathematical induction

1. Prove that for any positive integer number n, n 3 + 2n will be divisible by 3

2. Prove that: 13 + 23 + 33 + … + n 3 = n 2 (n + 1) 2 / 4 for all positive integers n.

 

Solution to Problem 1:

Let Statement P (n) be defined in the form n 3 + 2n is divisible by 3
Step 1: Basic Step

We first show that p (1) is true. Let n = 1 and formulate n 3 + 2n

1 3 + 2(1) = 3

3 is divisible by 3 hence p (1) is true.

Step 2: Inductive Hypothesis

We now assume that p (k) is true

k 3 + 2k will be divisible by 3 and will be equivalent to

k 3 + 2 k = 3 B , where B is a positive integer.

Step 3: Inductive Steps

We now consider the algebraic expression (k + 1) 3 + 2 (k + 1); expand it and group like terms

(k + 1) 3 + 2(k + 1) = k 3 + 3 k 2 + 5 k + 3

= [ k 3 + 2 k] + [3 k 2 + 3 k + 3]

= 3 B+ 3 [ k 2 + k + 1 ] = 3 [ B + k 2 + k + 1 ]
Therefore, (k + 1) 3 + 2 (k + 1) will also be divisible by 3 and hence, statement P(k + 1) is true.

Solution to Problem 2:

Statement P (n) is defined by

1 3 + 2 3 + 3 3 + … + n 3 = n 2 (n + 1) 2 / 4 

Step 1: Basic Step

We first show that p (1) is true.

Left Side = 1 3 = 1

Right Side = 1 2 (1 + 1) 2 / 4 = 1 hence p (1) is true.

Step 2: Inductive Hypothesis

We now assume that p (k) is true

1 3 + 2 3 + 3 3 + … + k 3 = k 2 (k + 1) 2 / 4

Step 3: Inductive Steps

add (k + 1) 3 to both sides

1 3 + 2 3 + 3 3 + … + k 3 + (k + 1) 3 = k 2 (k + 1) 2 / 4 + (k + 1) 3

factor (k + 1) 2 on the right side

= (k + 1) 2 [ k 2 / 4 + (k + 1) ] set to common denominator and group

= (k + 1) 2 [ k 2 + 4 k + 4 ] / 4

= (k + 1) 2 [ (k + 2) 2 ] / 4
We started from statement P(k) and can show:

1 3 + 2 3 + 3 3 + … + k 3 + (k + 1) 3 = (k + 1) 2 [ (k + 2) 2 ] / 4
Which is the statement P(k + 1).