Proof by induction, contradiction, counterexample practice questions.

In the proof by contradiction that there are infinitely many primes, one assumes the primes are exactly p₁, p₂, …, p_N and considers M = p₁p₂⋯p_N + 1. The contradiction arises because:

• M must itself be prime, since it is larger than every listed prime p_N
• M is even, so it is divisible by 2
• No listed prime divides M, yet M > 1 must have a prime factor
• M is smaller than the product of the listed primes

Answer: No listed prime divides M, yet M > 1 must have a prime factor

M ≡ 1 (mod pᵢ) for each listed prime, so none of them divides M; but M > 1 must have some prime factor, which therefore was not on the list. Note M need not itself be prime — that is a common misconception.

A proof by induction shows that 5ⁿ − 1 is divisible by 4 for all integers n ≥ 1. In the inductive step, 5^(k+1) − 1 is rewritten as 5(5^k − 1) + c. Determine the value of c.

• 4
• 5
• 1
• −4

Answer: 4

5^(k+1) − 1 = 5·5^k − 5 + 4 = 5(5^k − 1) + 4. Since 5^k − 1 is divisible by 4 by the inductive hypothesis and 4 is divisible by 4, the whole expression is divisible by 4.

Which value of x is a counterexample to the claim 'x² ≥ x for all real numbers x'?

• x = 2
• x = 1/2
• x = −1
• x = 0

Answer: x = 1/2

(1/2)² = 1/4 < 1/2, so the claim fails. For x = 2, x = −1 and x = 0 the inequality x² ≥ x actually holds, so they disprove nothing.

A single counterexample disproves a 'for all' statement. To disprove the statement 'there exists a real number x such that P(x)', one must instead:

• Find one value of x for which P(x) fails
• Find two different values of x for which P(x) fails
• Check that P(x) fails for all sufficiently large x
• Prove that P(x) is false for every real number x

Answer: Prove that P(x) is false for every real number x

The negation of an existential statement is universal: 'no x satisfies P(x)'. Exhibiting values where P fails is not enough, since P might still hold somewhere else.

An induction proof establishes that 2ⁿ > n² for all integers n ≥ 5. Which statement about the base case is correct?

• n = 1, because a proof by induction must always start at n = 1
• n = 4, since 2⁴ = 16 equals 4² but is not greater than it
• n = 5, since 2⁵ = 32 > 25 but 2⁴ = 16 is not > 4²
• n = 0, because 2⁰ = 1 > 0

Answer: n = 5, since 2⁵ = 32 > 25 but 2⁴ = 16 is not > 4²

The claimed statement is for n ≥ 5, so the base case is n = 5: 32 > 25. At n = 4 the strict inequality fails (16 = 16), so no earlier base case is possible.

To prove that log₂ 5 is irrational by contradiction, assume log₂ 5 = p/q with p, q positive integers, which gives 2^p = 5^q. The contradiction is that:

• 2^p is even but 5^q is odd, never equal
• p/q cannot be written in lowest terms
• 2^p is always smaller than 5^q
• 5^q is divisible by 2 only when q is even

Answer: 2^p is even but 5^q is odd, never equal

For positive integers p and q, 2^p is even but 5^q ends in 5 and is odd, so 2^p = 5^q is impossible. Hence log₂ 5 cannot be rational.