Direct Proof

A direct proof turns the assumptions of a statement into the conclusion through definitions and justified deductions. The challenge is usually deciding what to unpack and what form the conclusion requires. This chapter develops that habit before case analysis, indirect proof, and induction.

Turn the statement into a proof task

To prove that every object satisfying $P$ also satisfies $Q$, choose an arbitrary object in the stated domain, assume $P$, and derive $Q$. “Arbitrary” means that the proof may use the domain and hypotheses, but no special feature of a chosen numerical example. The result then applies to every allowed object.

A useful working order is to identify the domain, expand the hypotheses, inspect the definition of the target, and connect the two. MIT’s introductory proof notes give a companion account of deductions from stated assumptions [1][1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf.

Target	What a completed proof must supply
$n$ is even	An integer $m$ with $n=2m$
$n$ is odd	An integer $m$ with $n=2m+1$
$d\mid n$	An integer $m$ with $n=dm$
$x\in\mathbb Q$	Integers $a,b$, with $b\ne0$, such that $x=a/b$
$x\le y$	A justified comparison, for example $y-x\ge0$

For an existential statement, constructing a candidate is only half the job: check that it belongs to the required domain and satisfies the property. For an “if and only if” statement, prove both directions; a chain establishing one implication does not automatically establish the reverse.

Worked example: expose the required form

PropositionThe square of an odd integer is odd

If $n$ is an odd integer, then $n^2$ is odd.

The hypothesis gives a representation of $n$. The target asks for a representation of $n^2$ as twice an integer plus one. That suggests expanding the square and collecting its even part.

Proof

Let $n$ be an arbitrary odd integer. There is an integer $k$ such that $n=2k+1$. Then

$$\begin{aligned} n^2&=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned}$$

The quantity $2k^2+2k$ is an integer, so this is the defining form of an odd integer. Therefore $n^2$ is odd.

The final sentence is essential: it explains why the algebra proves the target. There is no need to assume $k$ positive. Negative odd integers and $n=1$ are covered by the same calculation.

Different objects need independent witnesses

PropositionA sum of rational numbers is rational

If $x,y\in\mathbb Q$, then $x+y\in\mathbb Q$.

Proof

Write $x=a/b$ and $y=c/d$, where $a,b,c,d$ are integers and $b,d\ne0$. Then

$$x+y=\frac{ad+bc}{bd}.$$

The numerator and denominator are integers, and $bd\ne0$. Hence the sum is rational by definition.

We did not give $x$ and $y$ the same numerator or denominator without justification. Similarly, two even integers should initially be written as $2k$ and $2m$, not both as $2k$. Reusing a witness can accidentally restrict a claim about two arbitrary objects to a claim about two equal ones.

Working backward helps discovery, not justification

When planning a proof, it is reasonable to start from the desired form and ask what would suffice. The written proof must then establish those sufficient conditions from the actual hypotheses. Beginning with the desired equality as if it were already known creates a circular argument unless every step is explicitly reversible and the endpoint is independently established.

ExampleAn inequality with a useful difference

For real $a,b$, prove $a^2+b^2\ge2ab$. Subtracting the right side suggests the square

$$a^2+b^2-2ab=(a-b)^2.$$

For the proof, start with the known fact $(a-b)^2\ge0$, expand, and rearrange. Equality holds exactly when $a=b$. The square explains both the inequality and its equality condition.

Also check that each operation is legal. Dividing by $a-b$ requires $a\ne b$; multiplying an inequality by an expression of unknown sign may reverse its direction; squaring a real equation can introduce extra candidates when solving it. The proof must account for those conditions rather than hide them inside algebra.

Exercises

Try to write the representation you need before opening the solution. The first three practise definitions and divisibility; later exercises extend the same habit to constructing witnesses and proving equivalences.

ExerciseAn even square

Prove that the square of an even integer is even.

Show solution

Solution

Let $n=2k$ with $k\in\mathbb Z$. Then $n^2=4k^2=2(2k^2)$. Since $2k^2$ is an integer, $n^2$ is even. Writing the factor $2$ is not enough by itself; identifying the remaining factor as an integer completes the argument.

ExerciseA sum of two even integers

Prove that the sum of any two even integers is even. Explain why assigning both integers the same witness would be insufficient.

Show solution

Solution

Write $a=2k$ and $b=2m$ for independently chosen integers $k,m$. Then $a+b=2(k+m)$, with integer $k+m$. Using $a=2k$ and $b=2k$ would prove only the restricted case $a=b$.

ExerciseA divisibility argument with a stated supporting fact

Prove that $3\mid n^3+2n$ for every integer $n$. You may use the fact that among three consecutive integers one is divisible by $3$; the next chapter justifies it using remainders.

Show solution

Solution

Rewrite the expression as

$$n^3+2n=(n-1)n(n+1)+3n.$$

One factor in the first product is divisible by $3$, so that product is $3m$ for some integer $m$. The entire expression is therefore $3(m+n)$. The witness $m$ need not be positive: for $n=1$ the product is $0$. The proof also covers zero and negative integers.

ExerciseConstruct a witness

Given rational numbers $a<b$, construct a rational number strictly between them and prove all required properties.

Show solution

Solution

Take $c=(a+b)/2$. Closure of rational numbers under addition and multiplication makes $c$ rational. Furthermore,

$$c-a=\frac{b-a}{2}>0, \qquad b-c=\frac{b-a}{2}>0.$$

Thus $a<c<b$. Checking rationality and both strict inequalities is what turns the candidate into an existence proof.

ExerciseProve both directions

For integers $n$, prove that $n$ is odd if and only if $n+1$ is even.

Show solution

Solution

If $n=2k+1$ with $k\in\mathbb Z$, then $n+1=2(k+1)$ is even. Conversely, if $n+1=2m$ with $m\in\mathbb Z$, then $n=2m-1=2(m-1)+1$ is odd. Both directions have now been established, using the relevant hypothesis in each.

When to change methods

Try direct proof when the hypotheses give an explicit form or a familiar inequality. If a definition changes with parity, sign, or remainder, Proof by Cases can expose the appropriate form in each branch. If the negation of the conclusion gives more useful information, consider Indirect Proof. Choosing a method is a way to organize the reasoning, not a replacement for checking each step.

References

1. [1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf ↩