Discrete Math Quiz: Mathematical Induction

19 questions · exam conditions

0:00

Mathematical InductionQuestion 1 of 19

A student attempts to use strong induction to prove that every positive integer $n \geq 1$ can be written as a sum of distinct powers of 2 (i.e., in binary representation). They verify small cases and assume that every integer $k$ with $1 \leq k \leq m$ can be written as such a sum. For the inductive step with $n = m + 1$ , they consider two cases. What is the key insight that determines how to proceed?

Check whether

m + 1

is a power of 2; if so, the representation is trivial, otherwise factor out the largest power of 2

m + 1

is odd, then

m

is even, and we can use the representation of

m

plus the additional power

2^0 = 1

m + 1

is even, write

m + 1 = 2j

where

j \leq m

, so

j

has a binary representation that can be shifted

Consider whether

m + 1

is even or odd: if even, use

m + 1 = 2 \cdot \frac{m+1}{2}

; if odd, use

m + 1 = m + 1

where

m

is even

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Mathematical Induction

Practice Mathematical Induction in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Mathematical Induction, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

Check whether $m + 1$ is a power of 2; if so, the representation is trivial, otherwise factor out the largest power of 2
If $m + 1$ is odd, then $m$ is even, and we can use the representation of $m$ plus the additional power $2^0 = 1$
If $m + 1$ is even, write $m + 1 = 2j$ where $j \leq m$ , so $j$ has a binary representation that can be shifted (correct answer)
Consider whether $m + 1$ is even or odd: if even, use $m + 1 = 2 \cdot \frac{m+1}{2}$ ; if odd, use $m + 1 = m + 1$ where $m$ is even

Explanation: Strong induction problems often hinge on finding the right way to connect your target case to previously proven cases. When proving binary representation exists for all positive integers, the key insight involves understanding how binary representations behave under multiplication by 2. The correct approach recognizes that if

m + 1

is even, you can write

m + 1 = 2j

where

j = \frac{m+1}{2}

. Since

m + 1 \geq 2

, we have

j \geq 1

, and since

m + 1 = 2j

, we get

j = \frac{m+1}{2} \leq \frac{m+m}{2} = m

. This means

j

falls within our inductive hypothesis range, so

j

has a binary representation. Crucially, multiplying by 2 in binary simply shifts all digits left (adding a zero at the end), so

2j

also has a valid binary representation using distinct powers of 2. Answer A is too simplistic—while powers of 2 are easy cases, this doesn't provide a systematic approach for non-powers of 2. Answer B has the right idea about odd numbers but misses the systematic connection to the inductive hypothesis. The logic is incomplete because it doesn't clearly show how to use

m

's representation. Answer D restates the case analysis without providing the crucial insight about how even cases connect to smaller numbers within the inductive range. When tackling strong induction proofs, always look for ways to express your target in terms of strictly smaller values that fall within your inductive hypothesis. The "shift" property of binary representations makes the even case particularly elegant.

Question 2

A student claims to prove by induction that for all $n \geq 1$ , $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ . In the inductive step, they assume the formula holds for $n = m$ and then write: "For $n = m+1$ : $\sum_{k=1}^{m+1} k^2 = \sum_{k=1}^{m} k^2 + (m+1)^2 = \frac{m(m+1)(2m+1)}{6} + (m+1)^2$ . To complete the proof, I need to show this equals $\frac{(m+1)(m+2)(2m+3)}{6}$ ." What is the most direct way to verify this algebraic step?

Factor out $(m+1)$ from both terms and simplify the resulting expression to match the target formula (correct answer)
Expand both the assumed formula and target formula completely, then verify they are equal term by term
Substitute specific values of $m$ to check if the equality holds for several test cases
Use L'Hôpital's rule to compare the limiting behavior of both expressions as $m \to \infty$

Explanation: The most efficient approach is to factor out (m+1): (m(m+1)(2m+1))/6 + (m+1)² = (m+1)[m(2m+1)/6 + (m+1)] = (m+1)[m(2m+1) + 6(m+1)]/6 = (m+1)[2m² + m + 6m + 6]/6 = (m+1)[2m² + 7m + 6]/6 = (m+1)(m+2)(2m+3)/6. Choice B would work but is unnecessarily complex. Choice C doesn't constitute a proof for all m. Choice D is inappropriate since we're dealing with polynomial equality, not limits.

Question 3

Consider the statement: "For all $n \geq 1$ , $\sum_{k=1}^{n} k \cdot k! = (n+1)! - 1$ ." A student wants to prove this by induction. In the inductive step, they assume the formula holds for $n = m$ and need to prove it for $n = m+1$ . They write: $\sum_{k=1}^{m+1} k \cdot k! = \sum_{k=1}^{m} k \cdot k! + (m+1) \cdot (m+1)! = (m+1)! - 1 + (m+1) \cdot (m+1)!$ . What should be their next step?

Factor out $(m+1)!$ to get $(m+1)!(1 + (m+1)) - 1 = (m+1)!(m+2) - 1 = (m+2)! - 1$
Rewrite as $(m+1)! + (m+1)(m+1)! - 1 = (m+1)![1 + (m+1)] - 1 = (m+2)! - 1$ (correct answer)
Use the identity $(m+1) \cdot (m+1)! = (m+2)! - (m+1)!$ to simplify the expression directly
Note that $(m+1)! - 1 + (m+1)(m+1)! = (m+1)! + (m+1)(m+1)! - 1 = (m+1)!(1 + m + 1) - 1$

Explanation: Choice B correctly shows the factoring: (m+1)! - 1 + (m+1)(m+1)! = (m+1)! + (m+1)(m+1)! - 1 = (m+1)![1 + (m+1)] - 1 = (m+1)!(m+2) - 1 = (m+2)! - 1. Choice A makes an error by factoring out (m+1)! from the -1 term, which is incorrect. Choice C mentions an identity that isn't standard and would need justification. Choice D starts correctly but writes 1 + m + 1 = m + 2 instead of 1 + (m+1) = m + 2, showing unclear parenthesization.

Question 4

A student attempts to prove by induction that $3^n - 1$ is divisible by 2 for all $n \geq 1$ . They verify the base case $n = 1$ : $3^1 - 1 = 2$ , which is divisible by 2. For the inductive step, they assume $3^k - 1$ is divisible by 2 for some $k \geq 1$ , meaning $3^k - 1 = 2m$ for some integer $m$ . Which expression correctly represents $3^{k+1} - 1$ in terms of the inductive hypothesis?

$3^{k+1} - 1 = 3(3^k - 1) + 2 = 3(2m) + 2 = 2(3m + 1)$
$3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(2m + 1) - 1 = 6m + 3 - 1 = 2(3m + 1)$ (correct answer)
$3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 3 - 1 = 3(2m) + 2 = 2(3m + 1)$
$3^{k+1} - 1 = (3^k - 1) \cdot 3 + 2 = (2m) \cdot 3 + 2 = 2(3m + 1)$

Explanation: Choice B is correct: 3^(k+1) - 1 = 3·3^k - 1. From the inductive hypothesis 3^k - 1 = 2m, we get 3^k = 2m + 1. Therefore: 3^(k+1) - 1 = 3(2m + 1) - 1 = 6m + 3 - 1 = 6m + 2 = 2(3m + 1). Choice A incorrectly factors 3·3^k as 3(

3^k

- 1), which would give 3·3^k = 3·3^k - 3, not 3·3^k. Choice C makes the same error. Choice D incorrectly writes 3^(k+1) - 1 as (

3^k

- 1)·3 + 2, which doesn't follow from the definition.

Question 5

Let $T_n$ be the $n$ -th triangular number: $T_n = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ . A student wants to prove by induction that $\sum_{k=1}^{n} T_k = \frac{n(n+1)(n+2)}{6}$ for all $n \geq 1$ . In the inductive step, they assume the formula holds for $n = m$ and write: $\sum_{k=1}^{m+1} T_k = \sum_{k=1}^{m} T_k + T_{m+1} = \frac{m(m+1)(m+2)}{6} + \frac{(m+1)(m+2)}{2}$ . What is the most efficient way to show this equals $\frac{(m+1)(m+2)(m+3)}{6}$ ?

Factor out $\frac{m+1}{6}$ to get $\frac{m+1}{6}[m(m+2) + 3(m+2)] = \frac{(m+1)(m+2)(m+3)}{6}$
Factor out $\frac{(m+1)(m+2)}{6}$ to get $\frac{(m+1)(m+2)}{6}[m + 3] = \frac{(m+1)(m+2)(m+3)}{6}$ (correct answer)
Use a common denominator of 6: $\frac{m(m+1)(m+2) + 3(m+1)(m+2)}{6} = \frac{(m+1)(m+2)(m+3)}{6}$
Expand both terms completely, combine like terms, and factor the resulting numerator as $(m+1)(m+2)(m+3)$

Explanation: Choice B is the most efficient: Factor out (m+1)(m+2)/6 from both terms: m(m+1)(m+2)/6 + (m+1)(m+2)/2 = m(m+1)(m+2)/6 + 3(m+1)(m+2)/6 = [(m+1)(m+2)/6][m + 3] = (m+1)(m+2)(m+3)/6. Choice A incorrectly factors out (m+1)/6 instead of (m+1)(m+2)/6. Choice C is correct but less efficient than B. Choice D would work but is unnecessarily complex compared to the factoring approach.

Question 6

Consider the statement: "For all integers $n \geq 3$ , $2^n > n^2$ ." A student attempts a proof by strong induction with base cases $n = 3$ and $n = 4$ , then assumes the statement holds for all integers $k$ where $3 \leq k \leq m$ for some $m \geq 4$ . For the inductive step to prove $2^{m+1} > (m+1)^2$ , which approach would be most appropriate?

Use the inductive hypothesis for $k = m$ to show $2^{m+1} = 2 \cdot 2^m > 2m^2$ , then prove $2m^2 > (m+1)^2$ for $m \geq 4$ (correct answer)
Apply the inductive hypothesis to both $k = m$ and $k = m-1$ to establish bounds on $2^{m+1}$ using both previous terms
Expand $(m+1)^2$ and use direct comparison with $2^{m+1}$ without referencing any inductive hypothesis at all
Use strong induction to assume the result for all $k \leq m-1$ , then prove the case $k = m$ and $k = m+1$ simultaneously

Explanation: Choice A is correct: From 2^m > m², we get 2^(m+1) = 2·2^m > 2m². We need to show 2m² > (m+1)² = m² + 2m + 1, or equivalently m² > 2m + 1, which holds for m ≥ 4. Choice B unnecessarily uses strong induction when regular induction suffices. Choice C abandons the inductive approach entirely. Choice D misunderstands the inductive step structure.

Question 7

A student claims to prove by induction that $\sum_{k=1}^{n} \frac{1}{2^k} = 1 - \frac{1}{2^n}$ for all $n \geq 1$ . In the inductive step, they assume the formula holds for $n = m$ and write: $\sum_{k=1}^{m+1} \frac{1}{2^k} = \sum_{k=1}^{m} \frac{1}{2^k} + \frac{1}{2^{m+1}} = 1 - \frac{1}{2^m} + \frac{1}{2^{m+1}}$ . To complete the proof, they must show this equals $1 - \frac{1}{2^{m+1}}$ . What algebraic manipulation achieves this?

$1 - \frac{1}{2^m} + \frac{1}{2^{m+1}} = 1 - \frac{1}{2^m}(1 - \frac{1}{2}) = 1 - \frac{1}{2^m} \cdot \frac{1}{2} = 1 - \frac{1}{2^{m+1}}$
$1 - \frac{1}{2^m} + \frac{1}{2^{m+1}} = 1 + \frac{1}{2^{m+1}} - \frac{1}{2^m} = 1 + \frac{1 - 2}{2^{m+1}} = 1 - \frac{1}{2^{m+1}}$
$1 - \frac{1}{2^m} + \frac{1}{2^{m+1}} = 1 - \frac{2}{2^{m+1}} + \frac{1}{2^{m+1}} = 1 - \frac{1}{2^{m+1}}$ (correct answer)
$1 - \frac{1}{2^m} + \frac{1}{2^{m+1}} = 1 - \frac{2^{m+1} - 2^m}{2^m \cdot 2^{m+1}} = 1 - \frac{2^m}{2^m \cdot 2^{m+1}} = 1 - \frac{1}{2^{m+1}}$

Explanation: When completing an inductive proof, you need to manipulate the expression algebraically to match your target formula exactly. Here, you must transform

1 - \frac{1}{2^m} + \frac{1}{2^{m+1}}

into

1 - \frac{1}{2^{m+1}}

. The key insight is recognizing that

\frac{1}{2^m} = \frac{2}{2^{m+1}}

because multiplying both numerator and denominator by 2 gives you a common denominator. Option C uses this approach correctly:

1 - \frac{1}{2^m} + \frac{1}{2^{m+1}} = 1 - \frac{2}{2^{m+1}} + \frac{1}{2^{m+1}} = 1 - \frac{1}{2^{m+1}}

. The fractions combine naturally since

-\frac{2}{2^{m+1}} + \frac{1}{2^{m+1}} = \frac{-2+1}{2^{m+1}} = -\frac{1}{2^{m+1}}

. Option A incorrectly factors out

\frac{1}{2^m}

, writing

1 - \frac{1}{2^m} + \frac{1}{2^{m+1}} = 1 - \frac{1}{2^m}(1 - \frac{1}{2})

, but this factoring doesn't match the original expression. Option B makes an algebraic error when combining fractions—writing

\frac{1}{2^{m+1}} - \frac{1}{2^m} = \frac{1-2}{2^{m+1}}

incorrectly assumes both terms have denominator

2^{m+1}

. Option D creates an unnecessarily complex common denominator

2^m \cdot 2^{m+1}

, then makes errors in simplification. Strategy tip: In inductive proofs involving fractions, look for opportunities to rewrite terms with common denominators. The simplest common denominator is usually the larger power, so express

\frac{1}{2^m}

in terms of

2^{m+1}

rather than finding a more complex shared denominator.

Question 8

Consider the recurrence relation $a_n = 3a_{n-1} - 2a_{n-2}$ with initial conditions $a_0 = 0$ and $a_1 = 1$ . A student conjectures that $a_n = 2^n - 1$ for all $n \geq 0$ and wants to prove this by strong induction. They verify $a_0 = 0 = 2^0 - 1$ and $a_1 = 1 = 2^1 - 1$ . In the inductive step, they assume $a_k = 2^k - 1$ for all $0 \leq k \leq m$ where $m \geq 1$ . Which calculation correctly verifies $a_{m+1} = 2^{m+1} - 1$ ?

$a_{m+1} = 3a_m - 2a_{m-1} = 3(2^m - 1) - 2(2^{m-1} - 1) = 3 \cdot 2^m - 3 - 2^m + 2 = 2 \cdot 2^m - 1$
$a_{m+1} = 3a_m - 2a_{m-1} = 3(2^m - 1) - 2(2^{m-1} - 1) = 3 \cdot 2^m - 2 \cdot 2^{m-1} - 1 = 2^{m+1} - 1$
$a_{m+1} = 3a_m - 2a_{m-1} = 3(2^m - 1) - 2(2^{m-1} - 1) = 3 \cdot 2^m - 3 - 2 \cdot 2^{m-1} + 2 = 2^{m+1} - 1$ (correct answer)
$a_{m+1} = 3a_m - 2a_{m-1} = 3(2^m - 1) - 2(2^{m-1} - 1) = 3 \cdot 2^m - 3 - 2^m + 2 = 2^{m+1} - 1$

Explanation: When proving a formula by strong induction on recurrence relations, you need to carefully substitute your inductive hypothesis and then simplify the algebra step-by-step. The key is tracking every term through the algebraic manipulation without making arithmetic errors. Let's work through the inductive step systematically. Using the recurrence relation and the inductive hypothesis that

a_k = 2^k - 1

for all

k \leq m

a_{m+1} = 3a_m - 2a_{m-1} = 3(2^m - 1) - 2(2^{m-1} - 1)

Now distribute carefully:

3(2^m - 1) = 3 \cdot 2^m - 3

and

2(2^{m-1} - 1) = 2 \cdot 2^{m-1} - 2

So:

a_{m+1} = 3 \cdot 2^m - 3 - (2 \cdot 2^{m-1} - 2) = 3 \cdot 2^m - 3 - 2 \cdot 2^{m-1} + 2

Since

2 \cdot 2^{m-1} = 2^m

, we get:

a_{m+1} = 3 \cdot 2^m - 2^m - 1 = 2 \cdot 2^m - 1 = 2^{m+1} - 1

This matches option C exactly. Option A incorrectly combines the constant terms, getting

2^m

instead of

2 \cdot 2^{m-1}

in the middle step. Option B fails to distribute the negative sign properly when expanding

-2(2^{m-1} - 1)

, losing track of the constant terms. Option D makes the same error as A, incorrectly simplifying

2 \cdot 2^{m-1}

2^m

too early. Study tip: In induction proofs involving algebra, write out every step of the distribution and simplification. Don't skip steps—that's where errors hide, especially with signs and exponent rules.

Question 9

Consider the statement: "For all $n \geq 4$ , $n! > 2^n$ ." A student verifies the base case $n = 4$ : $4! = 24 > 16 = 2^4$ . For the inductive step, they assume $k! > 2^k$ for some $k \geq 4$ and need to prove $(k+1)! > 2^{k+1}$ . They write: " $(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k$ by the inductive hypothesis." What condition on $k$ ensures that $(k+1) \cdot 2^k \geq 2^{k+1}$ ?

$k + 1 \geq 2$ , which holds for all $k \geq 1$ , so the inductive step is valid for $k \geq 4$
$k + 1 > 2$ , which requires $k > 1$ , and since we assume $k \geq 4$ , this condition is satisfied
$k + 1 \geq 2$ , which gives us equality, but we need $k + 1 > 2$ for strict inequality, requiring $k \geq 2$
$k + 1 \geq 2$ , and since $k \geq 4 > 1$ , we have $k + 1 > 2$ , giving the strict inequality needed (correct answer)

Explanation: Choice D correctly identifies that we need (k+1)·2^k ≥ 2^(k+1) = 2·2^k, which simplifies to k+1 ≥ 2, or k ≥ 1. Since our inductive assumption requires k ≥ 4, we actually have k+1 > 2, giving (k+1)·2^k > 2^(k+1), which completes the proof. Choice A states the condition correctly but doesn't emphasize that we get strict inequality. Choice B incorrectly claims we need k > 1 for the inequality. Choice C confuses the reasoning about when we need equality versus strict inequality.

Question 10

Let $P(n)$ be the statement: " $n^3 + 2n$ is divisible by 3 for all integers $n \geq 0$ ." A student proves $P(0)$ and $P(1)$ , then assumes $P(k)$ holds for some $k \geq 1$ (meaning $k^3 + 2k = 3m$ for some integer $m$ ). To prove $P(k+1)$ , they need to show $(k+1)^3 + 2(k+1)$ is divisible by 3. Which approach correctly uses the inductive hypothesis?

Expand to get $k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + (3k^2 + 3k + 3) = 3m + 3(k^2 + k + 1)$
Write $(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 5k + 3 = (k^3 + 2k) + (3k^2 + 3k + 3) = 3m + 3(k^2 + k + 1)$
Note that $(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = k^3 + 2k + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1)$
Use the expansion $(k+1)^3 = k^3 + 3k^2 + 3k + 1$ to get $k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3(k^2 + k + 1)$ (correct answer)

Explanation: Choice D correctly expands (k+1)³ + 2(k+1) = k³ + 3k² + 3k + 1 + 2k + 2 = k³ + 3k² + 5k + 3, then groups terms as (k³ + 2k) + (3k² + 3k + 3) = (k³ + 2k) + 3(k² + k + 1) = 3m + 3(k² + k + 1) = 3(m + k² + k + 1), which is divisible by 3. Choices A and C make the same calculation but with small notational issues. Choice B incorrectly states that k³ + 3k² + 3k + 1 + 2k + 2 = k³ + 3k² + 5k + 3, when it should equal k³ + 3k² + 5k + 3. The error is subtle but choice D is most clearly presented.

Question 11

Consider proving by strong induction that every integer $n \geq 2$ can be written as a product of prime numbers. The base case $n = 2$ holds since 2 is prime. For the inductive step, assume that every integer $k$ with $2 \leq k \leq m$ can be written as a product of primes, where $m \geq 2$ . To prove the statement for $n = m + 1$ , what is the key insight that makes strong induction necessary here?

If $m + 1$ is composite, we can write $m + 1 = ab$ where $2 \leq a, b \leq m$ , allowing us to apply the hypothesis to both factors (correct answer)
We need to check divisibility by all primes up to $\sqrt{m + 1}$ , requiring the hypothesis for multiple previous values simultaneously
The prime factorization of $m + 1$ depends on the prime factorizations of $m$ and $m - 1$ through arithmetic relationships
Regular induction fails because $m + 1$ and $m$ may share no common prime factors, breaking the inductive chain

Explanation: Choice A identifies the crucial insight: if m+1 is composite, we can factor it as m+1 = ab where 1 < a, b < m+1, so 2 ≤ a, b ≤ m. Strong induction gives us that both a and b can be written as products of primes, so m+1 = ab is also a product of primes. Choice B mischaracterizes the proof strategy. Choice C incorrectly suggests m+1 depends arithmetically on m and m-1. Choice D incorrectly claims regular induction fails due to lack of common factors, when the real issue is that we need factorization of potentially two different values less than m+1.

Question 12

Let $a_n$ be defined by $a_1 = 1$ , $a_2 = 3$ , and $a_n = 2a_{n-1} - a_{n-2} + 2$ for $n \geq 3$ . A student conjectures that $a_n = n^2$ and wants to prove this by strong induction. After verifying the base cases, they assume $a_k = k^2$ for all $1 \leq k \leq m$ where $m \geq 2$ . Which calculation correctly shows $a_{m+1} = (m+1)^2$ ?

$a_{m+1} = 2a_m - a_{m-1} + 2 = 2m^2 - (m-1)^2 + 2 = 2m^2 - m^2 + 2m - 1 + 2 = m^2 + 2m + 1$
$a_{m+1} = 2a_m - a_{m-1} + 2 = 2m^2 - (m-1)^2 + 2 = 2m^2 - (m^2 - 2m + 1) + 2 = m^2 + 2m + 1$ (correct answer)
$a_{m+1} = 2a_m - a_{m-1} + 2 = 2m^2 - (m-1)^2 + 2 = m^2 + (m^2 - (m-1)^2) + 2 = m^2 + 2m + 1$
$a_{m+1} = 2a_m - a_{m-1} + 2 = 2m^2 - (m-1)^2 + 2 = 2m^2 - m^2 + 2m - 1 + 2 = m^2 + 2m + 1$

Explanation: Choice B correctly expands (m-1)² as m² - 2m + 1, then: a_(m+1) = 2m² - (m² - 2m + 1) + 2 = 2m² - m² + 2m - 1 + 2 = m² + 2m + 1 = (m+1)². Choice A incorrectly writes (m-1)² = m² + 2m - 1 instead of m² - 2m + 1. Choice C doesn't fully expand (m-1)² and the middle expression m² + (m² - (m-1)²) doesn't simplify correctly to the final answer. Choice D makes the same error as A in expanding (m-1)².

Question 13

A student wants to prove that $F_{n+1} \cdot F_{n-1} - F_n^2 = (-1)^n$ for all $n \geq 2$ , where $F_n$ represents the $n$ -th Fibonacci number with $F_1 = 1, F_2 = 1$ . They decide to use strong induction. What is the minimum number of base cases they need to verify, and why?

One base case ( $n = 2$ ) because the identity involves consecutive Fibonacci terms and strong induction handles the dependencies.
Two base cases ( $n = 2, 3$ ) because the Fibonacci recurrence requires two previous terms, necessitating two base cases. (correct answer)
Three base cases ( $n = 2, 3, 4$ ) because the identity involves $F_{n+1}, F_n,$ and $F_{n-1}$ , requiring three consecutive verifications.
Two base cases ( $n = 2, 3$ ) because the identity references $F_{n-1}$ and we need to ensure all referenced terms are well-defined.

Explanation: This is Cassini's identity for Fibonacci numbers. Since we're using strong induction and the Fibonacci sequence is defined recursively using the two previous terms, we need at least two base cases to establish the pattern. For n=2: F₃·F₁ - F₂² = 2·1 - 1² = 1 = (-1)². For n=3: F₄·F₂ - F₃² = 3·1 - 2² = -1 = (-1)³. Two base cases ensure that when we use the inductive step for any n≥4, we have established cases for both n-1 and n-2. Choice A is insufficient for Fibonacci-related proofs. Choice C requires more than necessary. Choice D gives a reason but not the most precise mathematical justification.

Question 14

Consider proving by induction that every positive integer $n \geq 12$ can be expressed as $4a + 5b$ where $a, b$ are non-negative integers. A student establishes base cases for $n = 12, 13, 14, 15$ and then attempts the inductive step. They assume the statement holds for all integers from 12 to $k$ (where $k \geq 15$ ) and want to prove it for $k+1$ . What should be their primary approach in the inductive step?

Express $k+1$ directly in terms of the representation of $k$ by adding 1 to the coefficient $a$ or $b$ .
Show that $k+1$ can be written as a linear combination by using the Euclidean algorithm on 4 and 5.
Use the fact that $k+1 = (k-3) + 4$ and apply the inductive hypothesis to $k-3$ since $k-3 ≥ 12$ . (correct answer)
Prove that $k+1 = 4(a+1) + 5(b-1)$ by redistributing coefficients from the representation of $k$ .

Explanation: When you encounter an induction proof with multiple base cases, you're likely dealing with a situation where the inductive step requires "looking back" several steps rather than just one. This is called strong induction, and the key insight is strategically using your inductive hypothesis. The correct approach (C) leverages the beautiful structure of this problem. Since you want to prove

k+1

can be written as

4a + 5b

, you rewrite

k+1 = (k-3) + 4

. Because

k \geq 15

, we know

k-3 \geq 12

, so by the inductive hypothesis,

k-3 = 4a + 5b

for some non-negative integers

a, b

. Therefore,

k+1 = 4a + 5b + 4 = 4(a+1) + 5b

, completing the proof. Option A fails because simply adding 1 to a coefficient changes the value by 4 or 5, not by 1. Option B misses the point entirely—the Euclidean algorithm helps prove that representations exist in general, but doesn't help with the inductive step structure needed here. Option D attempts redistribution (

4(a+1) + 5(b-1) = 4a + 5b - 1

), but this decreases the total by 1 instead of increasing it, and it fails when

b = 0

. The multiple base cases in problems like this are your clue that you'll need to "step back" by the difference between consecutive terms that can't be easily bridged. Here, since

\gcd(4,5) = 1

but we can't make every small number, stepping back by 4 (the smaller coefficient) is the natural choice.

Question 15

A student is proving by mathematical induction that $\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$ for all positive integers $n$ . In their inductive step, they write: "Assume $\sum_{k=1}^{j} k^3 = \left(\frac{j(j+1)}{2}\right)^2$ . Then $\sum_{k=1}^{j+1} k^3 = \left(\frac{j(j+1)}{2}\right)^2 + (j+1)^3$ ." To complete the proof, they need to show this equals $\left(\frac{(j+1)(j+2)}{2}\right)^2$ . Which algebraic identity is most crucial for this verification?

$\left(\frac{j(j+1)}{2}\right)^2 + (j+1)^3 = (j+1)^2\left(\frac{j^2}{4} + (j+1)\right)$
$\left(\frac{j(j+1)}{2}\right)^2 + (j+1)^3 = \frac{j^2(j+1)^2 + 4(j+1)^3}{4}$
$(j+1)^2\left(\frac{j^2 + 4(j+1)}{4}\right) = \frac{(j+1)^2(j+2)^2}{4}$
$\frac{j^2(j+1)^2 + 4(j+1)^3}{4} = \frac{(j+1)^2(j^2 + 4j + 4)}{4} = \frac{(j+1)^2(j+2)^2}{4}$ (correct answer)

Explanation: This shows the complete algebraic verification needed. Starting from (j(j+1)/2)² + (j+1)³, we need to factor and simplify to reach ((j+1)(j+2)/2)². Choice D shows: first getting a common denominator of 4, then factoring out (j+1)², recognizing that j²+4j+4=(j+2)², and finally achieving the target form. Choice A shows only partial factoring. Choice B shows the common denominator step but doesn't complete the simplification. Choice C shows the final step but not how to get there from the previous expression.

Question 16

A student attempts to prove by mathematical induction that $2^n > n^2$ for all integers $n \geq 5$ . They verify the base case $n = 5$ correctly. In the inductive step, they assume $2^k > k^2$ and want to prove $2^{k+1} > (k+1)^2$ . They write: " $2^{k+1} = 2 \cdot 2^k > 2k^2$ by the inductive hypothesis. For the inequality $2k^2 > (k+1)^2$ to hold, we need $2k^2 > k^2 + 2k + 1$ , which simplifies to $k^2 > 2k + 1$ ." What should be their next step to complete this approach?

Prove that $k^2 > 2k + 1$ holds for all $k \geq 5$ by showing $k^2 - 2k - 1 > 0$ using the quadratic formula.
Use a different approach since $k^2 > 2k + 1$ fails for small values of $k$ , making this method potentially unreliable.
Recognize that $k^2 > 2k + 1$ is equivalent to $(k-1)^2 > 2$ and verify this holds for $k \geq 5$ . (correct answer)
Apply the inductive hypothesis again to show that $k^2 > 2k + 1$ follows from $2^k > k^2$ .

Explanation: Mathematical induction problems often require creative algebraic manipulation in the inductive step. When you've correctly set up the logical chain but need to verify an intermediate inequality, look for ways to simplify or rewrite expressions to make the verification clearer. The student correctly derived that they need

k^2 > 2k + 1

to complete their proof. The key insight is recognizing that this inequality can be rewritten in a more convenient form. By rearranging

k^2 > 2k + 1

, we get

k^2 - 2k > 1

, which factors as

k^2 - 2k + 1 - 1 > 1

, or

(k-1)^2 - 1 > 1

. This simplifies to

(k-1)^2 > 2

. For

k \geq 5

, we have

k-1 \geq 4

, so

(k-1)^2 \geq 16 > 2

. This verification is straightforward and completes the proof elegantly. Option A uses the quadratic formula unnecessarily - while technically correct, it's more complicated than needed. Option B incorrectly suggests abandoning the approach; the inequality

k^2 > 2k + 1

actually does hold for

k \geq 5

, so the method works fine. Option D misunderstands the logical structure - you can't use the inductive hypothesis

2^k > k^2

to directly prove

k^2 > 2k + 1

since there's no clear relationship between these inequalities. When working with induction proofs involving inequalities, always look for opportunities to factor or complete the square. These algebraic techniques often reveal simpler forms that make verification much clearer.

Question 17

Consider proving by mathematical induction that $\sum_{i=1}^{n} i \cdot 2^i = (n-1) \cdot 2^{n+1} + 2$ for all positive integers $n$ . In the inductive step, after assuming the formula holds for $n = k$ , which expression correctly represents what must be proven for $n = k+1$ ?

$\sum_{i=1}^{k} i \cdot 2^i + (k+1) \cdot 2^{k+1} = k \cdot 2^{k+2} + 2$ (correct answer)
$\sum_{i=1}^{k+1} i \cdot 2^i = (k+1-1) \cdot 2^{(k+1)+1} + 2$
$(k-1) \cdot 2^{k+1} + 2 + (k+1) \cdot 2^{k+1} = k \cdot 2^{k+2} + 2$
$\sum_{i=1}^{k} i \cdot 2^i + (k+1) \cdot 2^{k+1} = (k-1) \cdot 2^{k+2} + 2 + (k+1) \cdot 2^{k+1}$

Explanation: For the inductive step, we need to prove the formula for n=k+1. This means showing ∑(i=1 to k+1) i·2^i = ((k+1)-1)·2^((k+1)+1) + 2 = k·2^(k+2) + 2. The left side can be written as ∑(i=1 to k) i·2^i + (k+1)·2^(k+1), and using the inductive hypothesis, this becomes (k-1)·2^(k+1) + 2 + (k+1)·2^(k+1). Choice A correctly states what needs to be proven. Choice B shows the correct substitution but not the complete equation structure. Choice C shows the algebraic work but not the complete statement. Choice D is redundant and doesn't show the target expression clearly.

Question 18

Consider the statement: "For all $n \geq 1$ , $5^n - 1$ is divisible by 4." A student proves this by induction as follows: Base case ( $n=1$ ): $5^1 - 1 = 4$ , which is divisible by 4. Inductive step: Assume $5^k - 1 = 4j$ for some integer $j$ . Then $5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(4j + 1) - 1 = 20j + 4 = 4(5j + 1)$ . Which aspect of this proof requires the most careful justification?

The algebraic manipulation $5 \cdot 5^k - 1 = 5(4j + 1) - 1$ assumes the inductive hypothesis without proper substitution.
The base case should verify divisibility for multiple small values of $n$ to ensure the pattern holds.
The conclusion $20j + 4 = 4(5j + 1)$ needs verification that $5j + 1$ is indeed an integer.
The substitution $5^k = 4j + 1$ from the inductive hypothesis $5^k - 1 = 4j$ requires explicit justification. (correct answer)

Explanation: The student assumes 5^k - 1 = 4j, which means 5^k = 4j + 1. This substitution step should be explicitly stated since it's not immediately obvious. The student jumps from the inductive hypothesis to using 5^k = 4j + 1 without showing this algebraic rearrangement. Choice A is wrong because the substitution is mathematically valid once the rearrangement is shown. Choice B is wrong because one base case is sufficient for this type of induction proof. Choice C is wrong because 5j + 1 is clearly an integer when j is an integer.

Question 19

A student is proving by strong induction that every integer $n \geq 2$ can be written as a sum of distinct powers of 2. They correctly prove the base cases $n = 2$ and $n = 3$ . For the inductive step, they assume the statement is true for all integers from 2 up to some $k \geq 3$ , and consider an arbitrary integer $m$ where $k < m \leq k+1$ . What is the primary flaw in their approach?

The inductive hypothesis should assume the statement for all integers from 2 to $k+1$ , not just up to $k$ .
The range $k < m \leq k+1$ contains no integers when $k$ is an integer, making the inductive step vacuous. (correct answer)
Strong induction requires assuming the statement for all positive integers up to $k$ , not just those from 2 to $k$ .
The base cases are insufficient; strong induction requires proving the statement for all integers from 2 to some fixed value.

Explanation: In the inductive step, the student considers integers m where k < m ≤ k+1. Since k is an integer, there are no integers strictly between k and k+1. The only integer in this range would be k+1 itself, but k < k+1 excludes k+1. This makes the range empty, so there's nothing to prove. The student should be considering m = k+1. Choice A is wrong because the inductive hypothesis is correctly stated. Choice C is wrong because starting from 2 rather than 1 is fine for this problem. Choice D is wrong because the base cases shown are sufficient.