Principle of Mathematical Induction - Practice Questions with Answers
68 free MCQs on Principle of Mathematical Induction with worked answers and explanations. A proof technique used to establish that a statement is true for every natural number, using a base case and an inductive step.
Below are 68 practice questions on Principle of Mathematical Induction, sorted Easy → Hard. Tap “Show answer & explanation” under any question to check yourself. Want the full theory first? Read the Principle of Mathematical Induction notes.
Mathematical induction works like a row of dominoes: proving the base case P(1) tips the first domino, and proving the inductive step (P(k) ⟹ P(k+1)) guarantees each domino knocks over the next - together these two facts guarantee ALL dominoes fall, without checking each one individually.
Easy - 20 questions
Q1.
The principle of mathematical induction is used to prove statements for which set of numbers?
A All real numbers
B All natural numbers
C All irrational numbers
D All negative integers
Show answer & explanation
Answer: B. All natural numbers
Why: Mathematical induction proves a statement P(n) holds for every natural number n, starting from a base case.
Q2.
What is the first step of a proof by mathematical induction?
A Assume P(k) is true before checking anything else
B Verify the base case, usually P(1)
C Prove P(k+1) directly without a base case
D Substitute n equal to infinity into the statement
Show answer & explanation
Answer: B. Verify the base case, usually P(1)
Why: The first step (base case) checks that the statement is true for the smallest value of n, usually n = 1.
Q3.
In the inductive step, what do we assume?
A P(n) is already proven true for every natural number n
B P(k) is true for some natural number k
C P(1) is false, contradicting the base case requirement
D P(k+1) is false, which we then aim to disprove
Show answer & explanation
Answer: B. P(k) is true for some natural number k
Why: The inductive hypothesis assumes P(k) is true for an arbitrary natural number k, then uses it to prove P(k+1).
Q4.
For the statement P(n): 1+2+3+...+n = n(n+1)/2, what is P(1)?
A 1 = 1
B 1 = 2
C 2 = 1
D 1 = 0
Show answer & explanation
Answer: A. 1 = 1
Why: Substituting n=1: left side = 1, right side = 1(2)/2 = 1. So P(1) is 1 = 1, which is true.
Q5.
If the base case fails for a statement P(n), what can we conclude?
A P(n) remains true for any value of n regardless of the base case outcome
B Induction cannot establish the statement starting from that base case
C P(n) is false for this particular natural number, though that alone proves little
D The inductive step becomes unnecessary here and can safely be skipped over
Show answer & explanation
Answer: B. Induction cannot establish the statement starting from that base case
Why: If the base case fails, the entire induction argument breaks down since there is no starting domino to knock over.
Q6.
Which best describes the inductive step?
A Proving P(1) only, without considering any later case
B Showing that if P(k) is true, then P(k+1) is also true
C Proving P(n) directly for one specific, large chosen n
D Disproving P(k) to show the statement fails in general
Show answer & explanation
Answer: B. Showing that if P(k) is true, then P(k+1) is also true
Why: The inductive step is a conditional proof: assuming P(k), it shows P(k+1) must follow.
Q7.
Mathematical induction is most commonly compared to which everyday analogy?
A A row of falling dominoes
B A game of chess
C A balance scale
D A circular race track
Show answer & explanation
Answer: A. A row of falling dominoes
Why: If the first domino falls, and each falling domino knocks down the next, all dominoes eventually fall. This mirrors base case plus inductive step.
Q8.
To prove n<sup>3</sup> - n is divisible by 6 for all natural numbers n by induction, what is checked first?
A That (k+1)<sup>3</sup> - (k+1) is divisible by 6
B That 1<sup>3</sup> - 1 = 0 is divisible by 6
C That n is even
D That n<sup>3</sup> is divisible by 6
Show answer & explanation
Answer: B. That 1<sup>3</sup> - 1 = 0 is divisible by 6
Why: The base case checks n=1: 1<sup>3</sup> - 1 = 0, and 0 is divisible by 6 (0 = 6 x 0), so the base case holds.
Q9.
Which closing statement correctly completes an induction proof?
A Hence P(n) is true only for n=1, since that is the only case actually checked
B Hence, by the principle of mathematical induction, P(n) is true for all natural numbers n
C Hence P(k) is false, so the inductive step cannot proceed any further from here
D Hence the proof remains incomplete without further verification of every individual case
Show answer & explanation
Answer: B. Hence, by the principle of mathematical induction, P(n) is true for all natural numbers n
Why: A correct induction proof concludes by invoking the principle itself: since the base case and inductive step both hold, P(n) is true for all natural numbers n (from the base case onward).
Q10.
For proving 2<sup>n</sup> > n for all natural numbers n, what is P(1)?
A 2 > 1
B 1 > 2
C 2 = 1
D 1 < 0
Show answer & explanation
Answer: A. 2 > 1
Why: Substituting n=1: 2<sup>1</sup> = 2, and 2 > 1 is true, so the base case holds.
Q11.
Mathematical induction is a technique for proving statements about:
A natural numbers
B all real numbers
C complex numbers
D irrational numbers
Show answer & explanation
Answer: A. natural numbers
Why: Induction proves statements P(n) that depend on a natural (counting) number n.
Q12.
Verifying the statement for the first value (usually n = 1) is called the:
A base case
B inductive step
C final conclusion
D mere guess
Show answer & explanation
Answer: A. base case
Why: The base case checks that the statement holds for the starting value.
Q13.
Assuming the statement is true for n = k is called the ___ hypothesis:
A inductive
B the base
C the final
D the random
Show answer & explanation
Answer: A. inductive
Why: The inductive hypothesis is the assumption that P(k) holds.
Q14.
Proving the statement for n = k + 1 using the assumption is called the:
A inductive step
B base case
C final answer
D random guess
Show answer & explanation
Answer: A. inductive step
Why: The inductive step uses the assumption P(k) to establish P(k + 1).
Q15.
A successful induction proves the statement for all n greater than or equal to:
A the chosen starting value
B only ten and above
C one hundred and above
D positive infinity
Show answer & explanation
Answer: A. the chosen starting value
Why: Induction establishes the statement for every n from the base value onward.
Q16.
The principle of mathematical induction is often pictured as a row of falling:
A falling dominoes
B loose stones
C stacked bricks
D flipped coins
Show answer & explanation
Answer: A. falling dominoes
Why: Each domino knocking over the next mirrors P(k) implying P(k + 1).
Q17.
If the base case is not verified, the induction proof is:
A invalid
B still valid
C partly valid
D unnecessary
Show answer & explanation
Answer: A. invalid
Why: Without a true base case the chain never starts, so the proof is invalid.
Q18.
Mathematical induction is most useful for proving results involving a variable:
A n, a positive integer
B x, a real number
C z, a complex number
D θ, an angle
Show answer & explanation
Answer: A. n, a positive integer
Why: Induction applies to statements indexed by a positive integer n.
Q19.
The two essential parts of an induction proof are the base case and the:
A inductive step
B final step
C guessing step
D drawing step
Show answer & explanation
Answer: A. inductive step
Why: Every induction proof needs a base case and an inductive step.
Q20.
After both steps are proved, the statement is guaranteed for:
A all naturals from the base up
B only for the value n = 1
C only the even numbers involved
D for essentially no numbers
Show answer & explanation
Answer: A. all naturals from the base up
Why: Once both steps hold, P(n) is true for every natural number from the base value onward.
Medium - 20 questions
Q21.
In proving 1+2+...+n = n(n+1)/2 by induction, the inductive step adds which term to both sides of the assumed equation?
A n
B k+1
C k
D 2k+1
Show answer & explanation
Answer: B. k+1
Why: Assuming 1+2+...+k = k(k+1)/2, we add the next term (k+1) to both sides to extend the sum to 1+2+...+k+(k+1).
Q22.
After adding (k+1) to k(k+1)/2 in the induction proof of the natural number sum formula, the right-hand side simplifies to:
A (k+1)(k+2)/2
B k(k+2)/2
C (k+1)(k+1)/2
D k(k+1)/2 + 1
Show answer & explanation
Answer: A. (k+1)(k+2)/2
Why: k(k+1)/2 + (k+1) = (k+1)[k/2 + 1] = (k+1)(k+2)/2, which matches the formula for n = k+1.
Q23.
To prove the sum of the first n odd numbers equals n<sup>2</sup>, what is the inductive hypothesis P(k)?
A 1+3+5+...+(2k-1) = k<sup>2</sup>
B 1+3+5+...+(2k+1) = k<sup>2</sup>
C 1+2+...+k = k<sup>2</sup>
D k = k<sup>2</sup>
Show answer & explanation
Answer: A. 1+3+5+...+(2k-1) = k<sup>2</sup>
Why: P(k) states that the sum of the first k odd numbers, 1+3+5+...+(2k-1), equals k<sup>2.</sup>
Q24.
In the inductive step for the sum of first n odd numbers, what is added to k<sup>2</sup> to get the next term?
A 2k - 1
B 2k + 1
C k + 1
D 2k
Show answer & explanation
Answer: B. 2k + 1
Why: The (k+1)th odd number is 2(k+1) - 1 = 2k + 1. Adding this to k<sup>2</sup> gives k<sup>2</sup> + 2k + 1 = (k+1)<sup>2</sup>, proving P(k+1).
Q25.
While proving n<sup>3</sup> - n is divisible by 6, (k+1)<sup>3</sup> - (k+1) is rewritten as (k<sup>3</sup> - k) plus which extra term?
A 3k<sup>2</sup> + 3k
B 3k + 3
C k<sup>2</sup> + k
D 6k
Show answer & explanation
Answer: A. 3k<sup>2</sup> + 3k
Why: (k+1)<sup>3</sup> - (k+1) = k<sup>3</sup>+3k<sup>2</sup>+3k+1-k-1 = (k<sup>3</sup>-k) + (3k<sup>2</sup>+3k). The extra term is 3k<sup>2</sup> + 3k = 3k(k+1).
Q26.
Why is 3k(k+1) always divisible by 6 in the n<sup>3</sup> - n divisibility proof?
A Because k tends to be even in many natural number cases, independent of the value of k+1
B Because k(k+1) is a product of consecutive integers, so it is always even, making 3k(k+1) divisible by 6
C Because 3 itself is divisible by 6 without remainder, which some take as sufficient reasoning on its own
D Because k+1 happens to be divisible by 3 in this case, regardless of which natural number k is chosen
Show answer & explanation
Answer: B. Because k(k+1) is a product of consecutive integers, so it is always even, making 3k(k+1) divisible by 6
Why: Among any two consecutive integers k and k+1, one is always even, so k(k+1) is even. Multiplying by 3 gives a number divisible by both 2 and 3, hence by 6.
Q27.
To prove 4<sup>n</sup> - 1 is divisible by 3 for all natural numbers n, the inductive step considers 4<sup>k+1</sup> - 1, which can be written as:
A 4(4<sup>k</sup> - 1) + 3
B 4<sup>k</sup> - 1 + 4
C 4 x 4<sup>k</sup> - 4
D 4<sup>k</sup> + 3
Show answer & explanation
Answer: A. 4(4<sup>k</sup> - 1) + 3
Why: 4<sup>k+1</sup> - 1 = 4 x 4<sup>k</sup> - 1 = 4(4<sup>k</sup> - 1) + 4 - 1 = 4(4<sup>k</sup> - 1) + 3. Since 4<sup>k</sup> - 1 is divisible by 3 (hypothesis) and 3 is divisible by 3, the whole sum is divisible by 3.
Q28.
For the inequality 2<sup>n</sup> > n, the inductive step shows 2<sup>k+1</sup> = 2 x 2<sup>k</sup> > 2k. To complete the proof we additionally need:
A 2k >= k+1 for k >= 1
B k greater than 0, with no other condition needed
C 2<sup>k</sup> less than k, an inequality that rarely holds
D k is an even natural number specifically
Show answer & explanation
Answer: A. 2k >= k+1 for k >= 1
Why: Since 2<sup>k</sup> > k by hypothesis, 2 x 2<sup>k</sup> > 2k. To conclude 2<sup>k+1</sup> > k+1, we need 2k >= k+1, which holds for all k >= 1.
Q29.
Using induction to prove the sum of squares formula n(n+1)(2n+1)/6, what is P(2)?
A 1 + 4 = 2(3)(5)/6
B 1 + 4 = 10
C 5 = 5
D 1 + 2 = 5
Show answer & explanation
Answer: A. 1 + 4 = 2(3)(5)/6
Why: P(2) states 1<sup>2</sup> + 2<sup>2</sup> = 2(3)(5)/6. Left side = 1+4 = 5, right side = 30/6 = 5. Both equal 5, confirming P(2) is true.
Q30.
Which statement about induction is correct?
A Induction can prove a statement for just one specific value of n, leaving every other value of n unverified
B Induction proves a statement for all n from the base case onward by chaining the inductive step infinitely
C Induction requires checking each natural number individually by hand, one at a time, indefinitely
D Induction works mainly for inequality statements, rarely for equalities between expressions
Show answer & explanation
Answer: B. Induction proves a statement for all n from the base case onward by chaining the inductive step infinitely
Why: Induction's power is that the inductive step, once proven for arbitrary k, applies repeatedly: P(1) implies P(2), which implies P(3), and so on for every n from the base case onward.
Q31.
The sum 1 + 2 + 3 + … + n equals:
A n(n + 1)/2
B n(n + 1) itself
C n squared
D simply 2n
Show answer & explanation
Answer: A. n(n + 1)/2
Why: The sum of the first n natural numbers is n(n + 1)/2.
Q32.
The sum 1² + 2² + … + n² equals:
A n(n + 1)(2n + 1)/6
B n(n + 1)/2 only
C n squared only
D n cubed only
Show answer & explanation
Answer: A. n(n + 1)(2n + 1)/6
Why: The sum of the first n squares is n(n + 1)(2n + 1)/6.
Q33.
The sum 1³ + 2³ + … + n³ equals:
A [n(n + 1)/2]²
B n(n + 1)/2
C n²
D n(n + 1)(2n + 1)/6
Show answer & explanation
Answer: A. [n(n + 1)/2]²
Why: The sum of the first n cubes is the square of the sum of the first n numbers.
Q34.
In the inductive step for a sum formula, we add ___ to both sides of the assumed equation:
A the (k + 1)th term
B the very first term
C the number zero
D the value n
Show answer & explanation
Answer: A. the (k + 1)th term
Why: Adding the (k + 1)th term to P(k) lets us derive P(k + 1).
Q35.
To prove a statement for all n ≥ 1, the base case is usually taken at n =:
A 1
B 0
C 2
D 10
Show answer & explanation
Answer: A. 1
Why: The base case is checked at the smallest value in the range, here n = 1.
Q36.
The sum of the first n odd numbers, 1 + 3 + … + (2n − 1), equals:
A n²
B n(n + 1)
C 2n
D n³
Show answer & explanation
Answer: A. n²
Why: The sum of the first n odd numbers is n².
Q37.
In an induction proof of divisibility, the (k + 1) case is handled using the:
A the inductive hypothesis
B just the base case
C a final guessed value
D a random chosen number
Show answer & explanation
Answer: A. the inductive hypothesis
Why: The inductive hypothesis about the k case is rewritten to reveal the divisor in the (k + 1) case.
Q38.
For the statement 2ⁿ > n, the base case n = 1 gives:
A 2 > 1, which is true
B 2 < 1, which is false
C 1 = 1 exactly
D 0 > 1 falsely
Show answer & explanation
Answer: A. 2 > 1, which is true
Why: At n = 1, 2¹ = 2 > 1, so the base case holds.
Q39.
A standard induction proof consists of how many main steps?
A 2
B 1
C 3
D 4
Show answer & explanation
Answer: A. 2
Why: There are two steps: the base case and the inductive step.
Q40.
The geometric sum 1 + 2 + 4 + … + 2ⁿ⁻¹ equals:
A 2ⁿ − 1
B just 2ⁿ
C n² only
D only 2n
Show answer & explanation
Answer: A. 2ⁿ − 1
Why: This geometric series of n terms sums to 2ⁿ − 1.
Hard - 28 questions
Q41.
To prove n! > 2<sup>n</sup> for all natural numbers n >= 4 by induction, what should the base case be?
A n = 1
B n = 4
C n = 0
D n = 2
Show answer & explanation
Answer: B. n = 4
Why: The inequality n! > 2<sup>n</sup> is false for n=1,2,3 (check: 1!=1 vs 2, 2!=2 vs 4, 3!=6 vs 8, all fail), but holds from n=4 onward (4!=24 > 16=2<sup>4</sup>). So the base case must be n=4.
Q42.
In the inductive step for n! > 2<sup>n</sup> (n >= 4), assuming k! > 2<sup>k</sup>, how is (k+1)! related to k!?
A (k+1)! = (k+1) x k!, and since k+1 > 2 for k >= 4, (k+1)! > 2 x k! > 2 x 2<sup>k</sup> = 2<sup>k+1</sup>
B (k+1)! = k! + (k+1), treating factorial growth as additive rather than multiplicative
C (k+1)! = 2 x k!, fixing the multiplier at 2 regardless of the actual value of k+1
D (k+1)! is unrelated to k!, since each factorial is computed independently
Show answer & explanation
Answer: A. (k+1)! = (k+1) x k!, and since k+1 > 2 for k >= 4, (k+1)! > 2 x k! > 2 x 2<sup>k</sup> = 2<sup>k+1</sup>
Why: By definition (k+1)! = (k+1) x k!. Since k >= 4, k+1 >= 5 > 2, so (k+1)! > 2 x k!. Using the hypothesis k! > 2<sup>k</sup>, we get (k+1)! > 2 x 2<sup>k</sup> = 2<sup>k+1</sup>.
Q43.
To prove that 7<sup>n</sup> - 3<sup>n</sup> is divisible by 4 for all natural numbers n, the inductive step writes 7<sup>k+1</sup> - 3<sup>k+1</sup> as:
A 7(7<sup>k</sup> - 3<sup>k</sup>) + 4(3<sup>k</sup>)
B 7<sup>k</sup> - 3<sup>k</sup> + 4
C 7 x 7<sup>k</sup> - 3 x 3<sup>k</sup> only, with no simplification
D 4(7<sup>k</sup> - 3<sup>k</sup>)
Show answer & explanation
Answer: A. 7(7<sup>k</sup> - 3<sup>k</sup>) + 4(3<sup>k</sup>)
Why: 7<sup>k+1</sup> - 3<sup>k+1</sup> = 7 x 7<sup>k</sup> - 3 x 3<sup>k</sup> = 7(7<sup>k</sup> - 3<sup>k</sup>) + 7(3<sup>k</sup>) - 3(3<sup>k</sup>) = 7(7<sup>k</sup>-3<sup>k</sup>) + 4(3<sup>k</sup>). Since 7<sup>k</sup>-3<sup>k</sup> is divisible by 4 (hypothesis) and 4(3<sup>k</sup>) is clearly divisible by 4, the whole expression is divisible by 4.
Q44.
A student tries to prove P(n): n<sup>2</sup> = n by induction, checking P(1): 1 = 1 (true), and somehow forces an inductive step to look valid. What is the actual flaw?
A The base case itself is actually wrong here, since one squared does not truly equal one in this context
B P(n) is simply false for n=2 onward, so no valid inductive step can exist (any apparent proof has an algebraic error)
C Induction as a method rarely applies cleanly to quadratic statements like n<sup>2</sup> = n in general cases like this
D The flaw lies mainly in how the final concluding sentence of the proof happens to be phrased, not in the underlying logic
Show answer & explanation
Answer: B. P(n) is simply false for n=2 onward, so no valid inductive step can exist (any apparent proof has an algebraic error)
Why: Since P(2): 4 = 2 is false, the statement is false in general. Any inductive step that appears to prove P(k+1) from P(k) here must contain a hidden algebraic error, since a true base case plus a genuinely valid inductive step cannot produce a false conclusion.
Q45.
To prove that 10<sup>n</sup> + 3 x 4<sup>n+2</sup> + 5 is divisible by 9 for all natural numbers n, what is the value at n=1, and is it divisible by 9?
A 10 + 192 + 5 = 207, and 207/9 = 23, so yes
B 10 + 48 + 5 = 63, and 63/9 = 7, so yes
C 207, but it is not divisible by 9
D 10 + 3 + 5 = 18, divisible by 9
Show answer & explanation
Answer: A. 10 + 192 + 5 = 207, and 207/9 = 23, so yes
Why: At n=1: 10<sup>1</sup> + 3 x 4<sup>3</sup> + 5 = 10 + 3(64) + 5 = 10 + 192 + 5 = 207. Dividing, 207/9 = 23 exactly, confirming the base case.
Q46.
While proving the sum of cubes formula [n(n+1)/2]<sup>2</sup> by induction, the inductive step must show that [k(k+1)/2]<sup>2</sup> + (k+1)<sup>3</sup> equals:
A [(k+1)(k+2)/2]<sup>2</sup>
B [k(k+2)/2]<sup>2</sup>
C (k+1)<sup>2</sup> (k+2)<sup>2</sup>
D k<sup>2</sup>(k+1)<sup>2</sup>/4 + (k+1)
Show answer & explanation
Answer: A. [(k+1)(k+2)/2]<sup>2</sup>
Why: Factor out (k+1)<sup>2</sup>: [k(k+1)/2]<sup>2</sup> + (k+1)<sup>3</sup> = (k+1)<sup>2</sup> [k<sup>2</sup>/4 + (k+1)] = (k+1)<sup>2</sup> [(k<sup>2</sup>+4k+4)/4] = (k+1)<sup>2</sup> (k+2)<sup>2</sup>/4 = [(k+1)(k+2)/2]<sup>2</sup>, matching the formula for n=k+1.
Q47.
Which of the following is the correct inductive hypothesis when proving that n(n+1)(n+2) is divisible by 6 for all natural numbers n?
A Assume k(k+1)(k+2) is divisible by 6, then show (k+1)(k+2)(k+3) is divisible by 6
B Assume n itself is divisible by 6, without ever involving consecutive products together
C Assume just the single term (k+1) is divisible by 6, ignoring the rest
D Assume k(k+1) is divisible by 3, dropping the third factor from consideration
Show answer & explanation
Answer: A. Assume k(k+1)(k+2) is divisible by 6, then show (k+1)(k+2)(k+3) is divisible by 6
Why: The inductive hypothesis P(k) assumes the product of three consecutive integers starting at k is divisible by 6; the inductive step must then prove the same for the next set of three consecutive integers starting at k+1.
Q48.
For proving n<sup>2</sup> < 2<sup>n</sup> for all natural numbers n >= 5, what must be verified before applying the inductive step?
A That the base case n=5 holds: 25 < 32
B That n=1 holds: 1 < 2
C Nothing, induction applies automatically
D That n=4 holds: 16 < 16
Show answer & explanation
Answer: A. That the base case n=5 holds: 25 < 32
Why: The inequality n<sup>2</sup> < 2<sup>n</sup> fails for n=1,2,3,4 (at n=4: 16 < 16 is false since they are equal), but holds from n=5 onward (25 < 32). The base case must therefore be verified at n=5.
Q49.
While proving 2<sup>2n</sup> - 1 is divisible by 3 by induction, the inductive step rewrites 2^(2(k+1)) - 1 as:
A (2<sup>2k</sup> - 1) + 4
B 4(2<sup>2k</sup> - 1) + 3
C 4(2<sup>2k</sup> - 1) - 3
D 2(2<sup>2k</sup> - 1) + 1
Show answer & explanation
Answer: B. 4(2<sup>2k</sup> - 1) + 3
Why: 2<sup>2k+2</sup> - 1 = 4 . 2<sup>2k</sup> - 1 = 4(2<sup>2k</sup> - 1) + 3, and since 2<sup>2k</sup> - 1 is divisible by 3 by the inductive hypothesis, the whole expression is divisible by 3.
Q50.
A student proves P(k) implies P(k+1) for every k, but never verifies P(1). Even though the inductive step is logically correct, why does the proof fail?
A Without a verified base case, the chain of implications has no starting point to begin from
B The inductive hypothesis must always be assumed false, not true, for the argument to work
C The statement P(n) must instead be proven separately for every even and odd value of n
D Strong induction is required instead, since ordinary induction cannot use implications
Show answer & explanation
Answer: A. Without a verified base case, the chain of implications has no starting point to begin from
Why: Mathematical induction requires both a true base case and a valid inductive step; without an established starting point P(1), the chain of implications P(k) => P(k+1) never gets triggered for any n.
Q51.
To prove 3²ⁿ − 1 is divisible by 8, the base case n = 1 gives the value:
A 8, and 8 divides it
B 9, not divisible by 8
C 3, not divisible by 8
D 0, trivially special
Show answer & explanation
Answer: A. 8, and 8 divides it
Why: 3²(1) − 1 = 9 − 1 = 8, which is divisible by 8.
Q52.
In proving 1 + 2 + … + n = n(n + 1)/2, adding (k + 1) to k(k + 1)/2 gives:
A (k + 1)(k + 2)/2
B only (k + 1)/2
C only k(k + 1)/2
D only (k + 2)/2
Show answer & explanation
Answer: A. (k + 1)(k + 2)/2
Why: k(k+1)/2 + (k+1) = (k+1)(k+2)/2, which is the formula with n = k + 1.
Q53.
The inequality n! > 2ⁿ first becomes true (and stays true) for all n greater than or equal to:
A 4
B 1
C 2
D 10
Show answer & explanation
Answer: A. 4
Why: At n = 4, 24 > 16; for n = 3, 6 < 8, so the result holds from n = 4 onward.
Q54.
Which kind of result is proved most naturally by mathematical induction?
A a summation formula over n terms
B the value of a single number
C a geometric construction result
D the value of a certain limit
Show answer & explanation
Answer: A. a summation formula over n terms
Why: Induction is ideal for statements about a formula that depends on a positive integer n.
Q55.
If P(k) is assumed and P(k + 1) is proved, but the base case is false, then:
A the statement is not proven
B the statement is proven
C it holds for k only
D it holds for all n
Show answer & explanation
Answer: A. the statement is not proven
Why: Without a valid base case the inductive chain never starts, so nothing is actually proved.
Q56.
In proving (xⁿ − yⁿ) is divisible by (x − y), the (k + 1) case is rewritten using:
A that xᵏ − yᵏ is divisible
B only the given base case
C a purely lucky guess
D no earlier known result
Show answer & explanation
Answer: A. that xᵏ − yᵏ is divisible
Why: x<sup>k+1</sup> − y<sup>k+1</sup> is manipulated to contain xᵏ − yᵏ, which the hypothesis says is divisible by (x − y).