Reason with direct and indirect proof methods

A proof is a justified argument

A proof explains why a statement follows for every allowed case. First identify the domain, hypotheses and conclusion. A direct proof starts from the hypotheses. A contrapositive proof denies the conclusion and deduces failure of the hypothesis. A contradiction proof assumes the desired claim is false and reaches an impossibility. We will give complete arguments, not just name the methods. Induction has its own next section

1. 1Begin with the hypotheses, not the conclusion A direct proof starts from the stated assumptions and established definitions or results. Use an arbitrary member of the domain, not one chosen example. Each step must be justified

To begin a proof about every even integer, which is the useful general opening?

Definitions supply integer witnesses

Let r and s denote integers. Even integers have form 2r, and odd integers have form 2r + 1. The witnesses may be negative or zero. If two arbitrary odd integers are involved, write a = 2r + 1 and b = 2s + 1; using the same witness would silently assume a = b. For a positive integer d, divisibility d divides n means n = dk for some integer k. Zero and negative multiples are allowed

1. 1Write the integer witnesses An even integer is 2r and an odd integer is 2r + 1 for an integer r. For a positive integer a, a divides b means b = ak for an integer k. Two arbitrary integers need independent witness letters unless equality is given \(\displaystyle \begin{gathered}a\mid b\iff b=ak\\\text{for some }k\in\mathbb Z\end{gathered}\)

Direct proof: the sum of two odd integers is even

Let a and b be arbitrary odd integers. Then a = 2r + 1 and b = 2s + 1 for some integers r and s. Adding and factoring gives the expression below. Since r + s + 1 is an integer, a + b is twice an integer and hence even. The argument used no restriction on the signs of a or b, so it proves the statement for all odd integers

1. 1Explain why the final form proves the claim After obtaining twice an expression, state that the expression is an integer before concluding evenness. For divisibility, identify the integer multiplier. Algebra alone should not leave the logical conclusion unstated

Why is a = 2r + 1 and b = 2r + 1 not a valid representation of two arbitrary odd integers?

Direct proof: divisibility passes through a chain

Let a and b be positive integers and c an integer. Assume a divides b and b divides c. By definition b = ar and c = bs for some integers r and s. Substitution gives c = a(rs). Because rs is an integer, this is exactly the definition that a divides c. The conclusion follows from both hypotheses, not from comparing the sizes of the numbers

Written practice 1: odd products (ungraded)

Write a complete direct proof that the product of any two odd integers is odd. State the domain, choose independent integer witnesses, expand and identify the integer in the final odd form

Model 1: product of two odd integers

Let a and b be arbitrary odd integers. There are integers r and s with a = 2r + 1 and b = 2s + 1. Expand their product as below. The quantity 2rs + r + s is an integer, so the product is twice an integer plus 1. Thus ab is odd for all odd integers a and b. Compare the complete argument with your own, not just the final formula

A direct proof by exhaustive cases

For any integer n, either n is even or n is odd. If n = 2k, then n(n + 1) = 2[k(2k + 1)], which is even. If n = 2k + 1, then n + 1 = 2(k + 1), so n(n + 1) = 2[(2k + 1)(k + 1)], also even. Each bracket is an integer. The two cases exhaust all integers, including zero and negatives, so n(n + 1) is always even

Which proposed case split fails to cover all integers because it omits zero?

Direct proof of a real inequality

Let a and b be arbitrary real numbers. Every real square is nonnegative, so (a − b)² ≥ 0. Expanding and adding 2ab to both sides proves a² + b² ≥ 2ab. Equality holds exactly when the square is zero, which is exactly a = b. Nothing requires a and b to be positive. State the real domain because this uses the order properties of real numbers

1. 1Use a real square for an inequality For real a and b, the difference between a² + b² and 2ab is (a − b)². It is nonnegative, with equality exactly when a = b. A proof by cases must cover every allowed value

When does equality hold in a² + b² ≥ 2ab for real a and b?

Written practice 2: an inequality and its equality case (ungraded)

For arbitrary real a and b, prove a² + 4b² ≥ 4ab. Identify the square that gives the proof and state exactly when equality holds. Do not assume that a or b is positive. Write the complete reasoning before opening the model

Model 2: use the correct square

Let a and b be real. The real square (a − 2b)² is nonnegative. Expanding and rearranging gives a² + 4b² ≥ 4ab. Equality holds if and only if a − 2b = 0, that is, a = 2b. The argument establishes both the inequality and its complete equality condition

Contrapositive: use an equivalent implication

An implication P implies Q is equivalent to not Q implies not P. Proving the latter establishes the former. For integers, not even is odd and not odd is even. To prove that n² even implies n even, start with an arbitrary odd integer n and prove its square is odd. Merely proving that an even integer has an even square would prove the converse instead

1. 1Prove the contrapositive To prove if P then Q, one may instead start from not Q and deduce not P. The two implications are logically equivalent. The converse, if Q then P, is a different claim \(\displaystyle \begin{gathered}(P\implies Q)\\\iff(\neg Q\implies\neg P)\end{gathered}\)

Which statement is the contrapositive of “if n² is even, then n is even”, for integer n?

Complete contrapositive proof

Let n be an arbitrary odd integer, so n = 2k + 1 for some integer k. Expanding gives n² = 2(2k² + 2k) + 1. The bracket is an integer, so n² is odd. We have proved that n odd implies n² odd. By contraposition, for every integer n, if n² is even then n is even. The final sentence returns to the original claim

Why does 2(2k² + 2k) + 1 establish oddness when k is an integer?

Written practice 3: reverse the parity conclusion (ungraded)

Prove by contraposition that if the square of an integer n is odd, then n is odd. State the contrapositive first, prove it from the definition of an even integer, then return to the original claim. This is a different implication from the preceding example

Model 3: an even input has an even square

The contrapositive is: if n is even, then n² is even. Let n = 2k for an arbitrary integer k. Then n² = 4k² = 2(2k²). Since 2k² is an integer, n² is even. This proves the contrapositive; therefore if an integer square is odd, the integer is odd

Contradiction and lowest terms

To prove a statement by contradiction, assume its negation and deduce incompatible facts. To prove a real number irrational, suppose instead it is rational. Write it in lowest terms with integer numerator p and positive integer denominator q: p and q share no factor greater than 1. Every rational number admits such a representation. If the argument then forces a common factor, the rationality assumption fails

1. 1State the contradiction precisely Assume the negation of the desired claim and derive incompatible statements. For an irrationality proof, a rational number can be written with integer numerator and positive denominator in lowest terms. A common factor then contradicts that choice

Why choose the fraction p/q in lowest terms at the start of an irrationality proof?

An independent lemma about prime factors

Let p be a prime and m an integer. If m = 0 then p divides m immediately. If |m| = 1, then m² = 1 is not divisible by a prime, so the hypothesis cannot hold. Otherwise factor |m| > 1 into primes, using the fundamental theorem of arithmetic from 1C. Squaring doubles each prime multiplicity and introduces no new prime. Therefore, if p divides m², p already occurs in |m| and hence divides m. This lemma is independent of any claim about square roots. It does not hold for every composite divisor: 4 divides 2² but does not divide 2.

1. 1Justify the prime-square step independently If a prime divides an integer square, it divides the integer. For absolute value greater than 1, unique prime factorisation proves this because squaring doubles existing prime multiplicities without adding a new prime. Zero satisfies the conclusion immediately; at absolute value 1 the hypothesis is false

Complete contradiction proof: the square root of 3

Suppose the positive square root of 3 is rational. Choose integers p and q with q > 0 and no common factor greater than 1 such that √3 = p/q. Squaring gives p² = 3q², so 3 divides p². By the prime-square lemma, p = 3r for an integer r. Substitute and divide by 3 to obtain q² = 3r². The same lemma now shows that 3 divides q. Thus 3 divides both p and q, contradicting lowest terms. The rationality assumption is false, so √3 is irrational

After p² = 3q² and p = 3r, which equation is the correct next algebraic step?

Suppose √3 = p/q, where p and q are integers, q > 0, and p/q is in lowest terms. A proof shows that 3 divides both p and q. What is the contradiction?

Written practice 4: a new irrationality proof (ungraded)

Prove that the positive square root of 5 is irrational. Use the independently justified prime-square lemma, not a decimal approximation. Include the reduced rational assumption, both divisibility deductions, the exact contradiction and the conclusion

Model 4: the square root of 5

Suppose √5 is rational and choose √5 = p/q in lowest terms with integers p and q and q > 0. Squaring gives p² = 5q². Since 5 is prime, the prime-square lemma gives 5 divides p, so p = 5r for some integer r. Substitution yields 25r² = 5q², hence q² = 5r². The lemma gives 5 divides q as well. This contradicts the absence of a common factor greater than 1. Therefore √5 is irrational

Audit your argument, not just its answer

Check that every arbitrary value stays in its domain, every multiplier claimed to be an integer really is one, all cases are covered and every division uses a nonzero divisor. Do not assume the conclusion, use the converse as a substitute for the contrapositive, or justify a lemma with the theorem it is meant to prove. The finite practice checks recognise selected steps only. Your complete written proofs remain ungraded; compare them with the models and explain any differences

1. 1Check domains and legal operations Division requires a nonzero divisor. Nonnegative-square arguments use real numbers. Examples may suggest a claim but do not prove it over an infinite domain. A model proof is teaching, not a score for your own proof

A supposed proof assumes a = b and later cancels the factor a − b. Which condition fails?