Home / Courses / Intro to Proofs / Unit 3

Intro to Proofs Unit 3: Direct Proof

A direct proof starts from the hypothesis, unpacks the definitions, and uses algebra and known facts to arrive at the conclusion. This is the workhorse method for statements about integers, divisibility and rational numbers.

Covers: Definitions: even, odd, divisibility, rational, Structure of a direct proof, Parity proofs, Divisibility proofs, Proof by cases, Rational number proofs, Common proof-writing errors

Study guide

Proofs run on definitions, so state them precisely. An integer n is even if n = 2k for some integer k, and odd if n = 2k + 1 for some integer k. For integers a ≠ 0 and b, a divides b (written a | b) if b = ak for some integer k. A real number r is rational if r = a/b for integers a and b with b ≠ 0. Each definition is an existence statement, so using it means introducing a new integer, and proving it means producing one. Most beginner proofs that go wrong do so because a definition was paraphrased loosely instead of written out exactly.

To prove P → Q directly, assume P, then reason step by step until you reach Q. A clean template: 'Suppose n is odd. Then n = 2k + 1 for some integer k. So n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. Since 2k² + 2k is an integer, n² is odd.' Notice the final step explicitly matches the definition of the conclusion. When two different objects appear, give them different letters: m = 2a + 1 and n = 2b + 1, never 2k + 1 for both, because that silently assumes m = n.

Divisibility proofs follow the same pattern. If a | b and a | c, write b = ak and c = al; then b + c = a(k + l) and any combination xb + yc = a(xk + yl), so a divides it. Transitivity, if a | b and b | c then a | c, comes from substituting: c = bl = a(kl). Factoring is your main tool: n³ − n = (n − 1)n(n + 1) is a product of three consecutive integers, which must include a multiple of 2 and a multiple of 3. For rational numbers, combine the fractions, then check that the numerator and denominator are integers and that the denominator is nonzero.

Proof by cases splits the hypothesis into exhaustive possibilities and proves the conclusion in each one. Parity (n even or n odd), sign (x ≥ 0 or x < 0) and comparison (a ≥ b or a < b) are the most common splits. The cases must cover everything, and each case needs its own complete argument. Common errors to avoid: proving the converse by assuming the conclusion, checking examples instead of an arbitrary element, reusing a variable, and dividing by an expression that might be zero. Write in full sentences, so that each line clearly follows from earlier lines or a stated fact.

Key ideas

• Every proof step should follow from the hypothesis, a definition, or a known result.
• Even, odd, divisibility and rational are existence definitions: each introduces an integer.
• Different arbitrary objects need different variable names.
• Finish by showing the conclusion matches its definition exactly, such as 2(integer) + 1.
• If a divides b and c, it divides every integer combination of b and c.
• A product of k consecutive integers is divisible by k.
• Cases in a proof by cases must be exhaustive, and each must be proved.

Formulas and rules

Common mistakes

• Using the same letter k for two different numbers, such as m = 2k + 1 and n = 2k + 1.
• Proving a statement by checking a few examples.
• Starting from the conclusion and working backward, which proves the converse.
• Forgetting to show that the new quantity, such as 2k² + 2k, is an integer.
• Writing cases that do not cover every possibility, such as positive and negative but not zero.

Before the test, make sure you can

• State the definitions of even, odd, divides and rational precisely.
• Write a direct proof of a parity statement such as 'odd squared is odd'.
• Prove divisibility facts such as transitivity and divisibility of combinations.
• Prove that sums, products and quotients of rational numbers are rational.
• Set up and complete a proof by cases with exhaustive cases.
• Spot common errors: reused variables, assuming the conclusion, proof by example.
• Give a counterexample to a false divisibility claim.

Words to know

Even integer

n is even if n = 2k for some integer k.

Odd integer

n is odd if n = 2k + 1 for some integer k.

Divides

a | b means b = ak for some integer k (a ≠ 0).

Rational number

A number a/b with a and b integers and b ≠ 0.

Direct proof

A proof of P → Q that assumes P and derives Q.

Proof by cases

A proof that splits into exhaustive possibilities and proves the claim in each.

Parity

Whether an integer is even or odd.

Arbitrary element

A general element chosen without any special properties, so the argument applies to all.

Closure

Sums, differences and products of integers are integers.

Transitivity of divisibility

If a | b and b | c, then a | c.

Consecutive integers

Integers n, n + 1, n + 2, ...; any k of them contain a multiple of k.

Lemma

A smaller result proved to help prove a larger theorem.

Corollary

A result that follows quickly from a theorem just proved.

Theorem

A significant statement that has been proved true.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.