Principles of Mathematical Induction MCQ Quiz - Objective Question with Answer for Principles of Mathematical Induction - Download Free PDF

Concept:

Suppose there is a given statement P (n) involving the natural number n such that

• The statement is true for n = 1, i.e., P(1) is true, and
• If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., truth of P (k) implies the truth of P (k + 1).

Then, P (n) is true for all natural numbers n

Calculation:

We have to find 7ⁿ – 3ⁿ is divisible by which number

Consider P (n): 7n – 3n

P (1): 7¹ − 3¹ = 4

Thus, 7n – 3n is divisible by 4

Let P (k) is true for n = K

⇒ 7^k − 3^k is divisible by 4

So, 7n – 3n = 4d

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

⇒ 7^(k+1) − 3^(k+1) = 7^(k+1) −7.3^k + 7.3^k − 3^(k+1)

= 7(7^k − 3^k) + (7 − 3)3^k

= 7(4d) + (7 − 3)3^k

= 7(4d) + 4.3^k

= 4(7d + 3^k)​

Concept:

Principle of mathematical induction: Let P(n) be the statement. 

P(n) is true for n = 1. Let P(n) is true for n = k then if P(n) is true for n = k + 1 then P(n) is true for all natural numbers n.

Also, for n ≥ 3, n² > 2n + 1 [This can be proved using the Principle of mathematical induction.]

Explanation: 

Given Statement: n2 < 2n

• For n = 1: 1² < 2¹, which is true.
• For n = 2: 2² < 2², which is not true.
• For n = 3: 3² < 2³, which is not true.
• For " id="MathJax-Element-9-Frame" role="presentation" style="position: relative;" tabindex="0">
  n = 4: 4² < 2⁴, which is not true.
• For " id="MathJax-Element-10-Frame" role="presentation" style="position: relative;" tabindex="0">
  n = 5: 5² < 2⁵, which is true.
• For n = 6: 62 < 26, which is true.

Now, let's prove it for all natural numbers greater than 5.

Base Case (n = 5):

\(5^2 = 25 < 2^5 = 32\)

Which is true.

Let's assume for some arbitrary k ≥ 5, it holds that \( k^2 < 2^k\).

We need to show that \((k+1)^2 < 2^{k+1}\).

\( k^2 < 2^k\)

Multiply both sides by 2, we get

\(2k^2 < 2^{k+1}\)

⇒ \(k^2 + k^2 < 2^{k+1}\)

As \(k^2 > 2k + 1\)

⇒ \(k^2 + 2k + 1 < 2^{k+1}\)

⇒ \((k+ 1)^2 < 2^{k+1}\)

Which is the required result.

Thus, Given inequality holds true for all natural numbers greater than or equal to 5.

Thus,  Option 1 is the correct answer.

Concept:

Principle of mathematical induction: Let P(n) be the statement. 

P(n) is true for n = 1. Let P(n) is true for n = k then if P(n) is true for n = k + 1 then P(n) is true for all natural numbers n.

Also, for n ≥ 3, n² > 2n + 1 [This can be proved using the Principle of mathematical induction.]

Explanation: 

Given Statement: n2 < 2n

• For n = 1: 1² < 2¹, which is true.
• For n = 2: 2² < 2², which is not true.
• For n = 3: 3² < 2³, which is not true.
• For " id="MathJax-Element-9-Frame" role="presentation" style="position: relative;" tabindex="0">
  n = 4: 4² < 2⁴, which is not true.
• For " id="MathJax-Element-10-Frame" role="presentation" style="position: relative;" tabindex="0">
  n = 5: 5² < 2⁵, which is true.
• For n = 6: 62 < 26, which is true.

Now, let's prove it for all natural numbers greater than 5.

Base Case (n = 5):

\(5^2 = 25 < 2^5 = 32\)

Which is true.

Let's assume for some arbitrary k ≥ 5, it holds that \( k^2 < 2^k\).

We need to show that \((k+1)^2 < 2^{k+1}\).

\( k^2 < 2^k\)

Multiply both sides by 2, we get

\(2k^2 < 2^{k+1}\)

⇒ \(k^2 + k^2 < 2^{k+1}\)

As \(k^2 > 2k + 1\)

⇒ \(k^2 + 2k + 1 < 2^{k+1}\)

⇒ \((k+ 1)^2 < 2^{k+1}\)

Which is the required result.

Thus, Given inequality holds true for all natural numbers greater than or equal to 5.

Thus,  Option 1 is the correct answer.

Calculation

Let the statement P(n) be defined as

\(\mathrm{P}(\mathrm{n}): \frac{\mathrm{n}^{5}}{5}+\frac{\mathrm{n}^{3}}{3}+\frac{7 \mathrm{n}}{15}\) is a natural number for all n ∈ N.

Step 1 : For n = 1, P(1) : \(\frac{1}{5}+\frac{1}{3}+\frac{7}{15}\) = 1 ∈ N

Hence, it is true for n = 1.

Step II : Let it is true for n = k,

i.e. \(\rm \frac{{k}^{5}}{5}+\frac{{k}^{3}}{3}+\frac{7 {k}}{15}=λ \in \mathrm{N} \quad ...(i)\)

Step III: For n = k + 1

\(\frac{({k}+1)^{5}}{5}+\frac{({k}+1)^{3}}{3}+\frac{7({k}+1)}{15}\)

= \(\frac{1}{5}\left(k^{5}+5 k^{4}+10 k^{3}+10 k^{2}+5 k+1\right)\) + \(\frac{1}{3}\left(k^{3}+3 k^{2}+3 k+1\right)+\frac{7}{15} k+\frac{7}{15}\)

= \(\left(\frac{k^{5}}{5}+\frac{k^{3}}{3}+\frac{7}{15} k\right)+\left(k^{4}+2 k^{3}+3 k^{2}+2 k\right)\) + \(\frac{1}{5}+\frac{1}{3}+\frac{7}{15}\)

= λ + k⁴ + 2k³ + 3k² + 2k + 1

[using equation (i)]

which is a natural number, since λk ∈ N. Therefore, P(k + 1) is true, when P(k) is true, Hence, from the principle of mathematical induction, the statement is true for all natural numbers n.

Hence option 4 is correct

\( \Rightarrow 2^{4n} = 1 + nC_1 \cdot 15 + nC_2 \cdot 15^2 + nC_3 \cdot 15^3 + \ldots \)

\( \Rightarrow 2^{4n} - 1 - 15n = 15^2 [nC_2 + nC_3 \cdot 15 + \ldots] \)

\( = 225K, \text{ where } K \text{ is an integer.} \)

Hence \( 2^{4n} - 1 - 15n \) is divisible by 225.

Concepts:

Suppose there is a given statement P (n) involving the natural number n such that

• The statement is true for n = 1, i.e., P (1) is true, and
• If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., truth of P (k) implies the truth of P (k + 1).

Then, P (n) is true for all natural numbers n

Calculation:

Given:

P (n) = 121ⁿ – 25ⁿ + 1900ⁿ – (-4) ⁿ

Now, P (1) = 121¹ – 25¹ + 1900¹ – (-4)¹

⇒ P (1) = 121 – 25 + 1900 + 4

⇒ P (1) = 2000

Calculation:

S = 72n + 16n - 1

For n = 1

S = 49 + 16 - 1 = 64

For n = 2 

S = 2401 + 32 - 1 = 2432 = 64 × 32, which is divisible by 64

∴ Option 1 is correct

Concept:

Suppose there is a given statement P (n) involving the natural number n such that

• The statement is true for n = 1, i.e., P(1) is true, and
• If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., truth of P (k) implies the truth of P (k + 1).

Then, P (n) is true for all natural numbers n

Calculation:

We have to find 7ⁿ – 3ⁿ is divisible by which number

Consider P (n): 7n – 3n

P (1): 7¹ − 3¹ = 4

Thus, 7n – 3n is divisible by 4

Let P (k) is true for n = K

⇒ 7^k − 3^k is divisible by 4

So, 7n – 3n = 4d

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

⇒ 7^(k+1) − 3^(k+1) = 7^(k+1) −7.3^k + 7.3^k − 3^(k+1)

= 7(7^k − 3^k) + (7 − 3)3^k

= 7(4d) + (7 − 3)3^k

= 7(4d) + 4.3^k

= 4(7d + 3^k)​

Formula used:

1. (x + y)ⁿ = ⁿC₀ (xⁿ) (y⁰) + ⁿC₁ (x^n-1)y + ......ⁿC_n (x⁰)(yⁿ)

2. ⁿC_r = ⁿC_n-r

3. nC0 = 1

4. ⁿC₁ =  n

Calculations:

Let y = 4n - 3n - 1 

⇒ y = (1 + 3)n - 3n - 1 

By using the above formula

⇒ y = nC0 (1n) (30) + nC1 (1)n-1(3¹) + ......nCn (10)(3n) - 3n - 1

Again, using the formula (1), (2) & (3)

⇒ y = nC0 + nC1 (3) + nC₂ (3²) + ......nC_n (3n) - 3n - 1

⇒ y = 1 + 3n + ⁿC₂ 3² + .....+ nCn3ⁿ - 3n - 1

⇒ y = 3²(nC2 32 + ⁿC₃3³ .....+ nCn3n) 

⇒ y = 9 × Integer

∴ 4n - 3n - 1 is always divisible by 3 & 9 both.

Alternate Method

Since, n is positive, put n = 1, 2, 3....

Put n = 1

⇒ 41 - 3(1) - 1 = 4 - 3 - 1 = 0

Which is divisible by 3, 9, 8, 27

Put n = 2,

⇒ 42 - 3(2) - 1 = 16 - 6 - 1 = 9

Which is divisible by 3, 9

Put n = 3

⇒ 43 - 3(3) - 1 = 64 - 9 - 1 = 54

Which is divisible by 3, 9, 27

Put n = 4, 

⇒ 44 - 3(4) - 1 = 256 - 12 - 1 = 243

Which is divisible by 3, 9, 27

Put n = 5, 

⇒ 45 - 3(5) - 1 = 1024 - 15 - 1 = 1008 ,

Which is divisible by 3, 9, 27

Continued so on....

∴ 4n - 3n - 1 is always divisible by 3 & 9 both

Note: This is BSF RO Official Paper (Conducted on 22-Sep-2019) official paper and there were options 3, 9, 8 & 27 in the option. Since the relation is satisfied for both 3 & 9 therefore, we have changed the option. 

Concepts:

Principle of Mathematical Induction:

Suppose there is a given statement P (n) involving the natural number n such that

• The statement is true for n = 1, i.e., P (1) is true, and
• If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., the truth of P (k) implies the truth of P (k + 1). 

Then, P (n) is true for all natural numbers n

Calculation:

Given

P(n) = 2 + 4 + ......+ 2n

Put n = 1

P(1) = 2

Hence, P(n) = n(n + 1) + 2 is not true for n = 1 

So, The Principle of Mathematical Induction is not applicable and nothing can be said about the validity of the statement P(n) = n(n + 1) + 2

Concept:

Let us suppose, P(n) = 7n - 2n .

If n =1, then P(1) = 5

⇒ For, n = 1 we can conclude that P(n) is divisible by 5

Let us assume, for some positive integer k, P(k) = 7k - 2k is divisible by 5

⇒ 7k - 2k = 5 × d where d ∈ N.

Now, we have to show P(k + 1) is also true whenever P(k) is true.

P(k + 1) = 7(k + 1) - 2(k + 1) 

⇒ P(k + 1) = 7(k + 1) - 3(k + 1) = 7(k + 1) - 7 × 2k + 7 × 2k - 2(k + 1) 

⇒ P(k + 1) = 7 × (7k - 2k) + 2k × (7 - 2)

We know that P(k) is true i.e 7k - 2k = 5 × d where d ∈ N

⇒ P(k + 1) = 7 × (5d) + 2k × 5

⇒ P(k + 1) = 5 × (7d + 2k)

⇒ P(k + 1) = 5 × q where q = (7d + 2k)

Hence, P(k + 1) is also divisible by 5.

So, P(n) = 7n - 2n  is divisible by 5 for all positive integers n.

Shortcut Trick

P(n) = 7ⁿ – 2ⁿ

Put n = 1

7n – 2ⁿ = 7¹ – 2¹ = 7 – 2 = 5

which is divisible by 5

Put n = 2

7ⁿ – 2ⁿ = 7² – 2² = 49 – 4 = 45 (divisible by 5)

which is 

Put n = 3

7ⁿ – 2ⁿ = 7³ – 2³ = 343 – 8 = 335 (divisible by 5)

Hence, for any natural number n, 7ⁿ – 2ⁿ is divisible by 5

Concepts:

Suppose there is a given statement P (n) involving the natural number n such that

• The statement is true for n = 1, i.e., P (1) is true, and
• If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., truth of P (k) implies the truth of P (k + 1).

Then, P (n) is true for all natural numbers n

Calculation:

Given: 

P(n) = \(\rm 2.4^{2n+1}+3^{3n+1}\)

Take n = 1

P(1) = \(\rm 2.4^{2 \times 1+1}+3^{3\times 1+1} = \rm 2.4^3 + 3^4=209 = 11 \times 19\)

Therefore we can say that P (n) is divisible by 11

Concept:

• Mathematical induction: It is a technique of proving a statement, theorem, or formula which is assumed to be true, for every natural number n.
• By generalizing this in the form of a principle that we would use to prove any mathematical statement is called the principle of mathematical induction.

Calculations:

Consider

\(\frac{1}{1.2.3}+\frac{1}{2.3.4}+\frac{1}{3.4.5}+....+\frac{1}{n(n+1)(n+2)}\)

Clearly, the r^th term from the above series is 

Let the r^th term be \(u_r=\frac{1}{r(r+1)(r+2)}\)   ....(1)

now multiply and divide by 2 in (1)

⇒ \(u_r=\frac{1\times 2}{2r(r+1)(r+2)}\)

⇒ \(u_r=\frac{2}{2r(r+1)(r+2)}\)

add and subtract r in the numerator

⇒ \(u_r=\frac{(r+2) - r}{2r(r+1)(r+2)}\)

⇒ \(u_r=\frac{1}{2}\big[\frac{(r+2) }{r(r+1)(r+2)}- \frac{r }{r(r+1)(r+2)}\big]\)

⇒ \(u_r=\frac{1}{2}\big[\frac{1}{r(r+1)}- \frac{1}{(r+1)(r+2)}\big]\)   (2)

Now put r = 1 in (2), then we have

\(u_1=\frac{1}{2}\big[\frac{1}{1.2}- \frac{1}{2.3}\big]\)     

put r = 2 in (2)

⇒ \(u_2=\frac{1}{2}\big[\frac{1}{2.3}- \frac{1}{3.4}\big]\)     

put r = 3 in (2)

⇒ \(u_3=\frac{1}{2}\big[\frac{1}{3.4}- \frac{1}{4.5}\big]\)

      .  .  .  .  .  .  . 

put r = n in (2) 

\(u_r=\frac{1}{2}\big[\frac{1}{n(n+1)}- \frac{1}{(n+1)(n+2)}\big]\)        

Now, add all these equations and we get

\(S_n=\displaystyle\sum_{r=1}^{n} u_r=\frac{1}{2}\bigg[\frac{1}{1.2}-\frac{1}{(n+1)(n+2)}\bigg ]\)

\(=\frac{1}{4(n+1)(n+2)}\big[(n+1)(n+2)-2\big ]\)

\(=\frac{1}{4(n+1)(n+2)}\big[(n^2+n+2n+2-2\big ]\)

\(=\frac{1}{4(n+1)(n+2)}\big[n^2+3n\big ]\)

\(=\frac{n(n+3)}{4(n+1)(n+2)}\)

Hence, the correct answer is option 4).

Concepts:

Principle of Mathematical Induction:

Suppose there is a given statement P (n) involving the natural number n such that

• The statement is true for n = 1, i.e., P (1) is true, and
• If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k + 1, i.e., the truth of P (k) implies the truth of P (k + 1). 

Then, P (n) is true for all natural numbers n

Calculation:

Given:

T(k) = 1 + 3 + 5 + ........ + (2k - 1) = k2 + 10

Put k = 1

T(1) = 2 × 1 - 1 = 1² + 10

1 ≠ 10, LHS ≠ RHS

∴ T(1) is not true

Let T(k) is true

1 + 3 + 5 + ......... + (2k - 1) = k2 + 10     ---(1)

OR, 1 + 3 + 5 + ....... + (2k - 1) + (2k + 1) = k2 + 10 + 2k + 1  Using eqn (1)

⇒ 1 + 3 + 5 + ........ + (2k - 1) + (2k + 1) = (k + 1)² + 10

∴ T(k + 1) is true

i.e T(k) is true ⇒  T(k + 1) is true (Option Two is correct)

T(n) is not true for all n ϵ N, as T(1) is not true.

Concept:

\(\rm n! = n×(n-1)×(n -2)....× 3×2×1\)

Calculation:

Given:

P(n): 3n < n!

This can be solved directly by hit and trial method, putting the option in expression and checking its validity

We will choose first the smallest number from the options

Putting n = 3

P(n) = 3n < n! = 3³ < 3!

⇒ 27 \(\nless \) 3 × 2 × 1, 27 \(\nless \) 6 , Hence Option 2 is wrong

Putting n = 6

P(n) = 3n < n! = 63 < 6!

P(n) = 3n < n! = 3⁶ < 6! , 1029 < 6 × 5 × 4 × 3 × 2 × 1

1029 \(\nless \) 720 Hence Option 3 is wrong

Put n = 7

P(n) = 3n < n! = 3⁷ < 7! , 2187 < 7 × 6 × 5 × 4 × 3 × 2 × 1

2187 < 5040, Option 1 satisfies the given expression, Hence the correct answer is option 1.