Proof by Induction & Contradiction - IB Mathematics Analysis and Approaches

Which of the following mathematical propositions is most appropriately proven using proof by contradiction?
Answer: The sum of a rational number and an irrational number is irrational. Proofs about the nature of numbers (rational, irrational) are often best handled by contradiction. To prove 'the sum of a rational and an irrational is irrational,' you would assume the opposite: that the sum is rational. This allows you to perform algebraic manipulations that lead to a clear contradiction. The other options are standard results typically proven by mathematical induction (A and C) or by direct algebraic derivation (D).
In the proof of De Moivre's theorem by induction, $(\cos\theta + i\sin\theta)^n = \cos(n\theta) + i\sin(n\theta)$ , the inductive step involves expanding $(\cos(k\theta) + i\sin(k\theta))(\cos\theta + i\sin\theta)$ . After expansion, what is the real part of the resulting complex number?
Answer: $\cos(k\theta)\cos\theta - \sin(k\theta)\sin\theta$ When approaching De Moivre's theorem proofs by induction, you're working with complex number multiplication where the key is carefully tracking real and imaginary parts through algebraic expansion. To find the real part of $(\cos(k\theta) + i\sin(k\theta))(\cos\theta + i\sin\theta)$ , you need to multiply these complex numbers using the distributive property: $(\cos(k\theta) + i\sin(k\theta))(\cos\theta + i\sin\theta)$ $= \cos(k\theta)\cos\theta + \cos(k\theta)(i\sin\theta) + (i\sin(k\theta))\cos\theta + (i\sin(k\theta))(i\sin\theta)$ Simplifying each term: - First term: $\cos(k\theta)\cos\theta$ (real) - Second term: $i\cos(k\theta)\sin\theta$ (imaginary) - Third term: $i\sin(k\theta)\cos\theta$ (imaginary) - Fourth term: $i^2\sin(k\theta)\sin\theta = -\sin(k\theta)\sin\theta$ (real, since $i^2 = -1$ ) The real part combines the first and fourth terms: $\cos(k\theta)\cos\theta - \sin(k\theta)\sin\theta$ , which is answer D. Choice A omits the crucial negative sign from the $i^2$ term. Choice B gives you the imaginary part instead of the real part. Choice C has the wrong signs on both terms—it's mixing up which terms are positive and negative. Study tip: In complex multiplication problems, always remember that $i^2 = -1$ creates negative real terms, and systematically separate real from imaginary parts during expansion. This pattern appears frequently in trigonometric identities and complex number proofs.
In a proof by mathematical induction for a statement $P(n)$ , it is shown that $P(2)$ is true. It is also shown that for any integer $k \ge 2$ , the truth of $P(k)$ implies the truth of $P(k+2)$ . What can be concluded?
Answer: $P(n)$ is true for all even integers $n \ge 2$ . The base case establishes that $P(2)$ is true. The inductive step, $P(k) \implies P(k+2)$ , shows that if the statement is true for an integer, it is also true for the integer that is 2 greater. Starting from the base case $P(2)$ , the implication shows that $P(4)$ must be true. From $P(4)$ , we deduce $P(6)$ is true, and so on. This chain of logic establishes the truth of $P(n)$ for all even integers $n \ge 2$ . We cannot conclude anything about odd integers because there is no odd base case.
A student correctly completes a proof by contradiction to show that the sum of the angles in a triangle is $180^{\circ}$ . Which of the following would have been their initial assumption?
Answer: Assume there exists a triangle whose angle sum is not equal to $180^{\circ}$ . When you encounter a proof by contradiction question, you need to understand how this logical technique works. In proof by contradiction, you temporarily assume the opposite of what you want to prove, then show this assumption leads to a logical contradiction, thereby proving your original statement must be true. Since the student wants to prove that the sum of angles in a triangle is $180°$ , they must start by assuming the negation of this statement. The correct initial assumption would be "assume there exists a triangle whose angle sum is not equal to $180°$ " - option D. From this assumption, the student would derive geometric contradictions (perhaps using parallel line properties or other geometric axioms), ultimately showing that such a triangle cannot exist, therefore proving all triangles must have angle sums of $180°$ . Option A assumes what you're trying to prove, which defeats the purpose of proof by contradiction. Option B shifts focus to quadrilaterals, which is irrelevant to proving something about triangles. Option C makes too strong an assumption by claiming ALL triangles have non- $180°$ angle sums - this universal statement is harder to work with than the existential claim that at least one such triangle exists. The key insight is that in proof by contradiction, you only need to assume one counterexample exists to create a contradiction. If you can show that even one triangle with a non- $180°$ angle sum leads to impossibility, you've proven the statement for all triangles. Study tip: For proof by contradiction questions, always look for the assumption that negates what you want to prove, typically starting with "assume there exists..." rather than "assume all..."
To prove that there are infinitely many prime numbers, the proof by contradiction begins by assuming there is a finite number of primes, $p_1, p_2, \dots, p_n$ . A new number $N = p_1 p_2 \dots p_n + 1$ is constructed. The argument then states that $N$ must have a prime factor. What contradiction is ultimately reached?
Answer: The prime factor of $N$ cannot be any of the primes in the finite list, contradicting that the list was complete. When $N$ is divided by any of the primes $p_1, p_2, \dots, p_n$ from the supposedly complete list, there is a remainder of 1. This means that none of these primes are factors of $N$ . However, by the fundamental theorem of arithmetic, $N$ must have a prime factor (either it is prime itself, or it is composite). This prime factor is not on the list $p_1, \dots, p_n$ . This contradicts the initial assumption that the list of all prime numbers was finite and complete.
A student attempts to prove that if $ab$ is an irrational number, then either $a$ or $b$ is irrational. The student writes: 'Assume $a$ and $b$ are both rational. Let $a = p/q$ and $b = r/s$ for integers $p, q, r, s$ . Then $ab = pr/qs$ , which is rational. This contradicts the fact that the product of two rationals must be irrational.' Besides the error in the final sentence, what is the primary logical issue with this argument as a proof by contradiction?
Answer: The student has correctly proven the contrapositive, not used proof by contradiction. The original statement is $P \implies Q$ , where $P$ is ' $ab$ is irrational' and $Q$ is ' $a$ is irrational or $b$ is irrational'. A proof by contradiction would assume $P \text{ and not } Q$ , which is 'ab is irrational AND a is rational AND b is rational'. The student instead assumed $\text{not } Q$ ('a is rational AND b is rational') and proved $\text{not } P$ ('ab is rational'). Proving $\text{not } Q \implies \text{not } P$ is a valid proof of the contrapositive, which is logically equivalent to $P \implies Q$ . However, it is not a proof by contradiction.
Let $M = \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}$ . It is proposed that $M^n = \begin{pmatrix} 2n+1 & -4n \\ n & 1-2n \end{pmatrix}$ for $n \in \mathbb{Z}^+$ . In the inductive step, assuming the formula is true for $n=k$ , we compute $M^{k+1} = M^k M$ . What is the entry in the first row, first column of the resulting matrix $M^{k+1}$ ?
Answer: $2k+3$ We are computing $M^{k+1} = M^k M = \begin{pmatrix} 2k+1 & -4k \\ k & 1-2k \end{pmatrix} \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}$ . The entry in the first row, first column is found by taking the dot product of the first row of $M^k$ and the first column of $M$ . This gives $(2k+1)(3) + (-4k)(1) = 6k+3-4k = 2k+3$ . This matches the formula for $n=k+1$ , as $2(k+1)+1 = 2k+2+1 = 2k+3$ .
Let $P(n)$ be a statement to be proven by induction for $n \in \mathbb{Z}^+$ . If the base case $P(1)$ is false, but the inductive step (that is, $P(k) \implies P(k+1)$ for all $k \ge 1$ ) is proven to be valid, what can be concluded?
Answer: $P(n)$ is false for all $n \in \mathbb{Z}^+$ . Mathematical induction can be thought of as a chain of dominoes. The base case, $P(1)$ , is the act of knocking over the first domino. The inductive step, $P(k) \implies P(k+1)$ , ensures that each domino is positioned to knock over the next. If the first domino is never knocked over ( $P(1)$ is false), the chain reaction never starts. Since the implication $P(k) \implies P(k+1)$ requires $P(k)$ to be true to conclude anything about $P(k+1)$ , and we know $P(1)$ is false, we can never establish that $P(2)$ is true. Consequently, we can't establish $P(3)$ is true, and so on. Therefore, the statement is false for all $n \in \mathbb{Z}^+$ .
Let $P(n)$ be the proposition that $8^n - 3^n$ is divisible by 5. In the inductive step, assuming $P(k)$ is true, we consider $8^{k+1} - 3^{k+1}$ . Which of the following expressions is a valid manipulation that helps to complete the proof?
Answer: $8(8^k - 3^k) + 5 \cdot 3^k$ We start with $8^{k+1} - 3^{k+1} = 8 \cdot 8^k - 3 \cdot 3^k$ . To use the inductive hypothesis (that $8^k - 3^k$ is divisible by 5), we must isolate the term $8^k - 3^k$ . We can rewrite the expression as $8 \cdot 8^k - 8 \cdot 3^k + 8 \cdot 3^k - 3 \cdot 3^k$ . This simplifies to $8(8^k - 3^k) + (8-3) \cdot 3^k = 8(8^k - 3^k) + 5 \cdot 3^k$ . Since $8^k - 3^k$ is divisible by 5 by the inductive hypothesis, $8(8^k - 3^k)$ is divisible by 5. Also, $5 \cdot 3^k$ is clearly divisible by 5. The sum of two numbers divisible by 5 is also divisible by 5, completing the proof.
Let $P(n)$ be a statement about a positive integer $n$ . It is found that $P(50)$ is true. It is also proven that for any integer $k > 1$ , the truth of $P(k)$ implies the truth of $P(k-1)$ . What is the strongest conclusion that can be made?
Answer: $P(n)$ is true for all integers $n$ such that $1 \le n \le 50$ . This question tests your understanding of mathematical induction, specifically "backward induction" or "strong induction in reverse." When you see conditions about statements being true for one value and implications flowing in a particular direction, think carefully about which way the logical chain works. You're given that $P(50)$ is true, and that for any integer $k > 1$ , if $P(k)$ is true, then $P(k-1)$ is also true. This creates a "domino effect" moving backward from 50. Since $P(50)$ is true, and $50 > 1$ , you can apply the implication to conclude $P(49)$ is true. Since $P(49)$ is true and $49 > 1$ , you get $P(48)$ is true. This pattern continues all the way down to $P(1)$ , since you can keep applying the implication as long as $k > 1$ . Choice A is wrong because the implication works backward (from $k$ to $k-1$ ), not forward to larger values. You have no information about $P(51), P(52),$ etc. Choice B is wrong because while you can prove $P(n)$ for $n = 1, 2, 3, ..., 50$ , you cannot extend beyond 50 without additional information. Choice C is wrong because the backward implication allows you to prove much more than just $P(50)$ - you can prove all cases from 1 to 50. Choice D is correct because the backward chain of implications establishes $P(n)$ for every integer from 1 to 50. Remember: in induction problems, pay close attention to the direction of the implication. The logical flow determines exactly which values you can prove.
A sequence is defined by $a_1=2, a_2=3$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 3$ . A proof by induction is used to show that $a_n = 2^n + (-1)^n$ for all $n \in \mathbb{Z}^+$ . Why is a standard inductive hypothesis (assuming the proposition is true for $n=k$ ) insufficient for the inductive step?
Answer: The recurrence relation for $a_{k+1}$ depends on two preceding terms, $a_k$ and $a_{k-1}$ . In the inductive step, we need to prove the formula for $a_{k+1}$ . The recurrence is $a_{k+1} = a_k + 2a_{k-1}$ . To use the formula we are trying to prove, we need to substitute expressions for both $a_k$ and $a_{k-1}$ . A standard inductive hypothesis only assumes the formula is true for $n=k$ . Therefore, we need a stronger hypothesis, one that assumes the formula is true for both $n=k$ and $n=k-1$ (or for all integers up to $k$ ), which is known as strong induction.
To prove by contradiction that in any simple graph with $n \ge 2$ vertices, there must be at least two vertices with the same degree, what is a valid initial assumption?
Answer: Assume there is a graph with $n$ vertices where all vertices have different degrees. When you encounter a proof by contradiction problem, you need to identify what assumption would contradict the statement you're trying to prove. Here, you want to prove that any simple graph with $n \geq 2$ vertices must have at least two vertices with the same degree. In proof by contradiction, you assume the opposite of what you want to prove, then show this leads to an impossibility. The opposite of "at least two vertices have the same degree" is "all vertices have different degrees." So you'd assume there exists a graph where all $n$ vertices have completely different degrees, then demonstrate this is impossible. Here's why: In a simple graph with $n$ vertices, each vertex can have degree 0, 1, 2, ..., or $n-1$ (at most $n-1$ since it can't connect to itself). That gives you exactly $n$ possible degree values. However, if one vertex has degree 0 (connected to nothing), then no vertex can have degree $n-1$ (connected to everything), since that would require connecting to the isolated vertex. This means you actually have fewer than $n$ available degree values for $n$ vertices, making it impossible for all vertices to have different degrees. Option A assumes what you're trying to prove (same degrees), not its opposite. Option B describes a specific graph type (no edges) rather than negating the theorem. Option C focuses on an impossible degree situation but doesn't address the "different degrees" aspect. Remember: In contradiction proofs, always assume the exact logical opposite of your target statement, then show that assumption creates an impossibility.
To prove that $\log_3 10$ is irrational by contradiction, one assumes $\log_3 10 = \frac{p}{q}$ for integers $p, q$ with $q ≠ 0$ . Rewriting this gives $3^{p/q} = 10$ , or $3^p = 10^q$ . Why does this final equation represent a contradiction for positive integers $p$ and $q$ ?
Answer: $3^p$ has only 3 as a prime factor, while $10^q$ has prime factors 2 and 5. The equation is $3^p = 10^q = (2 \cdot 5)^q = 2^q 5^q$ . According to the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization. The prime factorization of the left side, $3^p$ , consists only of the prime number 3. The prime factorization of the right side, $10^q$ , consists of the prime numbers 2 and 5. Since these prime factorizations are different, the two numbers cannot be equal. This is a contradiction.
In the standard proof by contradiction that $\sqrt{5}$ is irrational, we assume $\sqrt{5} = \frac{p}{q}$ where $p, q \in \mathbb{Z}$ and the fraction is in its simplest form (i.e., $\gcd(p,q)=1$ ). The proof leads to the conclusion that both $p$ and $q$ must be multiples of 5. What is the primary contradiction reached at this point?
Answer: The assumption that $p$ and $q$ have no common factors is violated. The proof begins by assuming the fraction $\frac{p}{q}$ is in its simplest form, meaning $p$ and $q$ share no common factors other than 1. The steps of the proof then logically deduce that both $p$ and $q$ must have a factor of 5. This means they share a common factor, which directly contradicts the initial assumption that the fraction was in its simplest form. This is the fundamental contradiction that completes the proof.
The reasoning in the inductive step is flawed. For which value of $k$ does the argument fail?
Answer: $k=1$ The flaw lies in the transition from $k=1$ to $k+1=2$ . The argument relies on the overlap between the two sets of $k$ horses (the 'middle horses'). When considering a set of $k+1=2$ horses, $H_1, H_2$ , the first subset is $\{H_2\}$ and the second is $\{H_1\}$ . There is no overlap or 'middle horse' to link the color of $H_1$ to $H_2$ . The logic of the argument only works if the two subsets of size $k$ have a non-empty intersection, which requires $k > 1$ . Therefore, the argument fails for $k=1$ .
To prove by contradiction that for all integers $n$ , if $n^2$ is a multiple of 3, then $n$ is a multiple of 3, what is the correct initial assumption?
Answer: Assume there exists an integer $n$ such that $n^2$ is a multiple of 3, and $n$ is not a multiple of 3. A proof by contradiction for a statement of the form $P \implies Q$ begins by assuming $P$ is true and $Q$ is false. Here, $P$ is ' $n^2$ is a multiple of 3' and $Q$ is ' $n$ is a multiple of 3'. Therefore, the correct initial assumption is to assume there exists an integer $n$ for which $n^2$ is a multiple of 3 (P is true) and $n$ is not a multiple of 3 (Q is false).
A student is proving by induction that $\sum_{r=1}^{n} r^3 = \left( \frac{n(n+1)}{2} \right)^2$ . They correctly assume the formula for $n=k$ . Which expression correctly represents the value that must be added to $\left( \frac{k(k+1)}{2} \right)^2$ to begin the proof for $n=k+1$ ?
Answer: $(k+1)^3$ The inductive step is to show that $\sum_{r=1}^{k+1} r^3 = \left( \frac{(k+1)(k+2)}{2} \right)^2$ . We can write the sum to $k+1$ as the sum to $k$ plus the $(k+1)$ -th term. So, $\sum_{r=1}^{k+1} r^3 = \left( \sum_{r=1}^{k} r^3 \right) + (k+1)^3$ . Using the inductive hypothesis, this becomes $\left( \frac{k(k+1)}{2} \right)^2 + (k+1)^3$ . Therefore, the term that must be added is $(k+1)^3$ .
We wish to prove by induction that $(n+1)! > 4^n$ for all integers $n \ge N$ . What is the smallest integer value of $N$ that can be used as a valid base case?
Answer: 6 We must find the smallest integer $N$ for which the inequality $(N+1)! > 4^N$ holds. Let's test values: For $n=1$ : $2! = 2, 4^1 = 4$ . $2 \ngtr 4$ . For $n=2$ : $3! = 6, 4^2 = 16$ . $6 \ngtr 16$ . For $n=3$ : $4! = 24, 4^3 = 64$ . $24 \ngtr 64$ . For $n=4$ : $5! = 120, 4^4 = 256$ . $120 \ngtr 256$ . For $n=5$ : $6! = 720, 4^5 = 1024$ . $720 \ngtr 1024$ . For $n=6$ : $7! = 5040, 4^6 = 4096$ . $5040 > 4096$ . The inequality holds. Therefore, the smallest integer value for the base case is $N=6$ .
In a proof by induction for the statement $S(n): \sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}$ for $n \in \mathbb{Z}^+$ , the inductive step requires proving that if $S(k)$ is true for some $k \in \mathbb{Z}^+$ , then $S(k+1)$ is true. Which of the following equations must be established to complete this inductive step?
Answer: $\frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = \frac{(k+1)(k+2)(k+3)}{3}$ The inductive step assumes $S(k)$ is true, so $\sum_{i=1}^{k} i(i+1) = \frac{k(k+1)(k+2)}{3}$ . We need to prove $S(k+1)$ is true, which is $\sum_{i=1}^{k+1} i(i+1) = \frac{(k+1)(k+2)(k+3)}{3}$ . We start with the left side of $S(k+1)$ : $\sum_{i=1}^{k+1} i(i+1) = \left(\sum_{i=1}^{k} i(i+1)\right) + (k+1)((k+1)+1)$ . Using the inductive hypothesis, this becomes $\frac{k(k+1)(k+2)}{3} + (k+1)(k+2)$ . We must show this equals the right side of $S(k+1)$ , so the required equation is $\frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = \frac{(k+1)(k+2)(k+3)}{3}$ .

Start this quiz