Mathematical induction (basic and strong induction) - Discrete Math

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?
Answer: $\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}$ 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.
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?
Answer: If $m + 1$ is even, write $m + 1 = 2j$ where $j \leq m$ , so $j$ has a binary representation that can be shifted 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.
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?
Answer: The range $k < m \leq k+1$ contains no integers when $k$ is an integer, making the inductive step vacuous. 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.
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?
Answer: Use the fact that $k+1 = (k-3) + 4$ and apply the inductive hypothesis to $k-3$ since $k-3 ≥ 12$ . 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.
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$ ?
Answer: $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$ 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}$ to $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.
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?
Answer: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(2m + 1) - 1 = 6m + 3 - 1 = 2(3m + 1)$ 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.
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?
Answer: Two base cases ( $n = 2, 3$ ) because the Fibonacci recurrence requires two previous terms, necessitating two base cases. 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.
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?
Answer: Rewrite as $(m+1)! + (m+1)(m+1)! - 1 = (m+1)![1 + (m+1)] - 1 = (m+2)! - 1$ 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.
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?
Answer: $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}}$ 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.
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?
Answer: 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$ 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.
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?
Answer: Factor out $(m+1)$ from both terms and simplify the resulting expression to match the target formula 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.
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}$ ?
Answer: 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}$ 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.
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?
Answer: 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)$ 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.
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}$ ?
Answer: $k + 1 \geq 2$ , and since $k \geq 4 > 1$ , we have $k + 1 > 2$ , giving the strict inequality needed 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.
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?
Answer: The substitution $5^k = 4j + 1$ from the inductive hypothesis $5^k - 1 = 4j$ requires explicit justification. 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.
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?
Answer: Recognize that $k^2 > 2k + 1$ is equivalent to $(k-1)^2 > 2$ and verify this holds for $k \geq 5$ . 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.
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?
Answer: 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 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.
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$ ?
Answer: $\sum_{i=1}^{k} i \cdot 2^i + (k+1) \cdot 2^{k+1} = k \cdot 2^{k+2} + 2$ 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.
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$ ?
Answer: $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$ 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)².

Start this quiz