2.6 Direct proofs

Nature of Direct Proofs

A direct proof establishes the truth of a mathematical statement by starting from what you know and reasoning forward, step by step, until you reach the conclusion. It's the most straightforward proof technique: you assume the hypothesis is true, then show the conclusion must follow.

This matters because direct proofs are the backbone of mathematical reasoning. Every step requires justification, which forces you to understand why something is true rather than just accepting it.

Structure of a Direct Proof

Every direct proof follows the same basic framework:

1. State the theorem you're proving, usually in "if P, then Q" form
2. Assume the hypothesis (P) is true
3. Reason through logical steps, where each step is justified by a definition, axiom, or previously proven result
4. Arrive at the conclusion (Q), showing it follows from the chain of reasoning

The key requirement is that the chain of reasoning is unbroken. Each step builds on the previous one using deductive reasoning, moving from your assumptions toward the specific result you need.

Hypothesis and Conclusion

Most theorems you'll prove take the form "if P, then Q." The hypothesis (P) is your starting assumption. The conclusion (Q) is what you need to show must be true.

For example, in the statement "if $n$ is an even integer, then $n^2$ is even," the hypothesis is "$n$ is even" and the conclusion is "$n^2$ is even." Being precise about which part is which keeps your proof focused.

Logical Statements and Connectives

Proofs rely on propositional logic to build valid arguments. The main connectives you'll use:

• "and" ($\wedge$): both statements are true
• "or" ($\vee$): at least one statement is true
• "if-then" ($\rightarrow$): the hypothesis implies the conclusion
• "if and only if" ($\leftrightarrow$): both directions of implication hold

You'll also use quantifiers like "for all" ($\forall$) and "there exists" ($\exists$) to express universal or existential claims. Rules of inference such as modus ponens (from "P" and "if P then Q," conclude "Q") let you draw valid conclusions from your premises.

Proof Techniques Within Direct Proofs

Forward Reasoning

This is the most natural approach: start with what you're given and work toward the conclusion. You apply definitions, known theorems, and logical rules to derive new statements until you reach the result.

Forward reasoning works best when the path from hypothesis to conclusion is relatively clear. For instance, proving that the sum of two even integers is even: you start by writing each integer using the definition of "even," then add them and show the result fits that same definition.

Backward Reasoning

Sometimes it helps to start from the conclusion and ask, "What would I need to show for this to be true?" Then you work backward until you connect to the given information.

This is especially useful when the conclusion suggests a particular technique or when forward reasoning doesn't reveal an obvious path. In practice, you'll often combine forward and backward reasoning, working from both ends until the argument meets in the middle.

Algebraic Manipulation

Many direct proofs involve transforming equations or expressions. You'll use properties like commutativity, associativity, and distributivity to rewrite expressions, along with techniques like factoring, expanding, and substitution. This is essential for proofs involving equations, inequalities, or identities.

A Worked Example

Theorem: The sum of two even integers is even.

Here's how a direct proof of this works, step by step:

1. Assume the hypothesis. Let $a$ and $b$ be even integers.
2. Apply the definition. By definition of "even," there exist integers $k$ and $m$ such that $a = 2k$ and $b = 2m$.
3. Perform the operation. Then $a + b = 2k + 2m = 2(k + m)$.
4. Connect to the conclusion. Since $k + m$ is an integer, $a + b = 2(k + m)$ is even by definition.

Notice how each step cites a reason. That's what makes it a proof rather than just a calculation.

Common Proof Strategies

Proof by Cases

Sometimes you can't handle all possibilities at once. Instead, you divide the problem into exhaustive, mutually exclusive cases and prove the statement holds in each one separately.

For example, to prove something about all integers, you might split into "$n$ is even" and "$n$ is odd." If the statement holds in both cases, it holds for all integers.

Proof by Contradiction

This is technically an indirect method, but it's worth understanding alongside direct proofs. You assume the negation of what you want to prove and show this leads to a contradiction. Since the negation is impossible, the original statement must be true.

The classic example: proving $\sqrt{2}$ is irrational. You assume it is rational, then show this leads to a contradiction about shared factors.

Proof by Contrapositive

Instead of proving "if P, then Q," you prove the logically equivalent statement "if not Q, then not P." This is useful when working with the negation is easier than working with the original statement directly.

Writing Effective Proofs

Clarity and Precision

• Use clear, concise language. Define any terms or symbols before using them.
• Structure your proof with a logical flow. Numbered steps or short paragraphs both work.
• Every statement should be precise and unambiguous.

Justification of Steps

Each step in your proof needs a reason. Cite the definition, theorem, or axiom that supports it. Don't skip steps you think are "obvious," because what seems obvious to you might not be obvious to your reader (or your grader). If a transition isn't straightforward, explain the reasoning behind it.

Notation

Use standard mathematical notation consistently. If you introduce a variable or symbol, say what it represents. Balance symbolic expressions with verbal explanations so the proof reads naturally.

Common Pitfalls

Circular reasoning happens when you accidentally assume the thing you're trying to prove. For example, if you're proving that $n^2$ is even when $n$ is even, you can't start by assuming $n^2$ is even. Check each step to make sure you're not smuggling in the conclusion.

Insufficient justification means skipping steps or failing to explain why something follows. A proof with gaps isn't a proof. If you can't justify a step, that's a sign you need to think more carefully about why it's true.

Logical gaps occur when you omit crucial connections in your reasoning. Watch out for edge cases or special conditions you might have overlooked. After writing a proof, read it from start to finish and ask: does each step genuinely follow from what came before?

Direct Proofs vs. Other Proof Types

Direct vs. indirect proofs: Direct proofs show the conclusion follows straight from the hypothesis. Indirect proofs (contradiction, contrapositive) work by assuming something false and showing it can't hold. Both can prove the same theorem, but one approach is often cleaner than the other depending on the problem.

Deductive vs. inductive reasoning: Direct proofs use deductive reasoning, moving from general principles to specific conclusions. Inductive reasoning goes the other direction, generalizing from specific cases to form conjectures. Mathematical induction is a separate proof technique that proves statements for all natural numbers by establishing a base case and an inductive step.

Building Your Proof Skills

• Start simple. Work through basic proofs in number theory or algebra before tackling complex ones. Prove that the product of two odd numbers is odd, or that the sum of three consecutive integers is divisible by 3.
• Study existing proofs. Read well-written proofs and pay attention to their structure. Try to reconstruct them from memory afterward.
• Compare approaches. Look at multiple proofs of the same theorem to see how different strategies work.
• Get feedback. Share your proofs with classmates or instructors. Having someone else read your argument reveals gaps you might have missed.
• Build intuition. The more proofs you write, the better you'll get at recognizing which strategy fits a given problem. There's no shortcut here; it takes practice.