Principles of Mathematical Induction

1. FIRST PRINCIPLE OF MATHEMATICAL INDUCTION

The proof of proposition by mathematical induction consists of the following three steps :
Step I : (Verification step) : Actual verification of the proposition for the starting value “i”
Step II : (Induction step) : Assuming the proposition to be true for “k”, k$\ge$i and proving that it is true for the value (k + 1) which is next higher integer.
Step III : (Generalization step) : To combine the above two steps Let p(n) be a statement involving the natural number n such that
(i) p(1) is true i.e. p(n) is true for n = 1.

(ii) p(m + 1) is true, whenever p(m) is true i.e. p(m) is true ⇒ p(m + 1) is true.
Then p(n) is true for all natural numbers n.

2. SECOND PRINCIPLE OF MATHEMATICAL INDUCTION

The proof of proposition by mathematical induction consists of following steps :
Step I : (Verification step) : Actual verification of the proposition for the starting value i and (i + 1).
Step II : (Induction step) : Assuming the proposition to be true for k – 1 and k and then proving that it is true for the value k + 1; k $\ge$ i + 1.
Step III : (Generalization step) : Combining the above two steps.
Let p(n) be a statement involving the natural number n such that
(i) p(1) is true i.e. p(n) is true for n = 1 and
(ii) p(m + 1) is true, whenever p(n) is true for all n, where $\mathrm{i}\le \mathrm{n}\le \mathrm{m}$
Then p(n) is true for all natural numbers.
For a $\ne$ b, The expression $a^n–b^n$ is divisible by
(a) a + b if n is even.                               (b) a – b is n if odd or even. 

3. SOME USEFUL FORMULAS

Here are some formulas for sequences that are great for practicing proofs by induction. For any natural number n

• 1 + 2 + 3+….+ n = $\frac{\mathrm{n}(\mathrm{n}+1)}{2}$
• 1 + 3 + 5 + … + (2n-1) = n²
• 1 + 2 + 2² + … + 2ⁿ = 2ⁿ⁺¹ – 1
• 1² + 2² + 3² + … + n² = $\frac{\mathrm{n}(\mathrm{n}+1)(2\mathrm{n}+1)}{6}$
• 1³ + 2³ + 3³ + … + n³ = [n(n+1)/2]²
• 1*2 + 2*3 + … + n(n + 1) = $\frac{\mathrm{n}(\mathrm{n}+1)(\mathrm{n}+2)}{3}$
• 1² + 3² + 5² + … + (2n + 1)² = $\frac{(\mathrm{n}+1)(2\mathrm{n}+1)(2\mathrm{n}+3)}{3}$

Illustration -1
The value of $\frac{1}{1.2.3}+\frac{1}{2.3.4}+\dots \dots +\frac{1}{\mathrm{n}(\mathrm{n}+1)(\mathrm{n}+2)}$ is

(A) $\frac{\mathrm{n}(\mathrm{n}+1)}{2}$      (B) $\frac{\mathrm{n}(\mathrm{n}+1)(2\mathrm{n}+1)}{6}$        (C) $\frac{\mathrm{n}(\mathrm{n}+3)}{4(\mathrm{n}+1)(\mathrm{n}+2)}$       (D) none of these

Solution

(C)

Let P(n) $\equiv \frac{1}{1.2.3}+\frac{1}{2.3.4}+\dots ..+\frac{1}{\mathrm{n}(\mathrm{n}+1)(\mathrm{n}+2)}=\frac{\mathrm{n}(\mathrm{n}+3)}{4(\mathrm{n}+1)(\mathrm{n}+2)}$

$\mathrm{P}\left(1\right)=\frac{1}{1.2.3}=\frac{1}{6}\text{ on the L.H.S; on the R.H.S }=\frac{1(1+3)}{4(1+1)(1+2)}=\frac{1}{6}$

$\Rightarrow$ P(1) is true

Let P(k) be true.

$\Rightarrow \frac{1}{1.2.3}+\frac{1}{2.3.4}+\dots ..+\frac{1}{\mathrm{k}(\mathrm{k}+1)(\mathrm{k}+2)}=\frac{\mathrm{k}(\mathrm{k}+3)}{4(\mathrm{k}+1)(\mathrm{k}+2)}$

P(k + 1) on the L.H.S.

= $\left[\frac{1}{1.2.3}+\frac{1}{2.3.4}+\dots ..+\frac{1}{\mathrm{k}(\mathrm{k}+1)(\mathrm{k}+2)}\right]+\frac{1}{(\mathrm{k}+1)(\mathrm{k}+2)(\mathrm{k}+3)}$

The sum within the square brackets is P(k) which equals $\frac{\mathrm{k}(\mathrm{k}+3)}{4(\mathrm{k}+1)(\mathrm{k}+2)}$

$\Rightarrow$ P(k + 1) = $\frac{\mathrm{k}(\mathrm{k}+3)}{4(\mathrm{k}+1)(\mathrm{k}+2)}+\frac{1}{(\mathrm{k}+1)(\mathrm{k}+2)(\mathrm{k}+3)}=\frac{1}{4(\mathrm{k}+1)(\mathrm{k}+2)}\left[\frac{\mathrm{k}(\mathrm{k}+3{)}^2+4}{(\mathrm{k}+3)}\right]$

= $\frac{1}{4(\mathrm{k}+1)(\mathrm{k}+2)(\mathrm{k}+3)}\left[(\mathrm{k}+1{)}^2(\mathrm{k}+4)\right]=\frac{(\mathrm{k}+1)(\mathrm{k}+4)}{4(\mathrm{k}+2)(\mathrm{k}+3)}$.

Which is the desired R.H.S. of P(k+1) . Hence, P(k+1) is true.

Hence, by mathematical induction, the result is true for all n.

Illustration -2

The value of $\left[1–\frac{1}{2^2}\right]\left[1–\frac{1}{3^2}\right]\dots \dots \left[1–\frac{1}{(n+1{)}^2}\right]$ is, $\forall \mathrm{n}\in \mathrm{N}$

(A) $\frac{\mathrm{n}–1}{4}$           (B) $\frac{\mathrm{n}+2}{2\mathrm{n}+2}$        (C) $\frac{\mathrm{n}\left(\mathrm{n}–1\right)}{6}$       (D) $\frac{\mathrm{n}+2}{4\left(\mathrm{n}+1\right)}$

Solution

(B)

Let P(n) $\equiv \left[1–\frac{1}{2^2}\right]\left[1–\frac{1}{3^2}\right]\dots \dots \left[1–\frac{1}{(\mathrm{n}+1{)}^2}\right]=\frac{\mathrm{n}+2}{2\mathrm{n}+2}$

L.H.S. of P(1) =  $\left[1–\frac{1}{2^2}\right]=\frac{3}{4}$ = R.H.S

Hence P(1) is true.

Assume that P(k) is true.

$\Rightarrow \left[1–\frac{1}{2^2}\right]\left[1–\frac{1}{3^2}\right]\dots \left[1–\frac{1}{(\mathrm{k}+1{)}^2}\right]=\frac{\mathrm{k}+2}{2\mathrm{k}+2}$

For P(k + 1), the L.H.S. becomes

$\left[1–\frac{1}{2^2}\right]\left[1–\frac{1}{3^2}\right]\dots .\left[1–\frac{1}{(\mathrm{k}+1{)}^2}\right]\left[1–\frac{1}{(\mathrm{k}+2{)}^2}\right]$

= $\mathrm{P}\left(\mathrm{k}\right)\left[1–\frac{1}{(\mathrm{k}+2{)}^2}\right]=\frac{\mathrm{k}+2}{2\mathrm{k}+2}\left[\frac{{\mathrm{k}}^2+4\mathrm{k}+3}{(\mathrm{k}+2{)}^2}\right]$

= $\frac{\mathrm{k}+2}{2\mathrm{k}+2}\frac{(\mathrm{k}+1)(\mathrm{k}+3)}{(\mathrm{k}+2{)}^2}=\frac{(\mathrm{k}+2)(\mathrm{k}+1)(\mathrm{k}+3)}{2(\mathrm{k}+1)(\mathrm{k}+2{)}^2}$

$=\frac{\mathrm{k}+3}{2(\mathrm{k}+1)+2}\Rightarrow \mathrm{P}(\mathrm{k}+1)\text{ is true }$

Hence, by mathematical induction, the result is true for all n ∈ N

Illustration -3

The smallest positive integer n, for which $\mathrm{n}!<{\left(\frac{\mathrm{n}+1}{2}\right)}^{\mathrm{n}}$ hold is

(A) 1         (B) 2          (C) 3            (D) 4

Solution

(B)

Let P(n) : $\mathrm{n}!<{\left(\frac{\mathrm{n}+1}{2}\right)}^n$

Step I: For n = 2  $\Rightarrow 2!<{\left(\frac{2+1}{2}\right)}^2\Rightarrow 2<\frac{9}{4}$

⇒ 2 < 2.25 which is true. Therefore, P(2) is true.

Step II: Assume that P(k) is true, then P(k): $\mathrm{k}!<{\left(\frac{\mathrm{k}+1}{2}\right)}^{\mathrm{k}}$

Step III: For n = k + 1, P(k + 1): (k + 1)! < ${\left(\frac{\mathrm{k}+2}{2}\right)}^{\mathrm{k}+1}$

$\Rightarrow \mathrm{k}!<{\left(\frac{\mathrm{k}+1}{2}\right)}^{\mathrm{k}}\Rightarrow \left(\mathrm{k}+1\right)\mathrm{k}!<\frac{(\mathrm{k}+1{)}^{\mathrm{k}+1}}{2^{\mathrm{k}}}$

⇒ (k + 1)k!  < $\frac{(\mathrm{k}+1{)}^{\mathrm{k}+1}}{2^{\mathrm{k}}}$  ^{___________________} (i)

and   $\frac{(\mathrm{k}+1{)}^{\mathrm{k}+1}}{2^{\mathrm{k}}}<{\left(\frac{\mathrm{k}+2}{2}\right)}^{\mathrm{k}+1}$   ^{___________________} (ii)

$\Rightarrow {\left(\frac{\mathrm{k}+2}{\mathrm{k}+1}\right)}^{k+1}>2\Rightarrow {\left[1+\frac{1}{\mathrm{k}+1}\right]}^{k+1}>2$

$\Rightarrow 1+(\mathrm{k}+1)\frac{1}{\mathrm{k}+1}+\mathrm{k}+\mathrm{C}_2^1{\left(\frac{1}{\mathrm{k}+1}\right)}^2+\dots \dots \dots .>2$

$\Rightarrow 1+1+\mathrm{C}_2^{\mathrm{k}+1}{\left(\frac{1}{\mathrm{k}+1}\right)}^2+\dots \dots \dots .>2$

Which is true, hence (ii) is true.

From (i) and (ii),  $(\mathrm{k}+1)!<\frac{(\mathrm{k}+1{)}^{\mathrm{k}+1}}{2^{\mathrm{k}}}<{\left(\frac{\mathrm{k}+2}{2}\right)}^{\mathrm{k}+1}\Rightarrow (\mathrm{k}+1)!<{\left(\frac{\mathrm{k}+2}{2}\right)}^{\mathrm{k}+1}$

Hence P(k+1) is true. Hence by the principle of mathematical induction P(n) is true for all n∈N

Trick: By check options,

(A) For n = 1,  $1!<{\left(\frac{1+1}{2}\right)}^1\Rightarrow$ 1 < 1 which is wrong

(B) For n = 2, $2!<{\left(\frac{3}{2}\right)}^2\Rightarrow 2<\frac{9}{4}$  which is correct

(C) For n = 3,  $3!<{\left(\frac{3+1}{2}\right)}^3\Rightarrow$ 6 < 8 which is correct

(D) For n = 4, $4!<{\left(\frac{4+1}{2}\right)}^4\Rightarrow 24<{\left(\frac{5}{2}\right)}^4$

⇒ 24 < 39.0625 which is correct.

But smallest positive integer n is 2.

Illustration -4

Let S(k) = 1 + 3 + 5 + … + (2k – 1) = 3 + k². Then which of the following is true.

(A) Principle of mathematical induction can be used to prove the formula

(B) S(k) ⇒ S(k+1)

(C) S(k) $\cancel{\Rightarrow }$ S(k+1)

(D) S(1) is correct

Solution

(C)

We have S(k) = 1 + 3 + 5 + ….+ (2k – 1) = 3 + k²,

S(1) ⇒ 1 = 4, Which is not true and S(2) ⇒ 3 = 7, Which is not true. Hence induction cannot be applied and S(k) $\cancel{\Rightarrow }$ S(k + 1).

Illustration -5

Given  ${\mathrm{U}}_{\mathrm{n}+1}=3{\mathrm{U}}_{\mathrm{n}}–2{\mathrm{U}}_{\mathrm{n}–1}\text{ and }{\mathrm{U}}_0=2, {\mathrm{U}}_1=3$, the value of ${\mathrm{U}}_{\mathrm{n}}$ for all n∈N is

(A) $2^n–1$             (B)  $2^n+1$                       (C) 0          (D) None of these

Solution

(B)

$\because {\mathrm{U}}_{\mathrm{n}+1}=3{\mathrm{U}}_{\mathrm{n}}–2{\mathrm{U}}_{\mathrm{n}–1}$…..(i)

Step I : Given $U_1=3$

For n =1,  ${\mathrm{U}}_{1+1}=3{\mathrm{U}}_1–2{\mathrm{U}}_0, {\mathrm{U}}_2=3.3–2.2=5$,

Option (b) ${\mathrm{U}}_{\mathrm{n}}=2^{\mathrm{n}}+1$

For n = 1, ${\mathrm{U}}_1=2^1+1=3$ which is true. For n = 2, ${\mathrm{U}}_2=2^2+1=5$ which is true

Therefore, the result is true for n = 1 and n = 2

Step II : Assume it is true for n = k then it is also true for n = k – 1

Then  ${\mathrm{U}}_{\mathrm{k}}=2^{\mathrm{k}}+1$    …..(ii) and  ${\mathrm{U}}_{\mathrm{k}–1}=2^{\mathrm{k}–1}+1$  …..(iii)

Step III : Putting n = k in (i), we get

${\mathrm{U}}_{\mathrm{k}+1}=3{\mathrm{U}}_{\mathrm{k}}–2{\mathrm{U}}_{\mathrm{k}–1}=3\left[2^{\mathrm{k}}+1\right]–2\left[2^{\mathrm{k}–1}+1\right]$

= $3.2^{\mathrm{k}}+3–2.2^{\mathrm{k}–1}–2=3.2^{\mathrm{k}}+1–2.2^{\mathrm{k}–1}$

$\Rightarrow 3.2^{\mathrm{k}}–2^{\mathrm{k}}+1=2.2^{\mathrm{k}}+1=2^{\mathrm{k}+1}+1$

$\Rightarrow {\mathrm{U}}_{\mathrm{k}+1}=2^{\mathrm{k}+1}+1$

This shows that the result is true for n=k+1, by the principle of mathematical induction the result is true for all n∈N.

Illustration -6

Prove the following by using the principle of mathematical induction for all n ∈ N:

1³ + 2³ + 3³ + …. + n³ = ${\left(\frac{\mathrm{n}(\mathrm{n}–1)}{2}\right)}^2$

Solution

Let the given statement be P(n), i.e.,

P(n): 1³ + 2³ + 3³ + …. + n³ = ${\left(\frac{\mathrm{n}(\mathrm{n}+1)}{2}\right)}^2$

For n = 1, we have

P(1): 1³ = 1 = ${\left(\frac{1(1+1)}{2}\right)}^2={\left(\frac{1.2}{2}\right)}^2=1^2=1$,  which is true.

Let P(k) be true for some positive integer k, i.e.,

1³ + 2³ + 3³ + ….. + k³ = ${\left(\frac{\mathrm{k}(\mathrm{k}+1)}{2}\right)}^2$ ^__________ (i)

We shall now prove that P(k + 1) is true.

Consider

1³ + 2³ + 3³ + … + k³ + (k + 1)³ $={\left(\frac{\mathrm{k}(\mathrm{k}+1)}{2}\right)}^2+(\mathrm{k}+1{)}^3$     [Using (i)]

$=\frac{{\mathrm{k}}^2(\mathrm{k}+1{)}^2}{4}+(\mathrm{k}+1{)}^3$

$=\frac{{\mathrm{k}}^2(\mathrm{k}+1{)}^2+4(\mathrm{k}+1{)}^3}{4}$

$=\frac{(\mathrm{k}+1{)}^2\left\{{\mathrm{k}}^2+4(\mathrm{k}+1)\right\}}{4}$

$=\frac{(\mathrm{k}+1{)}^2\left\{{\mathrm{k}}^2+4\mathrm{k}+4\right\}}{4}$

$=\frac{(\mathrm{k}+1{)}^2(\mathrm{k}+2{)}^2}{4}$

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

$={\left(\frac{(\mathrm{k}+1)(\mathrm{k}+1+1)}{2}\right)}^2$

Thus, P(k + 1) is true whenever P(k) is true.

Hence, by the principle of mathematical induction, statement P(n) is true for all natural numbers i.e., n.

Illustration -7

Prove the following by using the principle of mathematical induction for all n ∈ N:

1² + 3² + 5² + … + (2n – 1)² = $\frac{\mathrm{n}(2\mathrm{n}–1)(2\mathrm{n}+1)}{3}$

Solution

Let the given statement be P(n), i.e.,

P(n) = 1² + 3² + 5² + … + (2n – 1)² = $\frac{\mathrm{n}(2\mathrm{n}–1)(2\mathrm{n}+1)}{3}$

For n = 1, we have

P(1) = 1² = 1 = $\frac{1(2.1–1)(2.1+1)}{3}=\frac{1.1.3}{3}=1$, which is true.

Let P(k) be true for some positive integer k, i.e.,

P(k) = 1² + 3² + 5² + … + (2k – 1)² = $\frac{\mathrm{k}(2\mathrm{k}–1)(2\mathrm{k}+1)}{3}$  ^{_____________} (1)

We shall now prove that P(k + 1) is true.

Consider

{1² + 3² + 5² + … + (2k – 1)²} + {2(k + 1) – 1}²

$=\frac{\mathrm{k}(2\mathrm{k}–1)(2\mathrm{k}+1)}{3}+(2\mathrm{k}+2–1{)}^2$    [Using (1)]

$=\frac{\mathrm{k}(2\mathrm{k}–1)(2\mathrm{k}+1)}{3}=(2\mathrm{k}+1{)}^2$

$=\frac{\mathrm{k}(2\mathrm{k}–1)(2\mathrm{k}+1)+3(2\mathrm{k}+1{)}^2}{3}$

$=\frac{(2\mathrm{k}+1)\left\{\mathrm{k}\right(2\mathrm{k}–1)+3(2\mathrm{k}+1\left)\right\}}{3}$

$=\frac{(2\mathrm{k}+1)\left\{2{\mathrm{k}}^2–\mathrm{k}+6\mathrm{k}+3\right\}}{3}$

$=\frac{(2\mathrm{k}+1)\left\{2{\mathrm{k}}^2+5\mathrm{k}+3\right\}}{3}$

$=\frac{(2\mathrm{k}+1)\left\{2{\mathrm{k}}^2+2\mathrm{k}+3\mathrm{k}+3\right\}}{3}$

$=\frac{(2\mathrm{k}+1)\left\{2\mathrm{k}\right(\mathrm{k}+1)+3(\mathrm{k}+3\left)\right\}}{3}$

$=\frac{(2\mathrm{k}+1)(\mathrm{k}+1)(2\mathrm{k}+3)}{3}$

$=\frac{(\mathrm{k}+1)\left\{2\right(\mathrm{k}+1)–1\}\left\{2\right(\mathrm{k}+1)+1\}}{3}$

Thus, P(k + 1) is true whenever P(k) is true.

Hence, by the principle of mathematical induction, statement P(n) is true for all natural numbers i.e., n.

4. DIVISIBILITY PROBLEMS

To show that an expression is divisible by an integer

(i) If a, p, n, r are positive integers, then first of all we write ${\mathrm{a}}^{\mathrm{pn}+\mathrm{r}}={\mathrm{a}}^{\mathrm{pn}}·{\mathrm{a}}^{\mathrm{r}}={\left({\mathrm{a}}^{\mathrm{p}}\right)}^{\mathrm{n}}·{\mathrm{a}}^{\mathrm{r}}.$

(ii) If we have to show that the given expression is divisible by c.

Then express, ${\mathrm{a}}^{\mathrm{p}}=\left[1+\left({\mathrm{a}}^{\mathrm{p}}–1\right]\right.$, if some power of $\left({\mathrm{a}}^{\mathrm{p}}–1\right)$ has c as a factor.

${\mathrm{a}}^{\mathrm{p}}=\left[2+\left({\mathrm{a}}^{\mathrm{p}}–2\right)\right]$, if some power of $\left({\mathrm{a}}^{\mathrm{p}}–2\right)$ has c as a factor.

${\mathrm{a}}^{\mathrm{p}}=\left[\mathrm{K}+\left({\mathrm{a}}^{\mathrm{p}}–\mathrm{K}\right)\right]$, if some power of $\left({\mathrm{a}}^{\mathrm{p}}–\mathrm{K}\right)$ has c as a factor.

Illustration -8

For every natural number n, 11ⁿ⁺² + 12²ⁿ⁺¹ is divisible by

(A) 133                          (B) 123                 (C) 91                (D) none of these

Solution

(A).

Let P(n) = 11ⁿ⁺² + 12²ⁿ⁺¹

P(1) = 11³ + 12³ = 3059 which is divisible by 133.

Let P(k) = 11^k+2 + 12^2k+1 be divisible by 133.

P(k+1) = 11^k+3 + 12^2k+3  = 11^k+2.11 + 12^2k+1 144,

= 11.11^k+2 + (133 + 11) 12^2k+1

= 11[11^k+2 + 12^2k+1] + 133.12^2k+1

= 11.P(k) + 133.12^2k+1

P(K) is divisible by 133 also 133.12^2k+1 is divisible by 133. Hence, P (k + 1) is also divisible by 133. Hence, by mathematical induction, the result is true for all n.

Illustration -9

For every natural number n, 5^{2n + 2} –24n – 25 is divisible by

(A) 502                          (B) 223                 (C) 471                   (D) 576

Solution

(D)

Let P (n) = 5^{2n + 2} –24n –25

Then P (1) = 5⁴ –24 –25 = 576

Then P (1) is divisible by 576

Now assume that P (k) is divisible by 576, that is assume

P (k) = 5^{2k + 2} – 24k – 25 = 576m        ……(1)

where m is a positive integer.

P (k + 1) = 5^{2(k + 1) + 2} – 24(k + 1) – 25 = 5².5^{2k + 2} – 24k – 49

= 25[5^{2k + 2} – 24k – 25] + 25.24k + 25.25 – 24k – 49 = 25P (k) + 576k + 576

= 25.576m + 576(k + 1)  by (1)  = 576(25m + k + 1)

Hence P (k + 1) is divisible by 576.

Hence by mathematical induction, the result is true for all n.

Illustration -10

$(1+x{)}^n–nx–1$ is divisible by (where n ∈ N)

(A) 2x            (B) $x^2$          (C) $2x^3$              (D) All of these

Solution

(B)

$(1+x{)}^n=1+nx+\frac{n(n–1)}{2!}{x}^2+\frac{n(n–1)(n–2)}{3!}{x}^3+\dots ..$

$\Rightarrow (1+\mathrm{x}{)}^{\mathrm{n}}–\mathrm{nx}–1={\mathrm{x}}^2\left[\frac{\mathrm{n}(\mathrm{n}–1)}{2!}+\frac{\mathrm{n}(\mathrm{n}–1)(\mathrm{n}–3)}{3!}\mathrm{x}+\dots ..\right]$

From above it is clear that $(1+\mathrm{x}{)}^{\mathrm{n}}–\mathrm{nx}–1$ is divisible by $x^2$.

Trick: $(1+\mathrm{x}{)}^{\mathrm{n}}–\mathrm{nx}–1$. Put n=2 and x=3;  Then $4^2–2.3–1=9$

Is not divisible by 6, 54 but divisible by 9. Which is given by option (c) = $x^2–9$.

Illustration -11

The greatest integer which divides the number ${101}^{100}–1$ is

(A) 100                          (B) 1000               (C) 10000           (D) 100000

Solution

(C)

$(1+100{)}^{100}=1+100·100+\frac{100.99}{1.2}(100{)}^2+\dots$

$\Rightarrow {101}^{100}–1=100.100\left[1+\frac{100.99}{1.2}+\frac{100.99.98}{3.2.1}100+\dots ..\right]$

$\Rightarrow$ From above it is clear that, ${100}^{100}–1$ is divisible by  $(100{)}^2=10000$

5. APPLICATIONs OF MATHEMATICAL INDUCTION

  SOME IMPORTANT POINTS

1. A.P. Series : a + (a + d) + (a + 2d) +……….

i) n^th term = $a+(n–1)d=t_n=S_n–S_{n–1}$

ii) Sum of first n terms of an A.P.

= $S_n=\sum t_n=\frac{n}{2}[2a+(n–1\left)d\right]$ (where a is first term, d is common difference of an A.P.)

2. G.P. Series : a + ar + ar² + ar³ +……..

i) n^th term = $t_n=a.r^{n–1}$

ii) Sum of first n terms = ${\mathrm{S}}_{\mathrm{n}}=\frac{\mathrm{a}\left({\mathrm{r}}^{\mathrm{n}}–1\right)}{\mathrm{r}–1}\text{ if }\mathrm{r}>1$

                                                      $=\frac{\mathrm{a}\left(1–{\mathrm{r}}^{\mathrm{n}}\right)}{1–\mathrm{r}}\text{ if }r<1$

iii) Sum of infinite terms = $S_{\infty }=\frac{a}{1–r}\left(\right|r|<1)$

3. Arithmetico – Geometric series (A.G.P.) :

a+(a+d).r+(a+2d).r²+…….+(a+(n – 1)d).r^n-1

i) n^th term of the series = ${\mathrm{t}}_{\mathrm{n}}=\left(\mathrm{a}+(\mathrm{n}–1)\mathrm{d}).{\mathrm{r}}^{\mathrm{n}–1}\right.$

ii) Sum of n terms = ${\mathrm{S}}_{\mathrm{n}}=\frac{\mathrm{a}}{1–\mathrm{r}}+\frac{\mathrm{dr}\left(1–{\mathrm{r}}^{\mathrm{n}–1}\right)}{(1–\mathrm{r}{)}^2}–\frac{(\mathrm{a}+\overline{\mathrm{n}–1}\mathrm{d}){\mathrm{r}}^{\mathrm{n}}}{(1–\mathrm{r})}$

iii) Sum of infinite terms = $S_{\infty }=\frac{a}{1–r}+\frac{dr}{(1–r{)}^2},\left|r\right|<1$

4. $\frac{1}{\mathrm{a}(\mathrm{a}+\mathrm{d})}+\frac{1}{(\mathrm{a}+\mathrm{d})(\mathrm{a}+2\mathrm{d})}+\dots ..+\frac{1}{(\mathrm{a}+(\mathrm{n}–1\left)\mathrm{d}\right)(\mathrm{a}+\mathrm{nd})}+\dots ..$

i) $\frac{1}{\{\mathrm{a}+(\mathrm{n}–1\left)\mathrm{d}\right\}(\mathrm{a}+\mathrm{nd})}{\mathrm{t}}_{\mathrm{n}}={\mathrm{n}}^{\mathrm{th}}\text{ term }$

ii) sum of n terms = ${\mathrm{S}}_{\mathrm{n}}=\frac{1}{\mathrm{d}}\left[\frac{1}{\mathrm{a}}–\frac{1}{\mathrm{a}+\mathrm{nd}}\right]=\frac{\mathrm{n}}{\mathrm{a}(\mathrm{a}+\mathrm{nd})}$

5. For a sequence, $T_1,T_2,T_3,T_4,\dots \dots$

the differnece of consecutive terms $\left(T_2–T_1,T_3–T_2,T_4–T_3\text{ etc.. }\right)$ are in A.P or G.P then n^th term of given series are in the form of $a{n}^2+bn+c\text{ or }a.r^n+b$ where a, b, c to be determined.

6. In finding n^th term of the series, in the suitable option

n = 1 gives the I^st term of the series

n = 2 gives the II^nd term of series.

7. In finding the sum of n terms of the series in the suitable option

n=1 gives the I^st term of the series

n=2 gives the sum of first 2 terms of the series

n=3 gives the sum of first 3 terms of the series.

8. To test the divisibility of the given expression put n = 1 and n = 2 in the given expression and get their values and G.C.D or H.C.F. of these two values gives the required divisor.

9. If the series is given upto n terms then begin the verification with n = 1, if the series is given upto (n – 1) terms, then begin the verification with n = 2. If the series is given upto (n – 2) terms, then begin the verification with n=3 etc.

10. $\cos \alpha +\cos (\alpha +\beta )+\cos (\alpha +2\beta )+\dots ++\cos (\alpha +(\mathrm{n}–1\left)\beta \right)$ = $\frac{\sin (n\beta /2)}{\sin (\beta /2)}\times \cos \left[\alpha +(n–1{)}^{\beta }/2\right]$

11. $\cos \alpha ·\cos 2\alpha ·\cos 4\alpha \dots \cos \left(2^{n–1}\alpha \right)$ = $\frac{\sin \left(2^n\alpha \right)}{2^n\sin \alpha }$

12. $\left(1+\frac{3}{1}\right)\left(1+\frac{5}{4}\right)\left(1+\frac{7}{9}\right)\dots \left(1+\frac{2\mathrm{n}+1}{{\mathrm{n}}^2}\right)=(\mathrm{n}+1{)}^2$

13. The sum of cubes of three consecutive natural numbers is always divisible by 9

14. For all positive integral values of n , $x^n–y^n$ is divisible by x – y.

15. For all positive integral values of n, $x^{2n+1}+y^{2n+1}$ is divisible by x + y.

16. For all positive integral values of n, $x^{2n–1}+y^{2n–1}$is divisible by x + y.

17. $P^{n+1}+(P+1{)}^{2n–1}$is divisible by $P^2+P+1,\forall n\ge 2$

18. $n^p–n$ is divisible by $P\forall n\ge 2$ where P is prime.

19. n is any odd integer then $n\left(n^2–1\right)$ is divisible by 24.

20. The product of “n” consecutive natural numbers is  always divisible by n!.

21. If x, y, m are positive integers then x is said to be congruent of y modulo m if x – y is divisible by m and is denoted by $\mathrm{x}\equiv \mathrm{y}\left(\mathrm{modm}\right)$

22. Suppose it is given F(n) > G(n) or $\frac{\mathrm{F}\left(\mathrm{n}\right)}{\mathrm{G}\left(\mathrm{n}\right)}>1$

We have to prove that

F(n +1 ) > G(n + 1) or $\frac{\mathrm{F}(\mathrm{n}+1)}{\mathrm{G}(\mathrm{n}+1)}>1$

or  $\frac{\mathrm{F}(\mathrm{n}+1)}{\mathrm{G}(\mathrm{n}+1)}>\frac{\mathrm{F}\left(\mathrm{n}\right)}{\mathrm{G}\left(\mathrm{n}\right)}>1\text{ or }\frac{\mathrm{F}(\mathrm{n}+1)}{\mathrm{F}\left(\mathrm{n}\right)}\frac{\mathrm{G}\left(\mathrm{n}\right)}{\mathrm{G}(\mathrm{n}+1)}>1.$

Illustration -12

For all n ∈ N, ²ⁿC_n

(A) < 4ⁿ          (B) > 4ⁿ       (C) > 2n + 1       (D) none of these

Solution

(A)

To show ²ⁿC_n < 4ⁿ

F(n) = 4ⁿ,   G(n) = ²ⁿC_n

F(n+1) = 4ⁿ⁺¹,   G(n+1) = ²ⁿ⁺²C_n+1

$\frac{\mathrm{F}(\mathrm{n}+1)}{\mathrm{F}\left(\mathrm{n}\right)}·\frac{\mathrm{G}\left(\mathrm{n}\right)}{\mathrm{G}(\mathrm{n}+1)}=\frac{4^{\mathrm{n}+1}}{4^{\mathrm{n}}}·\frac{\mathrm{C}_{\mathrm{n}}^{2\mathrm{n}}}{\left(\mathrm{C}_{\mathrm{n}+1}^{2\mathrm{n}+2}\right)}$

= 4. $\frac{\left(2\mathrm{n}\right)!}{\mathrm{n}!\mathrm{n}!}·\frac{(\mathrm{n}+1)!(\mathrm{n}+1)}{2\mathrm{n}+1}=2·\frac{(\mathrm{n}+1)}{(2\mathrm{n}+1)}>1$.  ( since  2n + 2 > 2n + 1 )

$\Rightarrow \frac{\mathrm{F}(\mathrm{n}+1)}{\mathrm{G}(\mathrm{n}+1)}·\frac{\mathrm{G}\left(\mathrm{n}\right)}{\mathrm{F}\left(\mathrm{n}\right)}>1\text{ or }\frac{\mathrm{F}(\mathrm{n}+1)}{\mathrm{G}(\mathrm{n}+1)}>\frac{\mathrm{F}\left(\mathrm{n}\right)}{\mathrm{G}\left(\mathrm{n}\right)}>1\Rightarrow \mathrm{F}(\mathrm{n}+1)>\mathrm{G}(\mathrm{n}+1)$

Illustration -13

For all-natural numbers n greater than 1, the value of $1+\frac{1}{4}+\dots ..+\frac{1}{n^2}$

(A)  $\ge \frac{2}{n}–\frac{1}{n}$        (B)  $\le \frac{2}{\mathrm{n}}–\frac{1}{\mathrm{n}}$       (C) $<2–\frac{1}{n}$        (D) $>\frac{1}{n}$

Solution

(C). For n = 2,

$\mathrm{LH}.\mathrm{S}=1+\frac{1}{4}=\frac{5}{4}\text{ and }\mathrm{RH}.\mathrm{S}.=2–\frac{1}{2}=\frac{3}{2}$

$\frac{5}{4}<\frac{3}{2}$ Hence it holds for n = 2.

Assume the result to hold for n = k

$\Rightarrow 1+\frac{1}{4}+\frac{1}{9}+\dots .+\frac{1}{k^2}<2–\frac{1}{k}$

For n = k+1, $\left[1+\frac{1}{4}+\frac{1}{9}+\dots .+\frac{1}{k^2}\right]+\frac{1}{(k+1{)}^2}<2–\frac{1}{k}+\frac{1}{(k+1{)}^2}$

Now, if we show that

$2–\frac{1}{k}+\frac{1}{(k+1{)}^2}<2–\frac{1}{(k+1)}$

$\Rightarrow \frac{1}{k}–\frac{1}{(k+1{)}^2}>\frac{1}{(k+1)}$ then we are through.

$\Rightarrow \frac{1}{k}–\frac{1}{(k+1{)}^2}–\frac{1}{k+1}>0\Rightarrow \frac{(k+1{)}^2–k–k(k+1)}{k(k+1{)}^2}$

$=\frac{k^2+2k+1–k–k^2–k}{k(k+1{)}^2}=\frac{1}{k(k+1{)}^2}>0$

Hence the result is true for n = k + 1.

Hence, by mathematical induction, the result is true for all n.

Illustration -14

For what natural number n, the inequality 2ⁿ > 2n + 1 is valid?

(A) n $\ge$ 3               (B) n > 1                      (C) n = 2               (D) n > 5

Solution

(A)

For n = 1, 2 < 2 + 1

n = 2, 4 < 5

n = 3, 8 > 7

so the result is true for n = 3

assume the result is true for n = k > 3, i.e.

2^k > 2k + 1

So, P (k + 1) = 2^{k + 1} = 2.2^k > 2.(2k + 1) = 4k + 2

= [2(k + 1) + 1] + (2k –1) > 2(k + 1) + 1 as 2k –1 > 0, since k > 3

∴ The result is true for n = k + 1

∴ By the principal of mathematical induction, the result holds $\forall \mathrm{n}\ge 3$.

Illustration -15

If x + y = a + b, x² + y² = a² + b², then xⁿ + yⁿ = aⁿ + bⁿ

(A) $\forall \mathrm{n}\in \mathrm{N}$             (B) n $\ge$ 4      (C) n $\ge$ 3          (D) none of these

Solution

(A)

Let P(n) $\equiv$ xⁿ + yⁿ = aⁿ + bⁿ

P(1) $\equiv$ x + y = a + b      … (1)

P(2) $\equiv$ x² + y² = a² + b²   … (2)

Hence P(1) and P(2) are true.  Assume the result to be true for n $\le$ k.

⇒ x ^{k – 1} + y^{k – 1} = a^{k – 1} + b^{k – 1} and x^k + y^k = a^k + b^k

In order to prove that P(k + 1) is true, we write

x^{k + 1} + y^{k + 1} = x(a^k + b^k – y^k) + y(a^k + b^k – x^k)

= (a^k + b^k) (x + y) – xy (x^{k – 1} + y^{k – 1})

= (a^k + b^k) (a + b) – xy (a^{k – 1} + b^{k – 1})

Now from (1) and (2) xy = ab ⇒ x^{k + 1} + y^{k + 1} = a^{k + 1} + b^{k +1}

which is the desired R.H.S. for P(k + 1).

Hence, by mathematical induction, the result is true for all n.

Illustration -16

If u₁ = cos θ, u₂ = cos 2θ and u_n = 2u_{n –1} cosθ – u_{n –2} for n > 2. Then u_n

(A) tan nθ        (B) cot nθ         (C) sin nθ                 (D) cos nθ  

Solution

(D)

We have to prove that u_n = cos nθ $\forall$ n $\in$ N

Clearly u₁ = cos θ, u₂ = cos 2θ

So the result is true for n = 1 and n = 2  …(1)

Now assume the result for 2 < n $\le$ k …(2)

Then u_{k + 1} = 2u_kcosθ – u_{k –1}

= 2 cos kθ cosθ – cos (k –1)θ         Using (2)

= cos (k + 1)θ + cos (k –1)θ –cos (k –1)θ = cos (k + 1)θ      …(3)

Hence the result is true for n = k + 1

Hence by mathematical induction the result is true for all n ∈ N.

Illustration -17

Let  ${\mathrm{I}}_{\mathrm{m}}={\int }_0^{\mathrm{\pi }}\frac{1–\mathrm{cosmx}}{1–\mathrm{cosx}}\mathrm{dx}$, use mathematical induction, I_m

(A) $(\mathrm{m}–1)\frac{\mathrm{\pi }}{4}, \mathrm{m}=0,1,2,\dots$      (B) $(\mathrm{m}–1)\frac{\mathrm{\pi }}{3}, \mathrm{m}=0,1,2,\dots$   

(C), m$\frac{\mathrm{\pi }}{2}$ = 0, 1, 2…                   (D) m$\mathrm{\pi }$, m = 0, 1, 2 …

Solution

(D). ${\mathrm{l}}_1={\int }_0^{\mathrm{\pi }}\frac{1–\mathrm{cosx}}{1–\mathrm{cosx}}\mathrm{dx}=\mathrm{\pi }$

${\mathrm{I}}_2={\int }_0^{\mathrm{\pi }}\frac{1–\cos 2\mathrm{x}}{1–\mathrm{cosx}}\mathrm{dx}=2{\int }_0^{\mathrm{\pi }}(1+\cos 2\mathrm{x})\mathrm{dx}=2\mathrm{\pi }$

The result is true for m = 1, 2. Let the result be true for m $\le$ k.

Now, 2I_k – I_{k – 1} – I_{k + 1}

= ${\int }_0^{\mathrm{\pi }}\frac{2(1–\mathrm{coskx})–[1–\cos (\mathrm{k}–1\left)\mathrm{x}\right]–[1–\cos (\mathrm{k}+1\left)\mathrm{x}\right]}{(1–\mathrm{cosx})}\mathrm{dx}$

= ${\int }_0^{\mathrm{\pi }}\frac{\left[\cos \right(\mathrm{k}–1)\mathrm{x}–\mathrm{coskx}]+\left[\cos \right(\mathrm{k}+1)\mathrm{x}–\mathrm{coskx}]}{2{\sin }^2(\mathrm{x}/2)}\mathrm{dx}$

= ${\int }_0^2\frac{2\sin \frac{\mathrm{x}}{2}\left[\sin \left(\frac{2\mathrm{k}–1}{2}\right)\mathrm{x}–\sin \left(\frac{2\mathrm{k}+1}{2}\right)\mathrm{x}\right]}{2{\sin }^2\frac{\mathrm{x}}{2}}\mathrm{dx}$ = ${\int }_0^{\mathrm{\pi }}\frac{2\sin \frac{\mathrm{x}}{2}\times 2\sin \left(–\frac{\mathrm{x}}{2}\right)\mathrm{coskx}}{2{\sin }^2\frac{\mathrm{x}}{2}}\mathrm{dx}$

= $–{\int }_0^{\mathrm{\pi }}\mathrm{coskx} \mathrm{dx}=0\Rightarrow {\mathrm{I}}_{\mathrm{k}+1}=2{\mathrm{I}}_{\mathrm{k}}–{\mathrm{I}}_{\mathrm{k}–1}=(\mathrm{k}+1)\mathrm{\pi }$

⇒ The result is true for m = k + 1.

Hence, by mathematical induction, the result is true for all n.