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)
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:
When the very first domino topples, it will lean against the second domino and make it fall.
Ensure that each domino will hit the domino next to it and that each hit makes a domino fall.
If conditions (1) and (2) are satisfied, then all the dominoes will fall, proving the principle of mathematical Induction.
(image will be uploaded soon)
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.
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.
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).
Share your contact information
Vedantu academic counsellor will be calling you shortly for your Online Counselling session.