This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Principle of Mathematical Induction”.

1. What is the base case for the inequality 7^{n} > n^{3}, where n = 3?

a) 652 > 189

b) 42 < 132

c) 343 > 27

d) 42 <= 431

View Answer

Explanation: By the principle of mathematical induction, we have 7

^{3}> 3

^{3}⇒ 343 > 27 as a base case and it is true for n = 3.

2. In the principle of mathematical induction, which of the following steps is mandatory?

a) induction hypothesis

b) inductive reference

c) induction set assumption

d) minimal set representation

View Answer

Explanation: The hypothesis of Step is a must for mathematical induction that is the statement is true for n = k, where n and k are any natural numbers, which is also called induction assumption or induction hypothesis.

3. For m = 1, 2, …, 4m+2 is a multiple of ________

a) 3

b) 5

c) 6

d) 2

View Answer

Explanation: For n = 1, 4 * 1 + 2 = 6, which is a multiple of 2. Assume that 4m+2 is true for m=k and so 4k+2 is true based on the assumption. Now, to prove that 4k+2 is also a multiple of 2 ⇒ 4(k+1)+2 ⇒ 2 * 4k – 4k + 6 ⇒ 2*4k+4 – 4k+2 ⇒ 2(4k+2) – 2(2k+1). Here, the first term 2(4k+2) is true as per assumption and the second term 2(4k+2) is must to be a multiple of 2. Hence, 4(k+1)+2 is a multiple of 2. So, by induction hypothesis, (4m+2) is a multiple of 2, for m = 1,2,3,…

4. For any integer m>=3, the series 2+4+6+…+(4m) can be equivalent to ________

a) m^{2}+3

b) m+1

c) m^{m}

d) 3m^{2}+4

View Answer

Explanation: The required answer is m

^{2}+3. Now, by induction assumption, we have to prove 2+4+6+…+4(k+1) = (k+1)

^{2}+3 also can be true, 2+4+6+…+4(k+1) = 2+4+6+⋯+(4k+4) and by the subsequent steps, we can prove that (m+1)

^{2}+3 also holds for m=k. So, it is proved.

5. For every natural number k, which of the following is true?

a) (mn)^{k} = m^{k}n^{k}

b) m*k = n + 1

c) (m+n)^{k} = k + 1

d) m^{k}n = mn^{k}

View Answer

Explanation: In the first step, for k = 1, (mn)

^{1}= m

^{1}n

^{1}= mn, hence it is true. Let us assume the statement is true for k = l, Now by induction assumption, (mn)

^{1}= m

^{1}n

^{1}is true. So, to prove, (mn)

^{l+1}= m

^{l}+ 1n

^{l+1}, we have (mn)

^{l}= m

^{l}n

^{l}and multiplying both sides by (mn) ⇒ (mn)

^{1}(mn)=(m

^{1}n

^{1})(mn)

⇒ (mn)

^{l+1}= (mm

^{1})(nn

^{1}) ⇒ (mn)

^{l+1}= (m

^{l+1}n

^{l+1}). Hence, it is proved. So, (mn)

^{k}= m

^{k}n

^{k}is true for every natural number k.

6. By induction hypothesis, the series 1^{2} + 2^{2} + 3^{2} + … + p^{2} can be proved equivalent to ____________

a) \(\frac{p^2+2}{7}\)

b) \(\frac{p*(p + 1)*(2p + 1)}{6}\)

c) \(\frac{p*(p+1)}{4}\)

d) p+p^{2}

View Answer

Explanation: By principle of mathematical induction, we now assume that p (b) is true 1

^{2}+ 2

^{2}+ 3

^{2}+ … + b

^{2}= \(\frac{b (b + 1) (2b + 1)}{6}\)

so to prove P(b+1): 1

^{2}+ 2

^{2}+ 3

^{2}+ … + b

^{2}+ (b + 1)

^{2}= \(\frac{b (b + 1) (2b + 1)}{6}\) + (b + 1)

^{2}

By induction assumption it is shown that 1

^{2}+ 2

^{2}+ 3

^{2}+ … + b

^{2}+ (b + 1)

^{2}= \(\frac{(b + 1) [(b + 2) (2b + 3)]}{6}\). Hence it is proved that 1

^{2}+ 2

^{2}+ 3

^{2}+ … + p

^{2}= \(\frac{p*(p + 1)*(2p + 1)}{6}\).

7. For any positive integer m, ______ is divisible by 4.

a) 5m^{2} + 2

b) 3m + 1

c) m^{2} + 3

d) m^{3} + 3m

View Answer

Explanation: The required answer is, m

^{3}+ 3m. Now, by induction hypothesis, we have to prove for m=k, k

^{3}+3k is divisible by 4. So, (k + 1)

^{3}+ 3 (k + 1) = k

^{3}+ 3 k

^{2}+ 6 k + 4

= [k

^{3}+ 3 k] + [3 k

^{2}+ 3 k + 4] = 4M + (12k

^{2}+ 12k) – (8k

^{2}+ 8k – 4), both the terms are divisible by 4. Hence (k + 1)

^{3}+ 3 (k + 1) is also divisible by 4 and hence it is proved for any integer m.

8. According to principle of mathematical induction, if P(k+1) = m^{(k+1)} + 5 is true then _____ must be true.

a) P(k) = 3m^{(k)}

b) P(k) = m^{(k)} + 5

c) P(k) = m^{(k+2)} + 5

d) P(k) = m^{(k)}

View Answer

Explanation: By the principle of mathematical induction, if a statement is true for any number m = k, then for its successor m = k + 1, the statement also satisfies, provided the statement is true for m = 1. So, the required answer is p(k) = m

^{k}+ 5.

9. Which of the following is the base case for 4^{n+1} > (n+1)^{2} where n = 2?

a) 64 > 9

b) 16 > 2

c) 27 < 91

d) 54 > 8

View Answer

Explanation: Statement By principle of mathematical induction, for n=2 the base case of the inequation 4

^{n+1}> (n+1)

^{2}should be 64 > 9 and it is true.

10. What is the induction hypothesis assumption for the inequality m ! > 2^{m} where m>=4?

a) for m=k, k+1!>2^{k} holds

b) for m=k, k!>2^{k} holds

c) for m=k, k!>3^{k} holds

d) for m=k, k!>2^{k+1} holds

View Answer

Explanation: By the induction hypothesis, assume that p (k) = k! > 2

^{k}is true, for m=k and we need to prove this by the principle of mathematical induction.

**Sanfoundry Global Education & Learning Series – Discrete Mathematics.**

To practice all areas of Discrete Mathematics, __here is complete set of 1000+ Multiple Choice Questions and Answers__.