Revision: Mathematical Inductions JEE Main Mathematical Inductions

Given that: a₁ = 3

a₂ = 7a_{2 – 1} = 7.a₁ = 7.3 = 21

a₃ = 7.a_{3 – 1} = 7.a₂ = 7.21 = 147

Let P(n): a_n = 3.7^{n – 1}, ∀ n ∈ N

Step 1: P(2) : a₂ = 3.7^{2 – 1} = 21

⇒ 21 = 21 which is true for P(2).

Step 2: P(k): a_k = 3.7^{k – 1}.

Let it be true.

Step 3: a_k = 7a_{k – 1}   .......(Given)

Put k = k + 1

a_{k + 1} = 7a_k = 7(3.7^{k – 1})

= 3.7^k+1–1

= `3.7^(("k"+1) – 1`

Which is true for P(k + 1).

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

Let P(n): `1/(n + 1) + 1/(n + 2) + ... + 1/(2n) > 13/24` ∀ n ∈ N

Step 1: P(2) : `1/(2 + 1) + 1/(2 + 2) > 13/24`

⇒ `1/3 + 1/4 > 13/24`

⇒ `7/12 > 13/24`

⇒ `14/24 > 13/24` which is true for P(2).

Step 2: P(k) : `1/(k + 1) + 1/(k + 2) + ... + 1/(2k) > 13/24`.

Let it be true for P(k).

Step 3: P(k + 1) : `1/(k + 1) + 1/(k + 2) + ... + 1/(2k) + 1/(2(k + 1)) > 13/24`

Since `1/(k + 1) + 1/(k + 2) + ... + 1/(2k) > 13/24`

So `1/(k + 1) + 1/(k + 2) + ... + 1/(2k) + 1/(2(k + 1)) > 13/24`

Which is true for P(k + 1).

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

Let P(n) : Number of subsets of a set containing n distinct elements is 2ⁿ, ∀ n ∈ N

Step 1: It is clear that P(1) is true for n = 1.

Number of subsets = 2¹ = 2.

Which is true.

Step 2: P(k) is assumed to be true for n = k.

Since the number of subsets = 2^k.

Step 3: P(k + 1) = 2^{k + 1}

We know that if one number (i.e., element) is added to the elements of a given set, the number of subsets become double.

∴ Number of subsets of set having (k + 1) distinct elements = 2 × 2^k = 2^{k + 1}

Which is true for P(k + 1).

Hence P(k + 1) is true whenever P(k) is true.

Let P(n) be the given statement, that is

P(n) : 1 × 1! + 2 × 2! + 3 × 3! + ... + n × n! = (n + 1)! – 1 for all natural numbers n.

Note that P(1) is true.

Since P(1): 1 × 1! = 1

= 2 – 1

= 2! – 1.

Assume that P(n) is true for some natural number k.

i.e., P(k) : 1 × 1! + 2 × 2! + 3 × 3! + ... + k × k! = (k + 1)! – 1

To prove P(k + 1) is true.

We have P(k + 1) : 1 × 1! + 2 × 2! + 3 × 3! + ... + k × k! + (k + 1) × (k + 1)!,

= (k + 1)! – 1 + (k + 1)! × (k + 1)

= (k + 1 + 1) (k + 1)! – 1

= (k + 2) (k + 1)! – 1 = ((k + 2)! – 1)

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

Therefore, by the Principle of Mathematical Induction, P(n) is true for all natural number n.

P(n) = 4ⁿ – 1 is divisible by 3.

So, substituting different values for n, we get,

P(0) = 4⁰ – 1 = 0 which is divisible by 3.

P(1) = 4¹ – 1 = 3 which is divisible by 3.

P(2) = 4² – 1 = 15 which is divisible by 3.

P(3) = 4³ – 1 = 63 which is divisible by 3.

Let P(k) = 4^k – 1 be divisible by 3,

So, we get,

⇒ 4^k – 1 = 3x.

Now, we also get that,

⇒ P(k + 1) = 4^k+1 – 1

= 4(3x + 1) – 1

= 12x + 3 is divisible by 3.

⇒ P(k + 1) is true when P(k) is true

Therefore, by Mathematical Induction,

P(n) = 4ⁿ – 1 is divisible by 3 is true for each natural number n.

P(n) = n³ – 7n + 3 is divisible by 3.

So, substituting different values for n, we get,

P(0) = 0³ – 7 × 0 + 3 = 3 which is divisible by 3.

P(1) = 1³ – 7 × 1 + 3 = −3 which is divisible by 3.

P(2) = 2³ – 7 × 2 + 3 = −3 which is divisible by 3.

P(3) = 3³ – 7 × 3 + 3 = 9 which is divisible by 3.

Let P(k) = k³ – 7k + 3 be divisible by 3.

So, we get,

⇒ k³ – 7k + 3 = 3x.

Now, we also get that,

⇒ P(k + 1) = (k + 1)³ – 7(k + 1) + 3

= k³ + 3k² + 3k + 1 – 7k – 7 + 3

= 3x + 3(k² + k – 2) is divisible by 3.

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n³ – 7n + 3 is divisible by 3, for all natural numbers n.

P(n) = xⁿ – yⁿ is divisible by x – y, x integers with x ≠ y.

So, substituting different values for n, we get,

P(0) = x⁰ – y⁰ = 0 Which is divisible by x − y.

P(1) = x − y Which is divisible by x − y.

P(2) = x² – y²

= (x + y)(x − y) Which is divisible by x − y.

P(3) = x³ – y³

= (x − y)(x² + xy + y²) Which is divisible by x − y.

Let P(k) = x^k – y^k be divisible by x – y;

So, we get,

⇒ x^k – y^k = a(x − y).

Now, we also get that,

⇒ P(k + 1) = x^k+1 – y^k+1

= x^k(x − y) + y(x^k − y^k)

= x^k(x − y) + y^a(x − y) Which is divisible by x − y.

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) xⁿ – yⁿ is divisible by x – y, where x integers with x ≠ y which is true for any natural number n.

P(n) = n³ – n is divisible by 6.

So, substituting different values for n, we get,

P(0) = 0³ – 0 = 0 Which is divisible by 6.

P(1) = 1³ – 1 = 0 Which is divisible by 6.

P(2) = 2³ – 2 = 6 Which is divisible by 6.

P(3) = 3³ – 3 = 24 Which is divisible by 6.

Let P(k) = k³ – k be divisible by 6.

So, we get,

⇒ k³ – k = 6x

Now, we also get that,

⇒ P(k + 1) = (k + 1)³ – (k + 1)

= (k + 1)(k²+ 2k + 1 − 1)

= k³ + 3k² + 2k

= 6x + 3k(k + 1) ......[n(n + 1) is always even and divisible by 2]

= 6x + 3 × (2y) Which is divisible by 6, where y = k(k + 1)

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n³ – n is divisible by 6, for each natural number n.

P(n) = n(n² + 5) is divisible by 6.

So, substituting different values for n, we get,

P(0) = 0(0² + 5) = 0 Which is divisible by 6.

P(1) = 1(1² + 5) = 6 Which is divisible by 6.

P(2) = 2(2² + 5) = 18 Which is divisible by 6.

P(3) = 3(3² + 5) = 42 Which is divisible by 6.

Let P(k) = k(k² + 5) be divisible by 6.

So, we get,

⇒ k(k² + 5) = 6x

Now, we also get that,

⇒ P(k + 1) = (k + 1)((k + 1)² + 5) = (k + 1)(k² + 2k + 6)

= k³ + 3k² + 8k + 6

= 6x + 3k² +3k + 6

= 6x + 3k(k + 1) + 6[n(n + 1) is always even and divisible by 2]

= 6x + 3 × 2y + 6 Which is divisible by 6.

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = n(n² + 5) is divisible by 6, for each natural number n.

P(n) is n² < 2ⁿ for n ≥ 5.

Let P(k) = k² < 2^k be true.

⇒ P(k + 1) = (k + 1)²

= k² + 2k + 1

2^k+1 = 2(2^k) > 2k²

Since, n² > 2n + 1 for n ≥ 3.

We get that,

k² + 2k + 1 < 2k²

⇒ (k + 1)² < 2^(k+1)

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction, P(n) = n² < 2ⁿ is true for all natural numbers n ≥ 5.

P(n) is 2n < (n + 2)!

So, substituting different values for n, we get,

P(0) ⇒ 0 < 2!

P(1) ⇒ 2 < 3!

P(2) ⇒ 4 < 4!

P(3) ⇒ 6 < 5!

Let P(k) = 2k < (k + 2)! is true;

Now, we get that,

⇒ P(k + 1) = 2(k + 1)((k + 1) + 2))!

We know that,

[(k + 1) + 2)! = (k + 3)! = (k + 3)(k + 2)(k + 1) ............. 3 × 2 × 1]

But, we also know that,

= 2(k + 1) × (k + 3)(k + 2) ............ 3 × 1 > 2(k + 1)

Therefore, 2(k + 1) < ((k + 1) + 2)!

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction,

P(n) = 2n < (n + 2)! Is true for all natural number n.

We have b₀ = 5 and b_k = 4 + b_{k – 1}

⇒ b₀ = 5, b₁ = 4 + b₀ = 4 + 5 = 9

And b₂ = 4 + b₁ = 4 + 9 = 13

Let P(n) : bn = 5 + 4n

Step 1: P(1) : b₁ = 5 + 4 = 9 

⇒ 9 = 9 which is true.

Step 2: P(k): b_k = 5 + 4k

Let it be true ∀ k ∈ N.

Step 3: Given that P(k) = 4 + b_{k – 1}

⇒ P(k + 1) = 4 + b_k+1–1

⇒ P(k + 1) = 4 + bk = 4 + 5 + 4k

⇒ P(k + 1) = 5 + 4(k + 1) which is true for P(k + 1).

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

Given that: d₁ = 2 and d_k = `(d_(k - 1))/k`

Let P(n): d_n = `2/(n!)`

Step 1: P(1) : d₁ = `2/(1!)` = 2 which is true for P(1).

Step 2: P(k) : d_k = `2/(k!)`. Let it be true for P(k).

Step 3: Given that: d_k = `(d_(k - 1))/k`

∴ d_k+1 = `(d_(k + 1 - 1))/(k + 1) = d_k/(k + 1)`

⇒ d_k+1 = `1/(k + 1) . d_k = 1/(k + 1) . 2/(k!)`

⇒ d_k+1 = `2/((k + 1)!)` Which is true for P(k + 1).

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

Let P(n): cosθ cos2θ cos2²θ ... cos2^n–1θ = `(sin 2^n theta)/(2^n sin theta)`, ∀ n ∈ N.

Step 1: P(1): cosθ = `(sin 2^1 theta)/(2^1 sin theta)`

= `(sin 2theta)/(2sin theta)`

= `(2sin theta cos theta)/(2sin theta)`

= cosθ

⇒ cosθ = cosθ which is true for P(1)

Step 2: P(k): cosθ.cos2θ.cos2²θ ... cos2^{k – 1}θ = `(sin 2^k theta)/(2^k sin theta)`

Let it be true for P(k).

Step 3: P(k + 1): cosθ.cos2θ.cos2²θ ... cos2^{k – 1}θ . cos`2^(("k"+1)–1`θ

= `(sin 2^k theta)/(2^k sin theta) . cos 2^((k + 1) - 1)theta`

=  `(sin 2^k theta)/(2^k sin theta) . cos 2^ktheta`

= `(2 sin 2^k theta . cos 2^k theta)/(2.2^k sin theta)`

= `(sin 2.2^k theta)/(2^(k + 1) sin theta)`  .....[∵ 2 sinθ cosθ = sin2θ]

= `(sin 2^(k + 1)theta)/(2^(k + 1) sin theta)` which is true for P(k + 1).

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

Let P(n): cos α + cos(α + β) + cos(α + 2β) + ... + cos(α + (n – 1)β) = `(cos(alpha + ((n - 1)/2)beta)sin((nbeta)/2))/(sin  beta/2)`

Step 1: P(1): cos α = `((cos alpha)(sin  beta/2))/(sin  beta/2)` = cos α

Step 2: P(k): cos α + cos(α + β) + cos(α + 2β) + ... + cos[α + (k – 1)β]

= `(cos[alpha + ((k - 1)/2)beta]sin((kbeta)/2))/(sin  beta/2)`. Let it be true.

Step 3: P(k + 1): cos α + cos(α + β) + cos(α + 2β) + ... + cos[α + (k – 1)β] + cos[α + (k + 1 – 1)β]

= `(cos[alpha + ((k - 1)/2)beta]sin((kbeta)/2))/(sin  beta/2) + cos(alpha + kbeta)`   ......(From Step 2)

= `(2cos[alpha + ((k - 1)/2)beta]sin((kbeta)/2) + 2cos(alpha + kbeta).sin  beta/2)/(2 sin  beta/2)`

= `(sin[alpha + kbeta - beta/2] - sin[alpha - beta/2] + sin[alpha + kbeta + beta/2] - sin[alpha + kbeta - beta/2])/(2sin  beta/2)`  ......[∵ 2 cosA sinB = sin(A + B) – sin(A – B)]

= `(sin[alpha + kbeta + beta/2] - sin(alpha - beta/2))/(2sin  beta/2)`

= `(2cos(alpha + (kbeta)/2) sin(k + 1)  beta/2)/(2sin  beta/2)`  ......`[because sin"A" - sin"B" = 2cos  ("A" + "B")/2 . sin  ("A" - "B")/2]`

= `(cos(alpha + (kbeta)/2).sin(k + 1) beta/2)/(sin  beta/2)`

= `(cos[alpha + ((k + 1 - 1)/2)beta] sin((k + 1)/2)beta)/(sin  beta/2)` which is true for P(k + 1).

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

Let P(n): `n^5/5 + n^3/3 + (7n)/15`, ∀ n ∈ N.

Step 1: P(1): `1^5/5 + 1^3/3 + (71)/15`

= `(3 + 5 + 7)/15`

= `15/13`

= 1 ∈ N

Which is true for P(1).

Step 2: P(k): `k^5/5 + k^3/3 + (7.k)/15`

Let it be true for P(k) and let `k^5/5 + k^3/3 + (7k)/15` = λ.

Step 3: P(k + 1) = `(k + 1)^5/5 + (k + 1)^3/3 + (7(k + 1))/15`

= `1/5 [k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1] + 1/3 [k^3 + 3k^2 + 3k + 1]`

= `(k^5/5 + k^3/3 + (7k)/15) + (k^4 + 2k^3 + 2k) + 1/5 + 1/3 + 7/15 + 71/15  k + 7/15`

= `lambda + k^4 + 2k^3 + 3k^2 + 2k + 1`  ....[From step 2]

= Positive integers

= Natural number

Which is true for P(k + 1).

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

P(n) = 2³ⁿ – 1 is divisible by 7.

So, substituting different values for n, we get,

P(0) = 2⁰ – 1 = 0 which is divisible by 7.

P(1) = 2³ – 1 = 7 which is divisible by 7.

P(2) = 2⁶ – 1 = 63 which is divisible by 7.

P(3) = 2⁹ – 1 = 512 which is divisible by 7.

Let P(k) = 2^3k – 1 be divisible by 7

So, we get,

⇒ 2^3k – 1 = 7x.

Now, we also get that,

⇒ P(k + 1) = `2^(3("k"+1))` – 1

= 2³(7x + 1) – 1

= 56x + 7

= 7(8x + 1) is divisible by 7.

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction, P(n) = 2³ⁿ – 1 is divisible by 7, for all natural numbers n.

P(n) = 7ⁿ – 2ⁿ is divisible by 5.

So, substituting different values for n, we get,

P(0) = 7⁰ – 2⁰ = 0 Which is divisible by 5.

P(1) = 7¹ – 2¹ = 5 Which is divisible by 5.

P(2) = 7² – 2² = 45 Which is divisible by 5.

P(3) = 7³ – 2³ = 335 Which is divisible by 5.

Let P(k) = 7^k – 2^k be divisible by 5.

So, we get,

⇒ 7^k – 2^k = 5x

Now, we also get that,

⇒ P(k + 1)= 7^k+1 – 2^k+1

= (5 + 2)7^k – 2(2^k)

= 5(7^k) + 2(7^k – 2^k)

= 5(7^k) + 2(5x) Which is divisible by 5.

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction, P(n) = 7ⁿ – 2ⁿ is divisible by 5 is true for each natural number n.

P(n) is 1 + 2 + 2² + … 2ⁿ = 2ⁿ⁺¹ – 1.

So, substituting different values for n, we get,

P(0) = 1 = 2⁰⁺¹ − 1 Which is true.

P(1) = 1 + 2 = 3 = 2¹⁺¹ − 1 Which is true.

P(2) = 1 + 2 + 2² = 7 = 2²⁺¹ − 1 Which is true.

P(3) = 1 + 2 + 2² + 2³ = 15 = 2³⁺¹ − 1 Which is true.

Let P(k) = 1 + 2 + 2² + … 2^k = 2^k+1 – 1 be true;

So, we get,

⇒ P(k + 1) is 1 + 2 + 2² + … 2^k + 2^k+1 = 2^k+1 – 1 + 2^k+1

= 2 × 2^{k + 1} – 1

= `2^(("k" + 1) + 1` – 1

⇒ P(k + 1) is true when P(k) is true.

Therefore, by Mathematical Induction, 1 + 2 + 2² + … 2ⁿ = 2ⁿ⁺¹ – 1 is true for all natural numbers n.

Let P(n) : 1 + 5 + 9 + … + (4n – 3) = n(2n – 1), for all natural numbers n.

P(1): 1 = 1(2 × 1 – 1) = 1, which is true.

Hence, P(1) is true.

Let us assume that P(n) is true for some natural number n = k.

∴ P(k) : 1 + 5 + 9 + … + (4k – 3) = k(2k – 1)   .......(i)

Now, we have to prove that P(k + 1) is true.

P(k + 1) : 1 + 5 + 9 + … + (4k – 3) + [4(k + 1) – 3]

= 2k² – k + 4k + 4 – 3

= 2k² + 3k + 1

= (k + 1)( 2k + 1)

= (k + 1)[2(k + 1) – 1]

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

So, by the principle of mathematical induction P(n) is true for any natural number n.