JEE Important Chapter - Mathematical Induction

A methodology or approach for proving a statement, theorem, or formula that is thought to be true for any natural number N is known as mathematical induction. The non-zero numbers that are utilised for counting are known as natural numbers. The concept of natural numbers is represented by the letter N. Natural numbers are not negative and do not contain fractions. The 'Principle of Mathematical Induction' is a generalisation of this that may be used to prove mathematical statements.

For example, the assertion $1^3 + 2^3 + 3^3 + ..... +n^3 = \left(\dfrac{n(n + 1)}{2}\right)^{2}$ is valid for all natural number values.

Therefore, Mathematical Induction is a method for proving natural number conclusions or establishing claims.

JEE Main Maths Chapter-wise Solutions 2022-23 

Important Topics of Mathematical Induction

• Mathematical Induction

• Principle of Mathematical Induction

Important Concepts of Mathematical Induction

Principle of Mathematical Induction

Every non-negative integer belongs to the class F if integer 0 belongs to the class F and F is hereditary. If integer 1 is a member of the class F and F is hereditary, then every positive integer is a member of F.

The principle is also frequently expressed in the intensional form: A property of integers is said to be hereditary if any integer x has the property and so does its successor. If a property of the numeral 1 is hereditary, then every positive integer possesses that feature as well.

Principle of Mathematical Induction Solution and Proof - Mathematical Induction Steps

Consider P(n) is an example of a statement, where n is a natural number. Then apply the following approach to determine the validity of P(n) for each n:

Step 1: Verify that the given statement is correct when n = 1.

Step 2: Assume that the above assertion P(n) holds for n = k, with k being any positive integer.

Step 3: For any positive integer k, prove that the result is true for P(k+1).

If the preceding requirements are met, it can be argued that P(n) is true for all n natural integers.

Properties of Mathematical Induction

The properties that can be proven using the Mathematical Induction Principle are listed below.

1. $1+2+3+\ldots+n=\dfrac{n(n+1)}{2}, n \geq 1$

2. $1^{2}+2^{2}+3^{2}+\ldots+n^{2}=\dfrac{n(n+1)(2 n+1)}{6}, n \geq 1$

3. $1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\dfrac{n^{2}(n+1)^{2}}{4}, n \geq 1$

4. $1+3+5+\ldots+(2 n-1)=n^{2}, n \geq 1$

5. $2^{n} > n, n \geq 1$

Proof by Mathematical Induction

The concept begins with a factual statement and ends with a conditional assertion. According to this, if the given assertion is true only for some positive integer k, then the statement P(n) is valid for n = k + 1.

This is also known as the inductive step, and the inductive hypothesis is the assumption that P(n) is true for n=k.

Example:

The proof that the sum of the first n odd positive numbers equals $n^2$ that is,

$1 + 3 + 5 + \ldots + (2n - 1) = n^2$ …….. (1)

Let F denote the class of integers for which equation (1) holds; then integer 1 belongs to F because $1^2 = 1$. Now, If integer $x$ belongs to F then,

$1 + 3 + 5 + \ldots + (2x − 1) = x^2$ …….. (2)

After $2x - 1$, the next odd integer is $2x + 1$, which when added to both sides of equation (2) gives

$1 + 3 + 5 + \ldots + (2x + 1) = x^2 + 2x + 1 = (x + 1)^2$

Equation (2) is the hypothesis of induction and it states that equation (1) holds when n equals x, whereas equation (3) states that equation (1) holds when n equals x + 1. Since equation (3) follows from equation (2), it has been established that whenever x belongs to F, the successor of x also belongs to F. As a result of the mathematical induction principle, all positive integers belong to F.

Application of Mathematical Induction in Real Life

Mathematical induction can be compared to dominoes falling. When a domino falls, it causes the following domino to fall in turn. The first domino takes down the second, and the second falls down on the third, and so on. All of the dominoes will be knocked over in the end. However, there are several rules that must be followed:

1. To start the knocking process, the first domino must fall. This is the first and most important step.

2. Any two adjacent dominoes must have the same space between them. Otherwise, a domino could fall without knocking down the next. The chain of reactions will then come to an end.

3. Maintaining the same inter-domino distance ensures that $P(k) \Rightarrow P(k + 1) $ for each integer $k \geq a$. This is when the inductive process begins.

Example: Dominoes Falling

Examples Based on Mathematical Induction

Example 1: Let Statement P(n) be defined in the form $n^3 + 2n$. Prove that it is divisible by 3.

Solution: Step 1 − Basic step

We first show that P(1) is true by substituting $n = 1$ in $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 + 2k = 3B$ , where B is a positive integer.

Step 3 − Inductive Steps

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

$(k + 1)^3 + 2(k + 1) = k^3 + 3k^2 + 3k + 1 + 2k + 2$

$\Rightarrow k^3 + 3k^2 + 5k + 3$

$\Rightarrow (k^3 + 2k) + (3k^2 + 3k + 3)$

$\Rightarrow 3B + 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.

Key Points to Remember: By mathematical induction, since both the base case and $P_{k}$ being true implies $P_{k+1}$ is true, $P_{n}$ is true for all n in the domain.

Example 2: Show that $3^n - 1$ is a multiple of 2 for n = 1, 2, ...

Solution: Step 1 − For $n = 1$, substitute in the given equation, we get

$3^1-1 = 3-1 = 2$ which is a multiple of 2

Step 2 − Let us assume $n = k$ to show that$ 3^n - 1$ is true for $n=k$, 

Hence, $3^k -1$ is true (assumption).

Step 3 − We have to prove that $3^{k+1}-1$ is also a multiple of 2

$3^{k+1} - 1 = 3 \times 3^k - 1 = (2 \times 3^k) + (3^k - 1)$

The first part, $(2 \times 3k)$, is a multiple of 2, and the second part, $(3k -1)$, supports our previous assumption.

Hence, $3^{k+1} - 1$ is a multiple of 2.

So, we can say that $3^n - 1$ is a multiple of 2.

Solved Problems of Previous Year’s Question

1. Show that $1 + 3 + 5 + \ldots + (2n - 1) = n^{2}$

Solution: To show that result is true for $n=1$ by substituting in $n^2$

We get $1=(1)^{2}$ Hence n = 1 is True.

Now, assume that result is true for $n=k$

$1 + 3 + 5 + \ldots + (2k - 1) = k^{2}$ is true (assumption)

Check for $n=k+1$

i.e., $1 + 3 + 5 + \ldots + (2(k + 1) - 1) = (k + 1)^{2}$

The above equation can be written as

$1 + 3 + 5 + \ldots + (2{k} - 1) + (2({k} + 1) - 1) = ({k} + 1)^{2}$

From assumption, we can write the equation as

$\Rightarrow k^{2} + (2(k + 1) - 1) = (k + 1)^{2}$

$\Rightarrow k^{2} + 2k + 2 - 1 = (k + 1)^{2}$

$\Rightarrow k^{2} + 2k + 1 = (k + 1)^{2}$

$\Rightarrow (k + 1)^{2} = (k + 1)^{2}$

So the result is true for $n=k+1$ as LHS = RHS

Trick to Solve: 1. Statement: Let $P_n$ be the proposition induction hypothesis for n in the domain.
2. Base Case: Consider the base case:

When LHS = RHS, the base case is true.

3. Induction Step: Assume $P_k$ is true for some k in the domain.

Consider $P_{k+1}$

LHS $P_{k+1}$

​RHS $P_{k+1}$ (using induction hypothesis).

Hence $P_k$ is true which then implies that $P_{k+1}$ is true.

2. Prove that $(ab)^n = a^nb^n$ is true for every natural number $n$.

Solution: For $n=1$, $(ab)^1 = a^1b^1 = ab$, Hence, it is true.

Now, let us assume the statement is true for $n=k$,

$(ab)^k = a^kb^k$ is true (assumption).

Check for $n=k+1$

$(ab)^{k+1} = a^{k+1}b^{k+1}$

From the assumption, we have $(ab)^k = a^k b^k$

Or, $(ab)^k (ab) = (a^k b^k ) (ab)$  (Multiplying both side by 'ab')

Or, $(ab)^{k+1} = (a^{k+1}b^{k+1})$

Hence, it is true.

So, $(ab)^n = a^nb^n$ is true for every natural number n.

3.For all $n \geq 1$, prove that, $1^2 + 2^2 + 3^2….n^2 = \dfrac{n(n + 1) (2n + 1)}{6}$

Solution: Let the given statement be P(n),

Check if $P(n)=1^{2}+2^{2}+3^{2}+\ldots \ldots+n^{2}=\dfrac{n(n+1)(2 n+1)}{6}$ is true for n=1, 

$P(1)= \dfrac{1(1+1)(2(1)+1)}{6} = 1$, 

Hence P(1) is true.

Now, let's assume P(k) to be true i.e.,

$1^{2}+2^{2}+3^{2} \ldots k^{2}=\dfrac{k(k+1)(2 k+1)}{6}$ is true (assumption)

Let's show that $P(k+1)$ true.

$\Rightarrow P(k+1)=P(k)+(k+1)^{2}$

$\Rightarrow \dfrac{k(k+1)(2 k+1)}{6}+(k+1)^{2}$

$\Rightarrow \dfrac{k(k+1)(2 k+1)+6(k+1)^{2}}{6}$

$\Rightarrow (k+1) \dfrac{\left(2 k^{2}+k\right)+6(k+1)}{6}$

$\Rightarrow \dfrac{(k+1)\left(2 k^{2}+7 k+6\right)}{6}$

$\Rightarrow \dfrac{(k+1)(k+2)(2 k+3)}{6}$

$\Rightarrow \dfrac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$

When P(k) is true for all natural numbers, P(k + 1) is true. As a result of the mathematical induction process, the provided result holds true for all natural numbers.

Conclusion

Mathematical induction is a method of proving that something is true for all integers starting with a small number, usually 0 or 1. There are three parts to proof: (1) Prove it in the base case, (2) Assume that k is an integer and (3) Demonstrate that it holds for k+1 using that assumption. It can be used to analyse complexity and correctness.

Important Related Links for JEE Main 2022-23