Discrete Mathematics Multiple Choice Questions on “Principle of Mathematical Induction”.
1. What is the base case for the inequality 7n > n3, where n = 3?
a) 652 > 189
b) 42 < 132
c) 343 > 27
d) 42 <= 431
Answer: c
Clarification: By the principle of mathematical induction, we have 73 > 33 ⇒ 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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) m2+3
b) m+1
c) mm
d) 3m2+4
Answer: a
Clarification: The required answer is m2+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 = mknk
b) m*k = n + 1
c) (m+n)k = k + 1
d) mkn = mnk
Answer: a
Clarification: In the first step, for k = 1, (mn)1 = m1n1 = mn, hence it is true. Let us assume the statement is true for k = l, Now by induction assumption, (mn)1 = m1n1 is true. So, to prove, (mn)l+1 = ml + 1nl+1, we have (mn)l = mlnl and multiplying both sides by (mn) ⇒ (mn)1(mn)=(m1n1)(mn)
⇒ (mn)l+1 = (mm1)(nn1) ⇒ (mn)l+1 = (ml+1nl+1). Hence, it is proved. So, (mn)k = mknk is true for every natural number k.
6. By induction hypothesis, the series 12 + 22 + 32 + … + p2 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+p2
Answer: b
Clarification: By principle of mathematical induction, we now assume that p (b) is true 12 + 22 + 32 + … + b2 = (frac{b (b + 1) (2b + 1)}{6})
so to prove P(b+1): 12 + 22 + 32 + … + b2 + (b + 1)2 = (frac{b (b + 1) (2b + 1)}{6}) + (b + 1)2
By induction assumption it is shown that 12 + 22 + 32 + … + b2 + (b + 1)2 = (frac{(b + 1) [(b + 2) (2b + 3)]}{6}). Hence it is proved that 12 + 22 + 32 + … + p2 = (frac{p*(p + 1)*(2p + 1)}{6}).
7. For any positive integer m ______ is divisible by 4.
a) 5m2 + 2
b) 3m + 1
c) m2 + 3
d) m3 + 3m
Answer: d
Clarification: The required answer is, m3 + 3m. Now, by induction hypothesis, we have to prove for m=k, k3+3k is divisible by 4. So, (k + 1)3 + 3 (k + 1) = k3 + 3 k2 + 6 k + 4
= [k3 + 3 k] + [3 k2 + 3 k + 4] = 4M + (12k2 + 12k) – (8k2 + 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)
Answer: b
Clarification: 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) = mk + 5.
9. Which of the following is the base case for 4n+1 > (n+1)2 where n = 2?
a) 64 > 9
b) 16 > 2
c) 27 < 91
d) 54 > 8
Answer: a
Clarification: Statement By principle of mathematical induction, for n=2 the base case of the inequation 4n+1 > (n+1)2 should be 64 > 9 and it is true.
10. What is the induction hypothesis assumption for the inequality m ! > 2m where m>=4?
a) for m=k, k+1!>2k holds
b) for m=k, k!>2k holds
c) for m=k, k!>3k holds
d) for m=k, k!>2k+1 holds
Answer: b
Clarification: By the induction hypothesis, assume that p (k) = k! > 2k is true, for m=k and we need to prove this by the principle of mathematical induction.