Proof by cases - Discrete Math

To prove "For integers $m$ and $n$ , if $mn$ is odd, then $m^2 + n^2 \equiv 2 \pmod{4}$ " using proof by cases, which case analysis correctly handles the constraint that $mn$ is odd?
Answer: Case 1: $m \equiv 1 \pmod{4}$ and $n \equiv 1 \pmod{4}$ . Case 2: $m \equiv 1 \pmod{4}$ and $n \equiv 3 \pmod{4}$ . Case 3: $m \equiv 3 \pmod{4}$ and $n \equiv 1 \pmod{4}$ . Case 4: $m \equiv 3 \pmod{4}$ and $n \equiv 3 \pmod{4}$ . When proving statements involving products of integers, you need to think carefully about what constraints the hypothesis imposes. Here, " $mn$ is odd" tells us something very specific: both $m$ and $n$ must be odd, since a product is odd if and only if both factors are odd. The key insight is that for modular arithmetic proofs, you want cases that distinguish between different remainders modulo the relevant number. Since we're proving something about congruence modulo 4, and we know both $m$ and $n$ are odd, we should consider what remainders odd numbers can have when divided by 4. Odd numbers are congruent to either 1 or 3 modulo 4. Choice B correctly identifies this: it considers all possible combinations where $m$ and $n$ are each congruent to either 1 or 3 modulo 4. These four cases are exhaustive and mutually exclusive, covering exactly the situation where both numbers are odd. Choice A focuses on signs (positive/negative), which is irrelevant since squaring eliminates sign differences. Choice C overcomplicates by introducing additional variables $k$ and $j$ and considering their parity, when the direct modular approach is cleaner. Choice D considers ordering relationships ( $m < n$ , $m = n$ , $m > n$ ), which don't affect the computation of $m^2 + n^2$ . Study tip: For modular arithmetic proofs, always identify what remainders are possible given your constraints, then create cases based on those remainders. Don't get distracted by irrelevant properties like sign or relative size.
Consider the statement: "For any integer $n$ , if $n^2 + 3n + 1$ is even, then $n$ is odd." Which approach correctly demonstrates this statement using proof by cases?
Answer: Case 1: Assume $n$ is even, so $n = 2k$ . Then $n^2 + 3n + 1 = 4k^2 + 6k + 1 = 2(2k^2 + 3k) + 1$ , which is odd. Case 2: Assume $n$ is odd, so $n = 2k + 1$ . Then $n^2 + 3n + 1 = 4k^2 + 10k + 4 = 2(2k^2 + 5k + 2)$ , which is even. Choice A correctly uses proof by cases on the variable $n$ (even vs. odd) to show that when $n$ is even, $n^2 + 3n + 1$ is odd (making the hypothesis false, so the implication is vacuously true), and when $n$ is odd, $n^2 + 3n + 1$ is even (making both hypothesis and conclusion true). Choice B incorrectly attempts to assume both hypothesis and conclusion simultaneously. Choice C has the right idea but uses imprecise language about "confirming" rather than proving. Choice D makes an error in reasoning about the parity of $n(n+3)$ .
A student proves "If $x$ and $y$ are real numbers with $x^2 + y^2 = 1$ , then $-1 \leq x + y \leq \sqrt{2}$ " by considering cases based on the signs of $x$ and $y$ . Which case requires the most careful analysis to establish the upper bound $x + y \leq \sqrt{2}$ ?
Answer: Case where $x \geq 0$ and $y \geq 0$ , since both variables contribute positively to the sum and we need to find the maximum value subject to $x^2 + y^2 = 1$ The upper bound $x + y \leq \sqrt{2}$ is achieved when both $x$ and $y$ are non-negative and as large as possible. Using Lagrange multipliers or the Cauchy-Schwarz inequality: $(x + y)^2 \leq 2(x^2 + y^2) = 2$ , so $x + y \leq \sqrt{2}$ with equality when $x = y = \frac{1}{\sqrt{2}}$ . The case where both are non-negative requires the most careful analysis because it's where the maximum is achieved. Choices B and C involve mixed signs that naturally limit the sum. Choice D addresses the lower bound, not the upper bound.
Consider proving "if $n$ is an integer and $3n + 2$ is even, then $n$ is even" by contrapositive using proof by cases. The contrapositive statement is "if $n$ is odd, then $3n + 2$ is odd." When $n$ is odd, we can write $n = 2k + 1$ . What does the case analysis reveal about $3n + 2$ ?
Answer: $3n + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 2) + 1$ , which is odd, proving the contrapositive. When you encounter a proof by contrapositive, you're proving that "if P then Q" by instead proving "if not Q then not P." Here, we're showing that if $n$ is odd, then $3n + 2$ must be odd. Since $n$ is odd, we can write $n = 2k + 1$ for some integer $k$ . Let's substitute this into $3n + 2$ : $3n + 2 = 3(2k + 1) + 2 = 6k + 3 + 2 = 6k + 5$ Now we need to determine the parity of $6k + 5$ . We can rewrite this as: $6k + 5 = 6k + 4 + 1 = 2(3k + 2) + 1$ Since $2(3k + 2)$ is always even (it's 2 times an integer), adding 1 makes the entire expression odd. This proves our contrapositive statement. Option A correctly calculates $2(3k + 2) + 1$ but incorrectly claims we need further case analysis on $k$ 's parity. We don't—the expression is odd regardless of $k$ . Option B makes an algebraic error, writing $6k + 5 = 2(3k + 3) - 1$ , which gives $6k + 6 - 1 = 6k + 5$ . While the arithmetic works out, they incorrectly conclude this makes the expression even. Option C stops at $6k + 5$ without recognizing that we can definitively determine its parity by factoring out the even part. Option D correctly performs all calculations and recognizes that $2(3k + 2) + 1$ is definitively odd, completing the contrapositive proof. Study tip: In parity proofs, always try to express your result in the form $2(\text{integer}) + 1$ (odd) or $2(\text{integer})$ (even) to make the conclusion clear.
A student proves that "if $x$ and $y$ are real numbers with $xy > 0$ , then $x$ and $y$ have the same sign" using proof by cases based on the signs of $x$ and $y$ . The student considers four cases: ( $+,+$ ), ( $+,-$ ), ( $-,+$ ), and ( $-,-$ ). What is the key insight that makes this proof by cases work?
Answer: Cases ( $+,+$ ) and ( $-,-$ ) satisfy $xy > 0$ , while cases ( $+,-$ ) and ( $-,+$ ) give $xy < 0$ , contradicting the hypothesis. When you encounter a proof by cases involving conditional statements, you need to understand how the hypothesis constrains which cases are actually possible. In this proof, the key insight is recognizing that not all four sign combinations are consistent with the given hypothesis $xy > 0$ . Let's analyze each case systematically: - Case ( $+,+$ ): If both $x > 0$ and $y > 0$ , then $xy > 0$ . This satisfies our hypothesis. - Case ( $-,-$ ): If both $x < 0$ and $y < 0$ , then $xy > 0$ . This also satisfies our hypothesis. - Case ( $+,-$ ): If $x > 0$ and $y < 0$ , then $xy < 0$ . This contradicts our hypothesis $xy > 0$ . - Case ( $-,+$ ): If $x < 0$ and $y > 0$ , then $xy < 0$ . This also contradicts our hypothesis. The proof works because cases ( $+,-$ ) and ( $-,+$ ) are impossible given the hypothesis, leaving only cases where $x$ and $y$ have the same sign. This makes answer D correct. Answer A is wrong because the case analysis actually illuminates why the statement is true. Answer B misunderstands the logic—we don't need all cases to satisfy $xy > 0$ ; rather, we use the hypothesis to eliminate impossible cases. Answer C incorrectly suggests the product "approaches zero" in mixed-sign cases, when it's actually negative. Strategy tip: In proof by cases with hypotheses, always check which cases are actually possible under the given conditions. Often, the hypothesis eliminates certain cases, making the proof more straightforward.
To prove that "For all integers $a$ and $b$ , if $a^2 + b^2$ is divisible by 4, then both $a$ and $b$ are even," a student considers cases based on the remainders when $a$ and $b$ are divided by 2. How many cases must be analyzed, and which cases lead to a contradiction?
Answer: 4 cases total; cases where exactly one of $a, b$ is even lead to contradictions, plus the case where both are odd leads to a contradiction We need 4 cases: (1) both even, (2) $a$ even, $b$ odd, (3) $a$ odd, $b$ even, (4) both odd. When exactly one is odd, $a^2 + b^2 \equiv 1 \pmod{4}$ , contradicting divisibility by 4. When both are odd, $a^2 + b^2 \equiv 2 \pmod{4}$ , also contradicting divisibility by 4. Choice B incorrectly counts cases. Choice C misses that the mixed cases also lead to contradictions. Choice D oversimplifies by combining cases prematurely.
A proof by cases is used to establish: "For integers $a, b, c$ with $a^2 + b^2 = c^2$ , at least one of $a, b, c$ is divisible by 4." The proof considers cases based on the remainders of $a$ and $b$ when divided by 4. Which combination of cases leads to the conclusion that $c$ must be divisible by 4?
Answer: When both $a \equiv 2 \pmod{4}$ and $b \equiv 2 \pmod{4}$ , since then $c^2 \equiv 4 + 4 \equiv 0 \pmod{8}$ , which forces $c$ to be divisible by 4 When $a \equiv 2 \pmod{4}$ and $b \equiv 2 \pmod{4}$ , we have $a^2 \equiv 4 \equiv 0 \pmod{4}$ and $b^2 \equiv 4 \equiv 0 \pmod{4}$ . More precisely, $a^2 \equiv 0 \pmod{8}$ and $b^2 \equiv 0 \pmod{8}$ when $a, b \equiv 2 \pmod{4}$ , so $c^2 = a^2 + b^2 \equiv 0 \pmod{8}$ . This forces $c$ to be even, and since $c^2 \equiv 0 \pmod{8}$ , we must have $c \equiv 0 \pmod{4}$ . Choice A has an arithmetic error. Choice B is impossible since no perfect square is congruent to 2 modulo 4. Choice D incorrectly analyzes the modular arithmetic.
Consider the statement: "For all real numbers $x$ , $x^3 - x \geq -\frac{2\sqrt{3}}{9}$ ." A proof by cases analyzes the critical points of $f(x) = x^3 - x$ . After finding $f'(x) = 3x^2 - 1$ , what case division correctly identifies all regions for monotonicity analysis?
Answer: Case 1: $x < -\frac{\sqrt{3}}{3}$ ; Case 2: $-\frac{\sqrt{3}}{3} < x < \frac{\sqrt{3}}{3}$ ; Case 3: $x > \frac{\sqrt{3}}{3}$ Setting f'(x) = 3x² - 1 = 0 gives x² = 1/3, so x = ±√3/3 = ±1/√3. These critical points divide the domain into three intervals where f'(x) has consistent sign: f'(x) > 0 for x < -√3/3 and x > √3/3 (function increasing), and f'(x) < 0 for -√3/3 < x < √3/3 (function decreasing). Choice B uses incorrect critical points, Choice C uses the correct points but with unnecessary boundary inclusions, and Choice D ignores the actual critical points.
Consider the statement: "For any integer $n \geq 2$ , either $n$ is prime or $n$ has a prime divisor $p$ with $p \leq \sqrt{n}$ ." A proof by cases divides based on whether $n$ is prime or composite. What additional insight is required to complete the composite case?
Answer: If $n$ is composite, then $n = ab$ where $1 < a, b < n$ . We can assume $a \leq b$ , so $a^2 \leq ab = n$ , giving $a \leq \sqrt{n}$ . The smallest prime divisor of $a$ is $\leq a \leq \sqrt{n}$ . Choice C provides the correct reasoning: if $n = ab$ with $1 < a, b < n$ , we can assume $a \leq b$ without loss of generality. Then $a^2 \leq ab = n$ , so $a \leq \sqrt{n}$ . Since $a > 1$ is composite or prime, it has a smallest prime divisor $p \leq a \leq \sqrt{n}$ , and this $p$ also divides $n$ . Choice A shows one factor is $\leq \sqrt{n}$ but doesn't ensure it's prime. Choice B incorrectly assumes the smallest prime divisor's location. Choice D misapplies the pigeonhole principle.
In proving "every integer $n \geq 12$ can be expressed as $4a + 5b$ where $a, b$ are non-negative integers," a student uses strong induction with proof by cases in the inductive step. For $n = k+1$ where $k \geq 12$ , the student considers cases based on the remainder when $k+1$ is divided by 4. Which case requires invoking the inductive hypothesis?
Answer: Case: $k+1 \equiv 1 \pmod{4}$ , because this requires using the hypothesis for $k+1-5 = k-4$ to handle the remainder. When k+1 ≡ 1 (mod 4), we cannot express k+1 directly as 4a since it's not divisible by 4. However, k+1-5 = k-4 ≡ 0 (mod 4) and k-4 ≥ 8 (since k ≥ 12), so we can apply the inductive hypothesis to k-4 = 4a + 5b, giving k+1 = 4a + 5(b+1). Choice A allows direct construction, Choice C has k-9 which might be less than 12, and Choice D has k-14 which could be negative.
Consider proving: "For any real number $x$ , $|x - 1| + |x - 3| \geq 2$ " using proof by cases based on the location of $x$ relative to the critical points. Which case division is both necessary and sufficient for a complete proof?
Answer: Case 1: $x < 1$ , Case 2: $1 \leq x < 3$ , Case 3: $x \geq 3$ , analyzing the behavior of each absolute value expression separately in each interval When proving inequalities involving absolute values, you need to identify the critical points where the expressions inside the absolute value bars equal zero, then analyze each resulting interval separately. For $|x - 1| + |x - 3| \geq 2$ , the critical points are $x = 1$ and $x = 3$ , since these are where the absolute value expressions change their behavior. The correct approach divides the real line into three intervals based on both critical points: $x < 1$ , $1 \leq x < 3$ , and $x \geq 3$ . In each interval, you can remove the absolute value bars by determining the sign of each expression. For $x < 1$ : both $(x-1)$ and $(x-3)$ are negative, so $|x-1| = -(x-1)$ and $|x-3| = -(x-3)$ . For $1 \leq x < 3$ : $(x-1) \geq 0$ and $(x-3) < 0$ . For $x \geq 3$ : both expressions are non-negative. This three-case division in option D captures all necessary behavioral changes. Option A fails because it only considers one critical point, missing the behavioral change at $x = 3$ . Option B unnecessarily includes $x = 0$ , which isn't a critical point for either absolute value expression, creating redundant work. Option C also ignores the critical point at $x = 1$ , focusing incorrectly on only the second absolute value term. Remember: for absolute value proofs, always identify ALL critical points where expressions inside the bars equal zero, then create cases for each interval between consecutive critical points.
A student attempts to prove that "if $n$ is an integer, then $n^2 + n + 1$ is odd" using proof by cases. The student considers Case 1: $n$ is even, and Case 2: $n$ is odd. In Case 1, the student writes $n = 2k$ and concludes $n^2 + n + 1 = 4k^2 + 2k + 1$ , which is odd. What error, if any, occurs in the Case 2 analysis?
Answer: No error occurs; the case division is complete and both cases lead to the correct conclusion that the expression is always odd. The proof approach is correct. For Case 2 (n odd): n = 2k+1, so n² + n + 1 = (2k+1)² + (2k+1) + 1 = 4k² + 4k + 1 + 2k + 1 + 1 = 4k² + 6k + 3 = 2(2k² + 3k + 1) + 1, which is odd. The case division is complete and sufficient. Choice B suggests an error that doesn't exist, Choice C is incorrect since the statement is true, and Choice D is wrong since n = 0 is covered in the even case.
A student attempts to prove "If $n$ is an integer and $n^3 - n$ is odd, then $n$ is even" using proof by cases on the remainder when $n$ is divided by 3. What is the fundamental flaw in this approach?
Answer: The case division creates unnecessary work, since the statement can be proven directly by noting that $n^3 - n$ is always even for any integer $n$ The fundamental flaw is that $n^3 - n = n(n^2 - 1) = n(n-1)(n+1)$ is the product of three consecutive integers, so one of them must be even, making the entire product even. Therefore, $n^3 - n$ is never odd for any integer $n$ , making the hypothesis of the conditional always false. The student's case division by residues modulo 3 is irrelevant because the statement is vacuously true. Choice A misidentifies the issue. Choice B suggests an unnecessary complication. Choice C focuses on the wrong modulus but misses that the hypothesis is impossible.
To prove "if $n$ is an odd integer, then $8$ divides $n^2 - 1$ ," a student uses cases based on $n \pmod{8}$ . Since $n$ is odd, only four cases need consideration. If the student finds that three cases work correctly but one case seems to fail, which case most likely contains the computational error?
Answer: Case: $n \equiv 5 \pmod{8}$ , because $n^2 - 1 \equiv 24 \pmod{8}$ and reducing $24$ modulo $8$ often leads to arithmetic errors. For n ≡ 5 (mod 8): n² - 1 ≡ 5² - 1 ≡ 25 - 1 ≡ 24 ≡ 0 (mod 8). The error likely occurs in reducing 24 mod 8, where students might incorrectly compute 24 ÷ 8 = 3 remainder 0, but write the remainder as 3, or make similar arithmetic mistakes with the larger intermediate values. The other cases involve smaller intermediate calculations that are less error-prone: Case A gives 0 directly, Case B gives 8 ≡ 0, and Case D gives 48 ≡ 0.
A student attempts to prove "for any integer $n$ , at least one of $n$ , $n+2$ , $n+4$ is divisible by 3" using proof by cases. The student divides based on $n \pmod{3}$ and correctly handles the case $n \equiv 0 \pmod{3}$ . In analyzing the case $n \equiv 1 \pmod{3}$ , which number in the triple is divisible by 3?
Answer: $n + 2$ , because $n \equiv 1 \pmod{3}$ implies $n + 2 \equiv 3 \equiv 0 \pmod{3}$ , making it divisible by 3. If n ≡ 1 (mod 3), then n + 2 ≡ 1 + 2 ≡ 3 ≡ 0 (mod 3), so n + 2 is divisible by 3. Choice A is wrong because n has remainder 1, not 0. Choice C is incorrect since n + 4 ≡ 1 + 4 ≡ 5 ≡ 2 (mod 3), giving remainder 2. Choice D misses the point by discussing the sum rather than identifying which individual number in the triple is divisible by 3.
In a proof by cases for "if $a$ and $b$ are integers with $a^2 + b^2$ even, then $a$ and $b$ have the same parity," what is the most significant logical flaw in considering only two cases: Case 1 (both $a$ and $b$ even) and Case 2 (both $a$ and $b$ odd)?
Answer: The case division incorrectly assumes the conclusion, making the proof circular by only considering cases where the conclusion holds. This case division assumes what we're trying to prove. A proper proof by cases should consider all possible parity combinations: (even, even), (even, odd), (odd, even), and (odd, odd). Then show that only the first and last cases can satisfy the hypothesis a² + b² even, thus proving the conclusion. Choice A misunderstands the logical structure, Choice B identifies incompleteness but doesn't recognize the circularity, and Choice D incorrectly focuses on zero as a special case.
A proof by cases for the statement " $n^4 - n^2$ is divisible by 12 for all integers $n$ " requires showing divisibility by both 3 and 4. If a student chooses to prove divisibility by 4 using cases based on $n \pmod{4}$ , which case requires the most careful analysis?
Answer: Case: $n \equiv 2 \pmod{4}$ , because this requires showing that $16k^4 + 32k^3 + 20k^2 - 4k$ is divisible by 4. For n ≡ 2 (mod 4), we have n = 4k + 2, so n⁴ - n² = (4k + 2)⁴ - (4k + 2)². The expansion yields multiple terms, and careful factoring is needed to show divisibility by 4. The other cases are more straightforward: Case A gives immediate divisibility, while Cases B and D, though requiring algebra, follow more standard patterns. Case C requires the most detailed algebraic manipulation to demonstrate the divisibility property.
Consider the statement: "For any integer $n \geq 2$ , either $n$ is prime or $n$ has a prime divisor $p \leq \sqrt{n}$ ." A student plans to prove this by cases, dividing based on whether $n$ is prime or composite. What is the primary weakness in this approach?
Answer: The case division creates a circular argument since determining whether $n$ is prime or composite requires the very result being proved. The proposed case division (prime vs. composite) is circular because to determine which case applies, we would need to already know whether n is prime—which is essentially what the statement is designed to help us determine efficiently. A better approach would use contradiction or direct construction. Choice B suggests an irrelevant distinction, Choice C proposes an overly complex division, and Choice D incorrectly accepts the circular logic as sound.
A student proves that " $\sqrt{2}$ is irrational" using proof by cases on the parity of integers $p$ and $q$ in the fraction $\frac{p}{q}$ . The student considers four cases: (even, even), (even, odd), (odd, even), and (odd, odd). Which case analysis contains a fundamental error?
Answer: Case (even, even): This case should be excluded from consideration because it violates the assumption that $\gcd(p,q) = 1$ . In the standard proof that √2 is irrational, we assume √2 = p/q where gcd(p,q) = 1 (fraction in lowest terms). The case (even, even) violates this assumption since both p and q would share the common factor 2. The correct approach shows that cases (even, odd) and (odd, even) both lead to contradictions from p² = 2q². Choice B is wrong since this case is algebraically straightforward, Choice C misunderstands the contradiction mechanism, and Choice D is incorrect as this case does lead to contradiction.
To prove that " $\lfloor 2x \rfloor = 2\lfloor x \rfloor$ or $\lfloor 2x \rfloor = 2\lfloor x \rfloor + 1$ for any real number $x$ " using proof by cases, the critical case division depends on the fractional part of $x$ . What is the key threshold that determines which equality holds?
Answer: The threshold is whether the fractional part of $x$ is less than $\frac{1}{2}$ or at least $\frac{1}{2}$ , since this determines whether $2x$ has fractional part less than 1 Let $x = n + f$ where $n$ is an integer and $0 \leq f < 1$ is the fractional part. Then $2x = 2n + 2f$ . If $f < \frac{1}{2}$ , then $2f < 1$ , so $\lfloor 2x \rfloor = \lfloor 2n + 2f \rfloor = 2n = 2\lfloor x \rfloor$ . If $f \geq \frac{1}{2}$ , then $2f \geq 1$ , so $\lfloor 2x \rfloor = \lfloor 2n + 2f \rfloor = 2n + 1 = 2\lfloor x \rfloor + 1$ . The threshold $\frac{1}{2}$ is critical because it determines when $2f$ crosses the integer boundary. Choices A and D use incorrect thresholds. Choice C is insufficient since it only addresses one case.

Start this quiz