Mathematical Induction-I

Author

Abhirup Moitra

Published

July 26, 2023

It is a capital mistake to theorize before you have all the evidence. It biases the judgment. ~ Sherlock Holmes (A Study in Scarlet)

The induction principle is the domino effect in mathematics! The domino effect is the chain reaction consisting of a row of falling dominoes. The dominoes are vertical and close enough to one another. One pushes the first domino of the row, and this falls onto the second domino, which falls onto the third domino, and so on. In the end, the whole row has fallen!

Inductive and Deductive Reasoning

Experiment

Let us experiment. Considered a basket full of mangoes. You want to check whether they are raw or ripe. One can find out by observing the mangoes individually. So, we pick up the mango from the basket and observe it. Let’s say it is raw. Then we pick up another mango and observe it and find that is raw as well. Based on these many of us would conclude all the mangoes in the basket are raw.

What exactly are we doing here?

Conclusion

So, we examine a couple of mangoes in the basket and accordingly arrived at a general conclusion. The conclusion i.e., we generalized the idea by saying all the mangoes in the basket are raw. By observing a specific outcome of the experiment we concluded the observation in a generalized form. This approach of reasoning from specific to general is called Inductive Reasoning.

Inductive Reasoning

Inductive reasoning is a method of logical thinking that combines observations with experiential information to conclude. When you use a specific set of data or existing knowledge from past experiences to make decisions, you’re using inductive reasoning.

Note:

  • Inductive reasoning is logically true.

  • Inductive reasoning may or may not be realistically true.

What does it mean? Let us consider an example.

Example

  • Statement 1: Mango is a fruit (Specific Statement)

  • Statement 2: The box is full of fruits (Specific Statement)

We try to conclude from the above two statements.

Conclusion: The box is full of Mangoes. (General Conclusion)

Here statement 1 and statement 2 are logically true. But the conclusion drawn although logically true may be false if the basket contains any other fruits apart from mangoes. So, it’s logically true but not definitely true. So, this is inductive reasoning.

Deductive Reasoning

On the other hand, we have Deductive reasoning which relies on making logical premises and basing a conclusion around those premises. It does not rely on making inferences, then assuming those inferences to be true. Deductive reasoning is a logical approach where you progress from general ideas to specific conclusions.

Notes

  • Deductive reasoning is logically true.

  • Deductive reasoning is realistically true.

So, a perfect example will lead you to a better understanding and a better grasp of this concept.

Example

  • Statement 1: All mangoes are fruits. (General Statement)

  • Statement 2: All fruits have seeds. (Specific Statement)

  • Conclusion: Mangoes have seeds (Specific Conclusion)

From here we can comment i.e., statement 1 and statement 2 are logically true. Hence, it’s obvious that these two facts are realistically true.

Inductive reasoning is frequently used in mathematics. Observing the pattern that exists in a particular case we induce a general conclusion from that outcome. The conclusion we arrived at based on inductive reasoning is called conjecture.

Conjecture

A conjecture is a hypothesis that hasn’t been proven. Just because we observe a pattern in many cases, doesn’t mean it holds true for all cases. The conjecture must be proved for that particular case. To prove such a conjecture ‘The Principle of Mathematical Induction’ is used.

Here we will use induction to prove that a conjecture is true. Let us consider the following expression \(2+4+6+\ldots+2n=n(n+1).\) This expression is a sum of the first \(n\) positive even integers where \(n\) can be any natural numbers. Based on that expression we come up with the following formula \(2+4+6+\ldots+2n=n(n+1).\)

How did we come up with this formula how do we know it’s applicable for any natural number \(n\)

We can not check the reliability of the formula for all the terms of the expression one by one as it would be very time-consuming in order to check the validity of the formula for each term we need a domino effect showing that if the formula is true for one integer then it will also be true for the next and so on.

What do we mean by the domino effect?

Mathematical Induction And Domino Effect

Suppose you queue several dominoes one after the other how would you position each of these dominoes to ensure that all of them fall when you hit the first domino? Logically we know to achieve our goal but how do we write it mathematically? The best way to achieve your goal i.e.,

  • When the first domino falls, it will hit the second one.

  • Each domino will hit the next one and each domino that is hit will fall.

when these two conditions are satisfied no matter how many dominoes be a queue all of them will always fall. Similarly in mathematics to prove the formula true, it has to fill two conditions i.e.,

  1. Base case: One has to push the first domino, this means that we need to prove the first case.

  2. Induction step: One falling domino pushes the next because the dominoes are close together. We have to prove that from one case we can deduce the next one.

The dominoes are the cases of the proof. ‘A domino has fallen’ means that the case has been proven. When all dominoes have fallen, the proof is complete. In mathematics, we can also consider infinitely many dominoes.

Let \(P_n\) be a property that depends on a natural number \(n.\) For example, \(P_n\) could be a tile number \(n\) falls. The steps of approval are the following,

\(P_n: \text{Tile number}\;n\; \text{falls}\)

a) Check \(P_{0}\) is true. (In other words that the first tile falls) \(\implies \text{Base case}\)

b) For any \(n \in \mathbb{N}\; ; n \ge 0\), assume \(P_n\) is true and prove that \(P_{n+1}\) is also true. \(\implies \text{Induction step}\)

If a tile falls it pushes the next i.e., after completing the above two steps we can conclude \(P_n\) is true \(\forall n \in \mathbb{N}.\)

Let’s understand The Principle of Mathematical Induction solving some problems.

Example 1

Use mathematical induction and prove that \(\displaystyle P(n): 2+4+6+\ldots+2n=n(n+1)\) is true \(\forall n \in \mathbb{N}.\)

Condition1: Base Case

\(P(1)\) is true for \(n=1\) i.e., \(n=1 \rightarrow \text{First term}\)

\(P(1)_{\text{L.H.S}}=2\) and \(P(1)_{\text{R.H.S}}=2\) \(\; \therefore \text{L.H.S=R.H.S}\; \text{(Proved)}\)

Condition2: Inductive Case

If \(P(n)\) is true for \(n=k\) then \(P(n)\) also true for \(n=k+1\) i.e.,

Let us assume , if \(n=k\) then \(\displaystyle P(k): 2+4+6+\ldots+2k=k(k+1)\)

\(P(k+1)_{\text{L.H.S}} = 2+4+6+\ldots+2k2(k+1) = k(k+1)+ 2(k+1)= (k+1)(k+2)\)

\(P(k+1)_{\text{R.H.S}}=k(k+1)=(k+1)[(k+1)+1] = (k+1)(k+2)\)

Hence, \(\boxed{P(k+1)_{\text{L.H.S}} = P(k+1)_{\text{R.H.S}}}\)

\(\displaystyle P(n): 2+4+6+\ldots+2n=n(n+1)\) is always true \(\forall n \in \mathbb{N}.\) (Proved)

Problem set1

  1. Prove using mathematical induction that for all \(n \ge 1,\)

  • \(\displaystyle P(n): 1 + 4 + 7 + · · · + (3n − 2)= \frac{n(3n-1)}{2}\)

  • \(P(n): 1 + 3 + 5 + … + (2n – 1) = n^2\)

  1. Using mathematical induction show that,

\(\displaystyle P(n):\Biggl( 1-\frac{1}{2^2} \Biggl).\Biggl( 1-\frac{1}{3^2} \Biggl)\ldots \Biggl( 1-\frac{1}{n^2} \Biggl)= \frac{n+1}{2n}\; \forall n \in\mathbb{N} , n\ge 2\)

Show that

  • \(\displaystyle P(n) : \frac{1}{2.5}+ \frac{1}{2.8}+\frac{1}{8.11}+\ldots+ \frac{1}{(3n-1)(3n+2)} = \dfrac{n}{2(3n+2)}\; \forall n \in \mathbb{N}.\)

  • \(\displaystyle P(n): 1^6-2^6+3^6-\ldots+(-1)^{n-1}n^6 = \frac{(-1)^{n-1}}{2}(n^6+3n^5-5n^3+3n)\)

  • \(\displaystyle P(n): \tan^{-1}\bigg(\frac{1}{3}\bigg)+\tan^{-1}\bigg(\frac{1}{7}\bigg)+\ldots+ \tan^{-1}\bigg(\frac{1}{1+n+n^2}\bigg)=\tan^{-1}\bigg(\frac{n}{n+2}\bigg)\)

Example 2

\(P(n): \frac{1}{\log_{x}{2} \log_{x}{4}} + \frac{1}{\log_{x}{4} \log_{x}{8}} +\ldots+\frac{1}{\log_{x}{2^{n-1}} \log_{x}{2^n}}= \big(1-\frac{1}{n}\big) \frac{1}{(\log_{x}{2})^2} \; x>0\; x \not = 0 \; \forall n\in \mathbb{Z}\)

\(\implies P(n): \frac{1}{\log_{x}{2} \log_{x}{2^2}}+ \frac{1}{\log_{x}{2^2} \log_{x}{2^3}}+ \ldots+ \frac{1}{\log_{x}{2^{n-1}} \log_{x}{2^n}}= \big(1-\frac{1}{n}\big) \frac{1}{(\log_{x}{2})^2}\)

Now,

Base Case

\(n=1, \text{then}\; P(1)_{\text{L.H.S}} = 0\; \text{and}\; P(1)_{\text{R.H.S}} = 0 \; \therefore P(1)\ \text{is true}\; \forall n \in \mathbb{Z}.\)

Inductive Case

Let us assume that \(m > 1 ; \forall m \in \mathbb{Z}\; P(m)\; \text{is true.}\)

\(\therefore\) \(P(m): \frac{1}{\log_{x}{2} \log_{x}{4}} + \frac{1}{\log_{x}{4} \log_{x}{8}} +\ldots+\frac{1}{\log_{x}{2^{m-1}} \log_{x}{2^m}}= \big(1-\frac{1}{m}\big) \frac{1}{(\log_{x}{2})^2}\;\;\; \ldots \ldots (1)\)

Now we have to prove for \(P(m+1)\; \text{this is true.}\)

\(P(m+1)_{\text{L.H.S}}= \frac{1}{\log_{x}{2} \log_{x}{4}} + \frac{1}{\log_{x}{4} \log_{x}{8}} +\ldots+\frac{1}{\log_{x}{2^{m-1}} \log_{x}{2^m}}+\frac{1}{\log_{x}{2^{m}} \log_{x}{2^n}}\)

\(\hspace{2.55 cm}= \big(1-\frac{1}{m}\big)\frac{1}{(\log_{x}{2})^2}+ \frac{1}{\log_{x}{2^{m}} \log_{x}{2^n}}\)

\(\hspace{2.55 cm} = \frac{1}{(\log_{x}{2})^2} \Big[\big(1-\frac{1}{m}\big)+ \frac{1}{m(m+1)}\Big]\)

\(\hspace{2.55 cm}=\big(1-\frac{1}{m+1}\big) \frac{1}{(\log_{x}{2})^2}\)

\(P(m+1)_{\text{R.H.S}} = \big(1-\frac{1}{m+1}\big) \frac{1}{(\log_{x}{2})^2}\)

\(P(m+1)_{\text{L.H.S}} = P(m+1)_{\text{R.H.S}}\).

As, \(P(m)\) is true, therefore \(P(m+1)\) is also true.

\(P(n): \frac{1}{\log_{x}{2} \log_{x}{4}} + \frac{1}{\log_{x}{4} \log_{x}{8}} +\ldots+\frac{1}{\log_{x}{2^{n-1}} \log_{x}{2^n}}= \big(1-\frac{1}{n}\big) \frac{1}{(\log_{x}{2})^2} \; x>0\; x \not = 0 \; \forall n\in \mathbb{Z}\) is true (Proved)

Conclusion

The Induction Principle is of great importance in all of the fields of mathematics. This content is all about those inquisitive students who are trying to understand the basic & fundamental concepts of higher mathematics but are unable to grasp the insight behind induction principle. Here, I have tried to deliver a coherent understanding and a phylosophical overview of Principle of Mathematical Induction.

In a single content, it is not possible to cover all the necessary problem-solving strategies which is also required further. That’s why I’m willing to discuss lots more problems and problem-solving strategies on mathematical induction in my upcoming content which will be an asset to deal with critical problems from INMO, IMO, PUTNUM.

See Also