Principle of Mathematical Induction

Mathematical Induction is a technique of proving a statement, theorem, or formula which is thought to be true, for every natural number N.

(Natural numbers are the non-zero numbers that are used for counting. They start at 1 and go upward infinitely. We use the symbol N to denote them. Natural numbers are non-negative and contain no fractional numbers. Zero is not considered as a natural number.)

By generalizing this in the form of a principle which we can use to prove any mathematical statement is ‘Principle of Mathematical Induction‘. 


For example: the statement 13 +23 + 33 + ….. +n3 = \[(\frac{n(n+1)}{2})2\] is considered true for all the values of natural numbers.


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).

FAQ (Frequently Asked Questions)

1) What is Proof by Induction?

One way of looking into mathematical induction is to prove not the one proposition, but a whole sequence of proposition, one for each n.


To apply mathematical induction, prove the first statement in the sequence, and then prove that if any particular statement is true, then the one after it is also true. This enables us to conclude that all the statements are true.


Induction Basis Other Than 0 or 1

If one wishes to prove a statement not for all natural numbers, but only for all numbers n greater than or equal to a certain number b, then the proof by induction consists of:

  1. Showing that the statement holds when n=b

  2. Showing that if the statement holds for an arbitrary number then the same statement also holds for n+1

2) Give 2 Practical Examples of Mathematical Induction?

Mathematical thinking is essential, as it helps in a better understanding of problems thus letting us reach solutions in a better way. Both mathematical thinking and deductive reasoning go hand in hand. Deductive thinking forms the grounds for the latter. Further, deductive reasoning further is based on logic and understanding.
For example:

  1. The German shepherd is a dog.

  2. All dogs have an immaculate sense of hearing.

  3. The German shepherd has an immaculate sense of hearing.

Now, if statements a) and b) are true then c) is also true. This theory of reasoning can be used mathematically as well, let’s see how?

  1. Sixteen is divisible by Two.

  2. Any number divisible by two is an even number.

  3. Sixteen is an even number.

From the above example, we get a hint of deduction.