Mathematical Induction

Mathematical induction definition is a technique or method by which a statement, theorem, or formula is proved, which is believed to be true for every natural number N. Natural numbers are the non-zero numbers that are used for counting. We use the symbol N to denote the concept of natural numbers. Natural numbers are non-negative and contain no fractional numbers. By generalizing this, we can use it to prove mathematical statements is the ‘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.


One major limitation of mathematical Induction is that it is limited to items quantifiable in the set of numbers.


Understanding the Principle of Mathematical Induction

Proof by Induction will help you understand the meaning of mathematical induction. It consists of -

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


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


(image will be uploaded soon)


Application of Mathematical Induction in Real Life - ‘The Domino Effect.’ 

If you queue a thousand dominoes and want to let them all fall by allowing the first domino to fall, how would you queue it?


The best idea is to queue it such that:

  1. When the very first domino topples, it will lean against the second domino and make it fall.

  2. Ensure that each domino will hit the domino next to it and that each hit makes a domino fall.

  3. If conditions (1) and (2) are satisfied, then all the dominoes will fall, proving the principle of mathematical Induction.

(image will be uploaded soon)


Mathematical Induction Example 

Here is a mathematical induction question:


Problem 1: Family Tree 

Imagine that your great, great, … grandfather Jim had two children. Call this generation one, so that generation one contains 2 offsprings of Jim Each of these children has two children, so generation two will have 4 offsprings. Each of the four offspring has 2 children, so, at 3rd generation, we have eight offspring. If this sequence continues generation after generation, prove that at n generation, there will be 2n offsprings?


Solution:Base Case: P(1) asserts that generation 1 has 21 offspring, which is true since we are told that Jim had two children.


Inductive Step: We assume for an arbitrary integer, say k, P(k) is true. That means, that generation k has 2k offspring. We have to show that k + 1 generation has 2k + 1 offspring.

Generation k + 1 has 2 x 2k offsprings [Generation k has 2k assumed to be true]

Generation k + 1 has 21 x 2k offsprings

Generation k + 1 has 2k + 1 offsprings

Thus, P(k + 1) is true because P(k) is also true. 

Hence P(n) is true for all natural numbers.

FAQ (Frequently Asked Questions)

1) Can mathematical induction be validated in a real-life scenario?

Prove: John is dead on each and every day after October 5, 2000. John died on October 5, 2000. Assume infinite days. Assume once John is dead, he cannot be brought back to life.


  • John died on 5th October, 2000. Hence, he is dead on 5th October, 2000.

  • This is the base case. We proved the statement (that John is dead) for the base case.

  • If John is dead on the day “D”, then John must be dead on the next day, which can be called “D+1”.

  • This step shows that P(n), that is the statement of n, implies P(n+1), i.e. “If it is true now, then it is true tomorrow. It does not matter when ‘now’ is.”

  • We have shown that. I hope it’s obvious why.

Thus, if John is dead on 5th October, 2000, he must be dead on 6th October, 2000, which implies he must be dead on 7th October, 2000, and so on.


Therefore, John is dead on each and every day after 5th October, 2000, which can be expressed as day “D+n”, where “D” is 5th October, 2000, and “n” is the number of days after 5th October, 2000.

QED.


The key here is to provide an implication. If the statement is true for n, it implies truth n+1. If it is true for one step, it is true for the next, and so on.


Since the base statement is true, it is true for every case after the base, as long as P(n) implies P(n+1).