The Central Idea
Many mathematical statements have the logical form
\[ P\Longrightarrow Q. \]A direct proof assumes that \(P\) is true and then uses valid reasoning to show that \(Q\) must also be true.
The basic structure is
\[ \boxed{\text{Assume }P\;\longrightarrow\;\text{derive consequences}\;\longrightarrow\;\text{establish }Q.} \]The word direct refers to the logical route: we move from the hypothesis toward the conclusion without replacing the statement by its contrapositive and without assuming the conclusion is false.
What a Proof Must Do
A proof must establish that a conclusion follows for every case covered by the hypotheses.
Suppose the claim is
\[ \text{If }n\text{ is even, then }n^2\text{ is even.} \]Checking
\[ 2^2=4,\qquad 4^2=16,\qquad 10^2=100 \]gives supporting examples, but it does not prove the claim for every even integer.
A proof needs a general argument that works for an arbitrary even integer.
Hypothesis and Conclusion
In a conditional statement
\[ P\Longrightarrow Q, \]\(P\) is the hypothesis and \(Q\) is the conclusion.
For example,
\[ \text{If }n\text{ is divisible by }6,\text{ then }n\text{ is divisible by }3, \]the hypothesis is
\[ n\text{ is divisible by }6, \]and the conclusion is
\[ n\text{ is divisible by }3. \]A direct proof begins by assuming the hypothesis.
Start with an Arbitrary Object
Universal statements often concern every object of some type.
A proof therefore begins with an arbitrary object satisfying the stated conditions.
For a claim about all even integers, we might write:
Let \(n\) be an arbitrary even integer.
Because \(n\) was chosen arbitrarily, an argument that depends only on evenness applies to every even integer, not merely to one example.
Definitions Turn Words into Mathematical Structure
Many direct proofs become possible as soon as a definition is written in a usable mathematical form.
For an integer \(n\),
\[ n\text{ is even}\quad\Longleftrightarrow\quad n=2k \]for some integer \(k\).
Similarly,
\[ n\text{ is odd}\quad\Longleftrightarrow\quad n=2k+1 \]for some integer \(k\), and
\[ a\mid b\quad\Longleftrightarrow\quad b=ak \]for some integer \(k\).
These definitions convert verbal properties into equations that can be manipulated.
Example: The Square of an Even Integer Is Even
Prove:
\[ \text{If }n\text{ is even, then }n^2\text{ is even.} \]Let \(n\) be an arbitrary even integer.
By the definition of evenness, there is an integer \(k\) such that
\[ n=2k. \]Squaring gives
\[ n^2=(2k)^2=4k^2=2(2k^2). \]Since \(k\) is an integer, \(2k^2\) is an integer.
Therefore \(n^2\) is twice an integer, so \(n^2\) is even.
\[ \boxed{n\text{ even}\Longrightarrow n^2\text{ even}.} \]Why the Previous Proof Works
The proof follows a short chain of justified steps:
- Begin with an arbitrary even integer \(n\).
- Use the definition of evenness to write \(n=2k\).
- Substitute into the expression \(n^2\).
- Rewrite the result as \(2\) times an integer.
- Apply the definition of evenness again.
The conclusion is not based on a pattern observed in examples. It follows from the defining structure of every even integer.
Existence Variables Must Stay in Their Domain
When a definition says that there exists an integer \(k\), the fact that \(k\) is an integer matters.
In the previous proof,
\[ n^2=2(2k^2). \]To conclude that \(n^2\) is even, the quantity \(2k^2\) must be an integer. It is an integer because the integers are closed under multiplication.
Good proofs keep track of these domain facts rather than silently assuming them.
Example: The Sum of Two Even Integers Is Even
Let \(a\) and \(b\) be even integers.
Then there exist integers \(r\) and \(s\) such that
\[ a=2r,\qquad b=2s. \]Add:
\[ a+b=2r+2s=2(r+s). \]Since \(r+s\) is an integer, \(a+b\) is twice an integer.
Therefore,
\[ \boxed{\text{the sum of two even integers is even}.} \]Use Different Variables for Different Existential Quantities
If \(a\) and \(b\) are both even, it is generally unsafe to write
\[ a=2k,\qquad b=2k. \]That would force \(a=b\), which was not given.
Instead write
\[ a=2r,\qquad b=2s \]for possibly different integers \(r\) and \(s\).
Variable choice is part of precise reasoning.
Example: The Sum of Two Odd Integers Is Even
Let \(a\) and \(b\) be odd integers.
Then
\[ a=2r+1,\qquad b=2s+1 \]for some integers \(r\) and \(s\).
Therefore,
\[ a+b=(2r+1)+(2s+1). \]Simplify:
\[ a+b=2r+2s+2=2(r+s+1). \]Since \(r+s+1\) is an integer,
\[ \boxed{a+b\text{ is even}.} \]Example: The Product of Two Odd Integers Is Odd
Let
\[ a=2r+1,\qquad b=2s+1, \]where \(r,s\in\mathbb Z\).
Multiply:
\[ ab=(2r+1)(2s+1). \]Expanding gives
\[ ab=4rs+2r+2s+1. \]Factor \(2\) from the first three terms:
\[ ab=2(2rs+r+s)+1. \]The quantity \(2rs+r+s\) is an integer, so \(ab\) has the form \(2k+1\).
Therefore,
\[ \boxed{ab\text{ is odd}.} \]Direct Proof with Divisibility
Divisibility statements are especially well suited to direct proof because the definition
\[ a\mid b\quad\Longleftrightarrow\quad b=ak \]immediately produces an equation.
The usual strategy is:
- translate each divisibility hypothesis into an equation;
- combine or rearrange those equations;
- factor out the divisor required by the conclusion.
Example: Divisibility Is Transitive
Prove:
\[ a\mid b\text{ and }b\mid c\Longrightarrow a\mid c. \]Assume \(a\mid b\) and \(b\mid c\).
By the definition of divisibility, there are integers \(r\) and \(s\) such that
\[ b=ar \]and
\[ c=bs. \]Substitute \(b=ar\) into \(c=bs\):
\[ c=(ar)s=a(rs). \]Since \(rs\in\mathbb Z\), the definition of divisibility gives
\[ \boxed{a\mid c}. \]Example: A Common Divisor Divides a Linear Combination
Suppose \(d\mid a\) and \(d\mid b\). Prove that
\[ d\mid (ma+nb) \]for all integers \(m\) and \(n\).
Since \(d\mid a\) and \(d\mid b\), there are integers \(r\) and \(s\) such that
\[ a=dr,\qquad b=ds. \]Then
\[ ma+nb=m(dr)+n(ds). \]Factor out \(d\):
\[ ma+nb=d(mr+ns). \]Because \(mr+ns\) is an integer,
\[ \boxed{d\mid(ma+nb)}. \]Direct Proof with Set Inclusion
A statement such as
\[ A\subseteq B \]means that every element of \(A\) is also an element of \(B\).
A direct proof of set inclusion therefore starts with an arbitrary element of the first set:
- let \(x\in A\);
- use the definition of \(A\) and other known facts;
- show that \(x\in B\);
- conclude \(A\subseteq B\).
Example: Intersection Is Contained in Each Set
Prove
\[ A\cap B\subseteq A. \]Let \(x\in A\cap B\).
By the definition of intersection,
\[ x\in A\quad\text{and}\quad x\in B. \]In particular,
\[ x\in A. \]Since every arbitrary element of \(A\cap B\) is in \(A\),
\[ \boxed{A\cap B\subseteq A}. \]Example: A Subset Relation through a Shared Property
Define
\[ A=\{n\in\mathbb Z:12\mid n\} \]and
\[ B=\{n\in\mathbb Z:3\mid n\}. \]We will prove \(A\subseteq B\).
Let \(n\in A\). Then \(12\mid n\), so
\[ n=12k \]for some integer \(k\).
Rewrite:
\[ n=3(4k). \]Since \(4k\) is an integer, \(3\mid n\). Therefore \(n\in B\).
Hence
\[ \boxed{A\subseteq B}. \]Direct Proof with Inequalities
Direct proofs also appear in order and inequality arguments.
Suppose \(a
Example: Squares Preserve Order for Positive Numbers
Suppose
\[ 0Chaining Implications
A direct proof often consists of several smaller implications.
If we know
\[ P\Longrightarrow R, \]and
\[ R\Longrightarrow S, \]and
\[ S\Longrightarrow Q, \]then the chain establishes
\[ \boxed{P\Longrightarrow Q}. \]Each intermediate statement serves as a bridge between the hypothesis and the conclusion.
Known Results Can Be Used as Steps
A proof does not need to re-prove every theorem from the foundations each time it is used.
Once a result has been established, it can become a justified step in a later proof.
A proof may therefore use:
- definitions;
- axioms and accepted properties;
- previously proved theorems;
- algebraic identities;
- valid rules of inference.
The important requirement is that each step has a legitimate basis.
Proof Is More Than Algebra
Algebra often appears inside a proof, but algebraic manipulation alone is not the proof.
For example,
\[ (2k+1)+(2r+1)=2(k+r+1) \]is an algebraic calculation.
The proof is completed only when we explain why the final form matters: \(k+r+1\) is an integer, so the result is twice an integer and is therefore even.
A complete proof connects calculations back to definitions and logical claims.
Necessary Information Should Be Stated
Compare the following two endings.
Incomplete:
\[ n^2=2(2k^2). \]Complete:
Since \(k\in\mathbb Z\), we have \(2k^2\in\mathbb Z\). Thus \(n^2\) is twice an integer, so \(n^2\) is even.
The second version makes the logical bridge explicit.
A Standard Direct-Proof Pattern
For many elementary statements of the form \(P\Rightarrow Q\), the following framework is reliable:
- State an arbitrary object satisfying the hypothesis.
- Assume the hypothesis \(P\).
- Unpack the relevant definitions.
- Introduce variables required by those definitions.
- Apply valid algebraic or logical steps.
- Reach a form matching the definition or condition in \(Q\).
- State explicitly why the conclusion follows.
Example: A Multiple of 12 Is a Multiple of 4
Prove:
\[ 12\mid n\Longrightarrow 4\mid n. \]Assume \(12\mid n\).
Then
\[ n=12k \]for some integer \(k\).
Rewrite \(12k\) as
\[ n=4(3k). \]Since \(3k\in\mathbb Z\),
\[ \boxed{4\mid n}. \]Example: The Product of an Even Integer and Any Integer Is Even
Let \(a\) be even and let \(b\) be any integer.
Since \(a\) is even,
\[ a=2k \]for some integer \(k\).
Then
\[ ab=(2k)b=2(kb). \]Because \(k,b\in\mathbb Z\), we have \(kb\in\mathbb Z\).
Therefore,
\[ \boxed{ab\text{ is even}.} \]Example: The Difference of Two Odd Integers Is Even
Let \(a\) and \(b\) be odd integers.
Then
\[ a=2r+1,\qquad b=2s+1 \]for integers \(r\) and \(s\).
Subtract:
\[ a-b=(2r+1)-(2s+1). \]Simplify:
\[ a-b=2r-2s=2(r-s). \]Since \(r-s\in\mathbb Z\),
\[ \boxed{a-b\text{ is even}.} \]Example: Divisibility of a Sum
Suppose \(5\mid a\) and \(5\mid b\). Prove \(5\mid(a+b)\).
By divisibility,
\[ a=5r,\qquad b=5s \]for integers \(r\) and \(s\).
Thus
\[ a+b=5r+5s=5(r+s). \]Since \(r+s\) is an integer,
\[ \boxed{5\mid(a+b)}. \]Proving an Equality Directly
Sometimes the conclusion is an identity or equality.
A common method is to begin with one side and use valid transformations until the other side is obtained.
For example, for all real \(x\),
\[ (x+1)^2-(x-1)^2=4x. \]Starting from the left:
\[ (x+1)^2-(x-1)^2 \] \[ =x^2+2x+1-(x^2-2x+1) \] \[ =4x. \]Therefore the identity holds.
Do Not Assume What You Are Trying to Prove
A proof becomes circular if it uses the desired conclusion as though it were already known.
To prove
\[ P\Longrightarrow Q, \]a direct proof may assume \(P\), but it may not simply assume \(Q\).
Every use of \(Q\) must come only after \(Q\) has been derived from known information.
Common Error: Proving with Examples
Suppose the claim is that the sum of two odd integers is even.
The calculations
\[ 3+5=8,\qquad 7+11=18,\qquad 101+9=110 \]are examples.
They do not prove the universal statement because infinitely many pairs remain unchecked.
Examples can suggest a theorem. A proof must explain why the theorem holds in every permitted case.
Common Error: Starting with a Special Case
If the claim concerns every integer \(n\), choosing \(n=8\) proves only something about \(8\).
A direct proof should usually begin with language such as
“Let \(n\) be an arbitrary integer satisfying the hypothesis.”
The arbitrariness is what allows the final conclusion to apply generally.
Common Error: Reversing an Implication
From
\[ P\Longrightarrow Q \]we may not automatically infer
\[ Q\Longrightarrow P. \]For example,
\[ 4\mid n\Longrightarrow 2\mid n \]is true, but the reverse is false. The integer \(6\) is divisible by \(2\) but not by \(4\).
A direct proof must follow implications in a valid direction.
Common Error: Using a Definition Only Halfway
Suppose a calculation ends with
\[ n^2=4k^2. \]If the goal is to prove that \(n^2\) is even, the most useful form is
\[ n^2=2(2k^2). \]This explicitly matches the definition of an even integer.
Shape the final expression so that the conclusion becomes immediate.
Common Error: Failing to Justify Integrality
To prove that an integer expression is even, obtaining the form
\[ 2(\text{something}) \]is not quite enough unless the “something” is known to be an integer.
If \(r,s\in\mathbb Z\), then
\[ r+s,\qquad rs,\qquad r-s \]are integers because the integers are closed under addition, multiplication, and subtraction.
Common Error: Introducing Unnecessary Assumptions
Suppose a theorem assumes only that \(n\) is even.
A proof should not additionally assume that \(n\) is positive unless positivity is actually given or derived.
Extra assumptions can accidentally prove only a narrower statement than the theorem claims.
Use exactly the hypotheses available.
Common Error: Writing a Calculation without a Logical Conclusion
A line such as
\[ a+b=2(r+s+1) \]does not explain itself.
Finish the argument:
Since \(r+s+1\in\mathbb Z\), the sum \(a+b\) is twice an integer. Therefore \(a+b\) is even.
Proof writing joins symbolic work with explanatory language.
How Much Detail Is Enough?
A proof should contain enough detail that a reader can verify every important inference.
Routine algebra may be compressed when the audience is prepared for it, but the key logical transitions should remain visible.
In an introductory proof course, it is usually better to state:
- which definition is being used;
- where a new variable comes from;
- why a constructed quantity belongs to the required domain;
- why the final expression establishes the conclusion.
A Direct Proof as a Dependency Chain
It can help to view a proof as a dependency structure.
The conclusion should depend on earlier statements:
\[ \text{hypothesis} \Longrightarrow \text{definition} \Longrightarrow \text{derived relation} \Longrightarrow \text{target form} \Longrightarrow \text{conclusion}. \]No step should appear without support, and no essential assumption should disappear unnoticed.
Direct Proof and Mathematical Communication
A proof serves two functions at once:
- it establishes that a mathematical statement is true;
- it explains why the statement is true.
Clear organization therefore matters. A correct argument becomes easier to inspect when assumptions, definitions, substitutions, and conclusions are stated in a deliberate order.
A Reliable Procedure for Direct Proof
- Identify the hypothesis and the conclusion.
- Choose an arbitrary object satisfying the hypothesis.
- Write down the hypothesis explicitly.
- Expand important definitions into usable mathematical forms.
- Introduce any required integers, elements, or parameters.
- Apply algebra, known theorems, and valid implications.
- Keep track of domains and conditions.
- Rearrange the result into a form that matches the conclusion.
- State explicitly why that form proves the conclusion.
- Check that no special case or extra assumption was introduced.
Example: Full Direct-Proof Workflow
Prove that if \(a\) and \(b\) are odd integers, then \(a+b+2\) is even.
Step 1: Introduce arbitrary objects.
Let \(a\) and \(b\) be arbitrary odd integers.
Step 2: Apply the definition of oddness.
\[ a=2r+1,\qquad b=2s+1 \]for some \(r,s\in\mathbb Z\).
Step 3: Substitute.
\[ a+b+2=(2r+1)+(2s+1)+2. \]Step 4: Simplify into the target form.
\[ a+b+2=2r+2s+4=2(r+s+2). \]Step 5: Verify the required domain.
Since \(r,s\in\mathbb Z\), the quantity \(r+s+2\) is an integer.
Step 6: Conclude.
\[ \boxed{a+b+2\text{ is even}.} \]Practice 1: Even Plus Even
Prove directly that if \(a\) and \(b\) are even integers, then \(a+b\) is even.
Practice 2: Odd Plus Odd
Prove directly that if \(a\) and \(b\) are odd integers, then \(a+b\) is even.
Practice 3: Even Times Integer
Prove directly that if \(a\) is even and \(b\) is an integer, then \(ab\) is even.
Practice 4: Divisibility
Prove directly:
\[ 15\mid n\Longrightarrow 5\mid n. \]Practice 5: Divisibility of a Difference
Suppose \(7\mid a\) and \(7\mid b\). Prove directly that
\[ 7\mid(a-b). \]Practice 6: Set Inclusion
Prove directly that
\[ A\cap B\subseteq B. \]Practice 7: Union Containment
Prove directly that
\[ A\subseteq A\cup B. \]Practice 8: Odd Difference
Prove directly that the difference of two odd integers is even.
Practice 9: Linear Combination
Suppose \(d\mid a\) and \(d\mid b\). Prove directly that
\[ d\mid(3a-2b). \]Practice 10: Identify the Error
A student tries to prove that the product of two odd integers is odd and writes
\[ a=2k+1,\qquad b=2k+1. \]Explain why this setup is too restrictive and correct it.
Practice Answers
Practice 1
Write
\[ a=2r,\qquad b=2s \]for integers \(r,s\). Then
\[ a+b=2r+2s=2(r+s). \]Since \(r+s\in\mathbb Z\), \(a+b\) is even.
Practice 2
Write
\[ a=2r+1,\qquad b=2s+1. \]Then
\[ a+b=2(r+s+1). \]Since \(r+s+1\in\mathbb Z\), \(a+b\) is even.
Practice 3
Since \(a\) is even,
\[ a=2k \]for some integer \(k\). Therefore
\[ ab=2(kb). \]Because \(kb\in\mathbb Z\), \(ab\) is even.
Practice 4
If \(15\mid n\), then
\[ n=15k=5(3k) \]for some \(k\in\mathbb Z\). Since \(3k\in\mathbb Z\),
\[ \boxed{5\mid n}. \]Practice 5
Write
\[ a=7r,\qquad b=7s. \]Then
\[ a-b=7r-7s=7(r-s). \]Since \(r-s\in\mathbb Z\),
\[ \boxed{7\mid(a-b)}. \]Practice 6
Let \(x\in A\cap B\). By definition of intersection, \(x\in A\) and \(x\in B\). Therefore \(x\in B\). Since \(x\) was arbitrary,
\[ \boxed{A\cap B\subseteq B}. \]Practice 7
Let \(x\in A\). By the definition of union, an element belonging to \(A\) belongs to \(A\cup B\). Therefore \(x\in A\cup B\), so
\[ \boxed{A\subseteq A\cup B}. \]Practice 8
Write
\[ a=2r+1,\qquad b=2s+1. \]Then
\[ a-b=2(r-s). \]Since \(r-s\in\mathbb Z\), \(a-b\) is even.
Practice 9
Since \(d\mid a\) and \(d\mid b\), write
\[ a=dr,\qquad b=ds. \]Then
\[ 3a-2b=3dr-2ds=d(3r-2s). \]Since \(3r-2s\in\mathbb Z\),
\[ \boxed{d\mid(3a-2b)}. \]Practice 10
Using the same \(k\) for both odd integers forces \(a=b\). The hypotheses do not require the two integers to be equal.
Use separate integer parameters:
\[ a=2r+1,\qquad b=2s+1. \]Then
\[ ab=(2r+1)(2s+1)=2(2rs+r+s)+1, \]which proves that \(ab\) is odd.
What to Remember
A direct proof follows the logical direction of the statement:
\[ \boxed{P\Longrightarrow Q.} \]- begin with an arbitrary object satisfying the hypothesis;
- use definitions to expose mathematical structure;
- justify each algebraic and logical step;
- track domains such as integer membership;
- shape the final result so that it matches the desired conclusion;
- do not replace a universal proof with a collection of examples;
- do not assume the conclusion or reverse an implication without justification.
The central habit is to ask: What does the hypothesis give me, and how can I transform that information into exactly what the conclusion requires?
Where We Go Next
Direct proof is often the simplest route from a hypothesis to a conclusion, but some statements are difficult to attack in that direction.
The next lesson, Proof by Contrapositive, uses the logically equivalent statement
\[ P\Longrightarrow Q \qquad\Longleftrightarrow\qquad \neg Q\Longrightarrow\neg P \]to prove a conditional claim from the opposite direction.