Principle Of Mathematical Induction

Given; P(n) which it true for all n ≥ 4 but P(1), P(2) and P(3) are not true

Let P(n) be 2ⁿ < n!

This statement is true for all n ≥ 4 but P(1), P(2) and P(3) are not true.

i.e P(0) ⇒ 2⁰ < 0! i.e 1 < 1 Which is not true

P(1) ⇒ 2¹ < 1! i.e 2 < 1 Which is not true

P(2) ⇒ 2² < 2! i.e 4 < 2 Which is not true

P(3) ⇒ 2³ < 3! i.e 8 < 6 Which is not true

P(4) ⇒ 2⁴ < 4! i.e 16 < 24 Which is true

P(5) ⇒ 2⁵ < 5! i.e 32 < 60 Which is true

And so on.

Given; P(n) which is true for all n.

Let P(n) be

⇒ P(k) which is true for all k.

∴ P(n) which is true for all n.

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

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

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

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

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

Let P(k) = 4^k – 1 is divisible by 3;

⇒ 4^k – 1 = 3x.

⇒ 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

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

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

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

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

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

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

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

⇒ 2^3k – 1 = 7x.

⇒ 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.

∴ By Mathematical Induction P(n) = 2³ⁿ – 1 is divisible by7, for all natural numbers n.

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

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

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

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

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

Let P(k) = k³ – 7k + 3 is divisible by 3; ⇒ k³ – 7k + 3 = 3x.

⇒ 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.

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

Given; P(n) = 3²ⁿ – 1 is divisible by 8.

P(0) = 3⁰ – 1 = 0; is divisible by 8.

P(1) = 3² – 1 = 8; is divisible by 8.

P(2) = 3⁴ – 1 = 80; is divisible by 8.

P(3) = 3⁶ – 1 = 728; is divisible by 8.

Let P(k) = 3^2k – 1 is divisible by 8; ⇒ 3^2k – 1 = 8x.

⇒ P(k+1) = 3^2(k+1) – 1 = 3²(8x + 1) – 1 = 72x + 8; is divisible by 8.

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

∴ By Mathematical Induction P(n) = 3²ⁿ – 1 is divisible by 8, for all natural numbers n.

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

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

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

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

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

Let P(k) = 7^k – 2^k is divisible by 5; ⇒ 7^k – 2^k = 5x.

⇒ 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); is divisible by 5.

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

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

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

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

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

P(2) = x² – y²

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

P(3) = x³ – y³

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

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

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

⇒ 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); is divisible by x − y.

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

∴ By Mathematical Induction P(n) xⁿ – yⁿ is divisible by x – y, where x integers with x ≠ y; is true for any natural number n.

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

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

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

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

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

Let P(k) = k³ – k is divisible by 6.; ⇒ k³ – k = 6x.

⇒ 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 ; is divisible by 6.

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

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

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

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

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

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

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

Let P(k) = k(k² + 5) is divisible by 6.; ⇒ k(k² + 5) = 6x.

⇒ 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 ; is divisible by 6.

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

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

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

Let P(k) = k² < 2^k is true;

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

= k² + 2k + 1

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

∵ n² > 2n + 1 for n ≥3

∴ k² + 2k + 1 < 2k²

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

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

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

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

P(0) ⇒ 0 < 2!

P(1) ⇒ 2 < 3!

P(2) ⇒ 4 < 4!

P(3) ⇒ 6 < 5!

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

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

((k+1)+2)! = (k+3)! = (k+3)(k+2)(k+1)……………3×2×1

= 2(k+1) × (k+3)(k+2)……………3×1

> 2(k+1)

∴ 2(k+1) < ((k+1) + 2)!

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

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

Given;

Let

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

∴ By Mathematical Induction Is true for all natural number n≥2.

Given; P(n) is 2 + 4 + 6 + …+ 2n = n² + n.

P(0) = 0 = 0² + 0 ; it’s true.

P(1) = 2 = 1² + 1 ; it’s true.

P(2) = 2 + 4 = 2² + 2 ; it’s true.

P(3) = 2 + 4 + 6 = 3² + 2 ; it’s true.

Let P(k) be 2 + 4 + 6 + …+ 2k = k² + k is true;

⇒ P(k+1) is 2 + 4 + 6 + …+ 2k + 2(k+1) = k² + k + 2k +2

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

= (k + 1)² + (k + 1)

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

∴ By Mathematical Induction 2 + 4 + 6 + …+ 2n = n² + n is true for all natural numbers n.

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

P(0) = 1 = 2⁰⁺¹ − 1 ; it’s true.

P(1) = 1 + 2 = 3 = 2¹⁺¹ − 1 ; it’s true.

P(2) = 1 + 2 + 2² = 7 = 2²⁺¹ − 1 ; it’s true.

P(3) = 1 + 2 + 2² + 2³ = 15 = 2³⁺¹ − 1 ; it’s true.

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

⇒ 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.

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

Given; P(n) is 1 + 5 + 9 + …+(4n – 3) = n (2n – 1).

P(1) = 1 = 1(2−1) ; it’s true.

P(2) = 1 + 5 = 6 =2(4−1) ; it’s true.

P(3) = 1 + 5 + 9 = 15 = 3(6−1) ; it’s true.

Let P(k) be 1 + 5 + 9 + …+(4k – 3) = k (2k – 1) is true;

⇒ P(k+1) is 1 + 5 + 9 + …+(4k – 3) + (4(k+1)−3)

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

= 2k² – k + 4k + 1

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

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

∴ By Mathematical Induction 1 + 5 + 9 + …+(4n – 3) = n (2n – 1) is true for all natural numbers n.

Given; a₁ = 3 and a_k = 7a_k–1

⇒ a₂ = 7 × a₁ = 7 × 3 = 21 = 3.7^2-1

⇒ a₃ = 7 × a₂ = 7² × a₁ = 49 × 3 = 147 = 3.7^3-1

⇒ a₄ = 7 × a₃ = 7² × a₂ = 7³ × a₁ = 343 × 3 = 1029 = 3.7^4-1

⇒ a_n = 7a_n-1 = 3.7^n-1

Let a_m = 7a_m-1 = 3.7^m-1 be true.

⇒ a_m+1 = 7a_m+1-1 = 7a_m = 7.3.7^m-1 = 3.7^(m+1)-1

⇒ a_m+1 is true when a_m is true.

∴ By Mathematical Induction a_n = 3.7^n–1 is true for all natural numbers n.

Given; A sequence b₀, b₁, b₂ ... is defined by letting b₀ = 5 and b_k = 4 + b_{k – 1} for all natural numbers k.

⇒ b₁ = 4 + b₀

= 4 + 5 = 9

= 5 + 4.1

⇒ b₂ = 4 + b₁

= 4 + 9

= 13

= 5 + 4.2

⇒ b₃ = 4 + b₂

= 4 + 13

= 17

= 5 + 4.3

Let b_m = 4 + b_m-1 = 5 + 4m be true.

⇒ b_m+1 = 4 + b_m+1-1

= 4 + b_m

= 4 + 5 + 4m

= 5 + 4(m+1)

⇒ b_m+1 is true when b_m is true.

∴ By Mathematical Induction b_n = 5 + 4n is true for all natural numbers n.

Given; A sequence d₁, d₂, d₃ …. Is defined by letting d₁ = 2 and .

⇒ d_m+1 is true when d_m is true.

∴ By Mathematical Induction is true for all natural numbers n.

Given;

⇒ When n=1 :

It’s true at n = 1.

⇒ When n=2 :cos α+cos(α+(2-1)β) = cos α+cos (α+β)

=cos α+cos(α+β)

It’s true at n = 2.

⇒ When n=3: cos α+cos(α+β)+cos(α+2β)

=cos α+cos(α+2β)+cos(α+β)=2 cos(α+β) cos β+cos(α+β)

It’s true at n = 3.

Let n=k

Be true

⇒ at n=k+1

Cos α +cos (α + β)+cos(α + 2β)+ …. +cos(α + (k – 1)β)+cos(α+(k+1-1)β)

⇒ It’s true at n = k+1.

∴ By Mathematical Induction

is true for all natural numbers n.

Given; P(n) : cos θ cos 2θ cos2²θ ….. cos 2^n–1θ =

⇒ When n=1 :

It’s true at n = 1.

⇒ When n=2: cos θ cos 2θ

It’s true at n = 2.

⇒ When n=3 :cos θ cos 2θ cos 4θ

It’s true at n = 3.

Let n=k

Be true

⇒ at n=k+1

⇒ It’s true at n = k+1.

∴ By Mathematical Induction cos θ cos 2θ cos2²θ ….. cos 2^n–1θ = is true for all natural numbers n.

Given; Given; P(n) : sinθ + sin 2θ + sin 3θ + …. + sin nθ

⇒ When n=1:

It’s true at n = 1.

Let n=k

Be true

⇒ at n=k+1

Sin θ +sin 2θ+sin 3θ+ …. +sin kθ + sin (k+1) θ

⇒ It’s true at n = k+1.

∴ By Mathematical Induction sin θ + sin 2θ + sin 3θ + …. + sin nθ is true for all natural numbers n.

Given;

=1 which is true

=10;It' s true

=59; It' s true

be a natural number

i.e. It's true

which is a real number.

⇒ P(k+1) is true.

∴ By Mathematical Induction is a natural numbers.

Given;

⇒ P(k+1) is true.

∴ By Mathematical Induction is true for natural numbers n>1.

To prove; Number of subsets of a set containing n distinct elements is 2ⁿ.

For a null set there is only one element Φ and therefore only one subset.

⇒ at n = 0 number of subsets = 1 = 2⁰

By considering a set with 1 element there will be 2 subsets with 1 and Φ

⇒ at n = 0 number of subsets = 2 = 2²

By considering a set S_k with k element

Let at n = k number of subsets = 2^k be true.

For a set S_k+1 containing k+1 element

The extra one element in set S_k+1 when compared with S_k will form an extra collection of subsets by combing with the existing 2^k subsets and as a result an extra 2^k subsets are formed.

⇒ at n = k+1 number of subsets = 2^k + 2^k = 2.2^k = 2^k+1

⇒ P(k+1) is true.

∴ By Mathematical Induction number of subsets of a set containing n distinct elements is 2ⁿ, for all n ϵ N.

Given; Given; P(n): 10ⁿ + 3.4ⁿ⁺² + k is divisible by 9.

P(1) = 10 +3.4³ + k = 202 + k

For this number to be divisible by 9; sum of its digits should be 9 or multiples of 9.

⇒ 2 + 2 + k = 9

∴ k = 5

Given; P(n): 3.5^{2n + 1} + 2^{3n + 1}

⇒ P(1) = 3.5²⁺¹ + 2^{3 + 1} = 375 + 16 = 391 = 17 × 23

⇒ P(2) = 3.5⁴⁺¹ + 2⁶⁺¹ = 9375 + 256 = 9503 = 17 × 559

These are divisible by 17

Given; P(n): xⁿ – 1 is divisible by x – k

⇒ P(1) : x – 1

⇒ P(2) : x² – 1 = (x−1)(x+1)

⇒ P(3) : x³ – 1 = (x−1)(x²+xy+1)

⇒ P(4) : x⁴ − 1 = (x²−1)(x²+1) = (x−1)(x+1)(x²+1)

∴ The least positive integral value of k is 1.

Given; P(n): 2n < n! n ϵ N

⇒ P(1) : 2×1<1! ⇒ 2<1; it’s not true.

⇒ P(2) : 2×2<2! ⇒ 4<2; it’s not true.

⇒ P(3) : 2×3<3! ⇒ 6<6; it’s not true.

⇒ P(4) : 2×4<4! ⇒ 8<24; it’s true.

⇒ P(3) : 2×5<5! ⇒ 10<120; it’s true.

∴ n≥4

True; This is the principle of mathematical induction.