1.1.1 Structure of mathematical proof

What you'll learn

How a mathematical proof is structured from assumptions to conclusion.
How to use proof by deduction to build a logical chain.
How to use proof by exhaustion when there are finitely many possible cases.
How to distinguish a proof from evidence based only on examples.

What is a mathematical proof?

A mathematical statement is a sentence that is either true or false. For example, “the sum of two odd integers is even” is a mathematical statement.

A proof is a logically complete argument showing that a statement must be true in every case covered by the statement. Each step must follow from information already given, an accepted definition, a known result or valid algebra.

Definition

Mathematical proof

A mathematical proof is a sequence of justified statements that begins with accepted assumptions and reaches a required conclusion by valid logical reasoning.

Testing several values can provide useful evidence and may help you discover a pattern. However, evidence is not generally a proof because untested cases could behave differently.

For example, calculating that

12+1=2,22+2=6,32+3=121^2+1=2,\qquad 2^2+2=6,\qquad 3^2+3=12

suggests that $n^2+n$ is even for positive integers $n$ . A proof must explain why this is true for every integer, not just the integers tested.

Common Mistake

Examples are not a universal proof

Checking many numerical examples does not prove a statement about all integers. A universal claim requires a general argument that covers every permitted value.

The basic structure of a proof

Most proofs contain four connected parts.

1. The claim

The claim is the statement to be proved. You should identify exactly what it says and which values it covers.

Words such as all, every and any indicate a universal statement: a claim intended to hold throughout a specified set.

2. The assumptions

An assumption is information you are allowed to take as true at the start of the argument. This includes the conditions in the question and any definitions you use.

For example, if $n$ is an even integer, the definition of even allows you to write

n = 2 k

for some integer $k$ .

The phrase “for some integer $k$ ” matters. It ensures that the algebraic form matches the definition of an even integer.

3. The logical argument

The argument is a chain of statements in which each step follows from the preceding information. Reasons may include:

a definition;
algebraic manipulation;
a known mathematical result;
consideration of all possible cases;
a consequence of an earlier step.

4. The conclusion

The final line should connect your result explicitly to the original claim. If you obtain an expression of the form $2 m$ , you should state that it is even because $m$ is an integer.

Key Idea

A complete logical chain

A proof starts from the conditions given, uses only justified steps and ends by explicitly confirming the required conclusion.

Implication and equivalence

The notation

P⇒QP\Rightarrow Q

means “if $P$ is true, then $Q$ is true”. This is called an implication. Here, $P$ is the hypothesis and $Q$ is the conclusion.

An implication does not automatically work backwards. From $P⇒QP\Rightarrow Q$ , you cannot assume that $Q⇒PQ\Rightarrow P$ .

The notation

P⇔QP\Leftrightarrow Q

means that both $P⇒QP\Rightarrow Q$ and $Q⇒PQ\Rightarrow P$ are true. The statements are then equivalent, meaning that each one is true exactly when the other is true.

Example

Distinguishing implication from equivalence

Consider the statements:

$P$ : “ $n$ is divisible by 4.”
$Q$ : “ $n$ is even.”

If $n$ is divisible by 4, then $n = 4 k$ for some integer $k$ .
Rewrite this as $n = 2 (2 k)$ . Since $2 k$ is an integer, $n$ is even. Therefore $P⇒QP\Rightarrow Q$ .
The reverse implication is false: $n = 6$ is even but is not divisible by 4.
Therefore the two statements are not equivalent.

Proof by deduction

Proof by deduction begins with known facts or assumptions and uses valid logical steps to reach the required result. It is often called a direct proof because you move directly from the hypothesis to the conclusion.

Algebraic definitions are particularly useful:

If $n$ is even, then $n = 2 k$ for some integer $k$ .
If $n$ is odd, then $n = 2 k + 1$ for some integer $k$ .
If $n$ is divisible by $d$ , then $n = d k$ for some integer $k$ .

Example

Proving that the sum of two odd integers is even

Prove that the sum of any two odd integers is even.

Let the two odd integers be $2 a + 1$ and $2 b + 1$ , where $a$ and $b$ are integers. Using different letters allows the two odd integers to have different values.
Add and simplify:
$(2a+1)+(2b+1)=2a+2b+2=2(a+b+1).\begin{aligned} (2a+1)+(2b+1) &=2a+2b+2\\ &=2(a+b+1). \end{aligned}$
Since $a$ and $b$ are integers, $a + b + 1$ is also an integer.
The sum therefore has the form two multiplied by an integer, so it is even. Hence the sum of any two odd integers is even.

Common Mistake

Using one variable for two arbitrary integers

Writing both odd integers as $2 k + 1$ assumes that they are equal. Use separate integer variables, such as $2 a + 1$ and $2 b + 1$ , unless equality is given.

Choosing useful algebraic forms

A good proof often depends on translating the conditions into forms that expose the required structure.

Example

Proving divisibility of a product

Prove that the product of two consecutive integers is even.

Let the consecutive integers be $n$ and $n + 1$ , where $n$ is an integer.
Every integer is either even or odd. If $n$ is even, then the product $n (n + 1)$ contains the even factor $n$ , so the product is even.
If $n$ is odd, then $n + 1$ is even, so the product contains the even factor $n + 1$ and is again even.
These two possibilities cover every integer $n$ . Therefore $n (n + 1)$ is always even.

This argument uses deduction together with a split into cases. The split is valid because every integer is either even or odd.

Proof by exhaustion

Proof by exhaustion establishes a statement by dividing the problem into a finite number of possible cases and proving the result in every case.

Definition

Proof by exhaustion

A proof by exhaustion lists or classifies all possible cases, checks each one using valid reasoning and concludes that the claim is true because no cases remain.

This method is useful when:

a variable can take only finitely many stated values;
objects can be divided into a finite set of categories;
possible remainders after division give a finite number of cases.

When an integer is divided by 3, for example, its remainder must be 0, 1 or 2. Therefore every integer has exactly one of the forms

n=3k,n=3k+1,n=3k+2n=3k,\qquad n=3k+1,\qquad n=3k+2

for some integer $k$ .

Example

Classifying square numbers modulo 3

Prove that the square of any integer has remainder 0 or 1 when divided by 3.

Every integer $n$ has one of the forms $3 k$ , $3 k + 1$ or $3 k + 2$ , where $k$ is an integer.
If $n = 3 k$ , then
$n^2=9k^2=3(3k^2),$
so the remainder is 0.
If $n = 3 k + 1$ , then
$n^2=9k^2+6k+1=3(3k^2+2k)+1,$
so the remainder is 1.
If $n = 3 k + 2$ , then
$n^2=9k^2+12k+4=3(3k^2+4k+1)+1,$
so the remainder is again 1.
The three cases include every integer. Therefore an integer square has remainder 0 or 1 when divided by 3.

Tip

Check that the cases are exhaustive

Before checking individual cases, state why your list covers every possibility. For remainder arguments, the possible remainders after division by $d$ are 0, 1, up to $d - 1$ .

Common Mistake

Large or infinite collections

Proof by exhaustion requires a genuinely finite and complete collection of cases. Checking the first hundred integers does not exhaust all integers.

Presenting a rigorous proof

A clear proof should let another mathematician verify every link in the argument. Use complete sentences around your algebra and define all variables.

You should normally:

begin with an arbitrary object satisfying the conditions;
translate definitions into algebraic forms;
justify why newly formed quantities are integers where necessary;
cover every case if you split the argument;
finish with a sentence matching the original claim.

The word arbitrary means that your chosen object has no special property beyond those stated. Proving the result for an arbitrary integer therefore proves it for every integer satisfying the conditions.

Exam technique

In the exam

Identify the exact hypothesis and conclusion before beginning the algebra.
Define variables precisely, including statements such as “where $k$ is an integer”.
For deduction, ensure that every line follows logically from the previous information.
For exhaustion, state all possible cases and explain why the list is complete.
End by interpreting your final expression and explicitly stating the required conclusion.

Self review

Check yourself

Why does checking several numerical examples usually fail to prove a universal statement?
How would you represent two different even integers algebraically?
What cases would you need to consider when classifying an integer by its remainder after division by 4?

What you'll learn

How a mathematical proof is structured from assumptions to conclusion.
How to use proof by deduction to build a logical chain.
How to use proof by exhaustion when there are finitely many possible cases.
How to distinguish a proof from evidence based only on examples.

What is a mathematical proof?

A mathematical statement is a sentence that is either true or false. For example, “the sum of two odd integers is even” is a mathematical statement.

Definition

Mathematical proof

A mathematical proof is a sequence of justified statements that begins with accepted assumptions and reaches a required conclusion by valid logical reasoning.

Testing several values can provide useful evidence and may help you discover a pattern. However, evidence is not generally a proof because untested cases could behave differently.

For example, calculating that

12+1=2,22+2=6,32+3=121^2+1=2,\qquad 2^2+2=6,\qquad 3^2+3=12

suggests that $n^2+n$ is even for positive integers $n$ . A proof must explain why this is true for every integer, not just the integers tested.

Common Mistake

Examples are not a universal proof

Checking many numerical examples does not prove a statement about all integers. A universal claim requires a general argument that covers every permitted value.

The basic structure of a proof

Most proofs contain four connected parts.

1. The claim

The claim is the statement to be proved. You should identify exactly what it says and which values it covers.

Words such as all, every and any indicate a universal statement: a claim intended to hold throughout a specified set.

2. The assumptions

An assumption is information you are allowed to take as true at the start of the argument. This includes the conditions in the question and any definitions you use.

For example, if $n$ is an even integer, the definition of even allows you to write

n = 2 k

for some integer $k$ .

The phrase “for some integer $k$ ” matters. It ensures that the algebraic form matches the definition of an even integer.

3. The logical argument

The argument is a chain of statements in which each step follows from the preceding information. Reasons may include:

a definition;
algebraic manipulation;
a known mathematical result;
consideration of all possible cases;
a consequence of an earlier step.

4. The conclusion

The final line should connect your result explicitly to the original claim. If you obtain an expression of the form $2 m$ , you should state that it is even because $m$ is an integer.

Key Idea

A complete logical chain

A proof starts from the conditions given, uses only justified steps and ends by explicitly confirming the required conclusion.

Implication and equivalence

The notation

P⇒QP\Rightarrow Q

means “if $P$ is true, then $Q$ is true”. This is called an implication. Here, $P$ is the hypothesis and $Q$ is the conclusion.

An implication does not automatically work backwards. From $P⇒QP\Rightarrow Q$ , you cannot assume that $Q⇒PQ\Rightarrow P$ .

The notation

P⇔QP\Leftrightarrow Q

means that both $P⇒QP\Rightarrow Q$ and $Q⇒PQ\Rightarrow P$ are true. The statements are then equivalent, meaning that each one is true exactly when the other is true.

Example

Distinguishing implication from equivalence

Consider the statements:

$P$ : “ $n$ is divisible by 4.”
$Q$ : “ $n$ is even.”

If $n$ is divisible by 4, then $n = 4 k$ for some integer $k$ .
Rewrite this as $n = 2 (2 k)$ . Since $2 k$ is an integer, $n$ is even. Therefore $P⇒QP\Rightarrow Q$ .
The reverse implication is false: $n = 6$ is even but is not divisible by 4.
Therefore the two statements are not equivalent.

Proof by deduction

Algebraic definitions are particularly useful:

If $n$ is even, then $n = 2 k$ for some integer $k$ .
If $n$ is odd, then $n = 2 k + 1$ for some integer $k$ .
If $n$ is divisible by $d$ , then $n = d k$ for some integer $k$ .

Example

Proving that the sum of two odd integers is even

Prove that the sum of any two odd integers is even.

Let the two odd integers be $2 a + 1$ and $2 b + 1$ , where $a$ and $b$ are integers. Using different letters allows the two odd integers to have different values.
Add and simplify:
$(2a+1)+(2b+1)=2a+2b+2=2(a+b+1).\begin{aligned} (2a+1)+(2b+1) &=2a+2b+2\\ &=2(a+b+1). \end{aligned}$
Since $a$ and $b$ are integers, $a + b + 1$ is also an integer.
The sum therefore has the form two multiplied by an integer, so it is even. Hence the sum of any two odd integers is even.

Common Mistake

Using one variable for two arbitrary integers

Writing both odd integers as $2 k + 1$ assumes that they are equal. Use separate integer variables, such as $2 a + 1$ and $2 b + 1$ , unless equality is given.

Choosing useful algebraic forms

A good proof often depends on translating the conditions into forms that expose the required structure.

Example

Proving divisibility of a product

Prove that the product of two consecutive integers is even.

Let the consecutive integers be $n$ and $n + 1$ , where $n$ is an integer.
Every integer is either even or odd. If $n$ is even, then the product $n (n + 1)$ contains the even factor $n$ , so the product is even.
If $n$ is odd, then $n + 1$ is even, so the product contains the even factor $n + 1$ and is again even.
These two possibilities cover every integer $n$ . Therefore $n (n + 1)$ is always even.

This argument uses deduction together with a split into cases. The split is valid because every integer is either even or odd.

Proof by exhaustion

Proof by exhaustion establishes a statement by dividing the problem into a finite number of possible cases and proving the result in every case.

Definition

Proof by exhaustion

A proof by exhaustion lists or classifies all possible cases, checks each one using valid reasoning and concludes that the claim is true because no cases remain.

This method is useful when:

a variable can take only finitely many stated values;
objects can be divided into a finite set of categories;
possible remainders after division give a finite number of cases.

When an integer is divided by 3, for example, its remainder must be 0, 1 or 2. Therefore every integer has exactly one of the forms

n=3k,n=3k+1,n=3k+2n=3k,\qquad n=3k+1,\qquad n=3k+2

for some integer $k$ .

Example

Classifying square numbers modulo 3

Prove that the square of any integer has remainder 0 or 1 when divided by 3.

Every integer $n$ has one of the forms $3 k$ , $3 k + 1$ or $3 k + 2$ , where $k$ is an integer.
If $n = 3 k$ , then
$n^2=9k^2=3(3k^2),$
so the remainder is 0.
If $n = 3 k + 1$ , then
$n^2=9k^2+6k+1=3(3k^2+2k)+1,$
so the remainder is 1.
If $n = 3 k + 2$ , then
$n^2=9k^2+12k+4=3(3k^2+4k+1)+1,$
so the remainder is again 1.
The three cases include every integer. Therefore an integer square has remainder 0 or 1 when divided by 3.

Tip

Check that the cases are exhaustive

Before checking individual cases, state why your list covers every possibility. For remainder arguments, the possible remainders after division by $d$ are 0, 1, up to $d - 1$ .

Common Mistake

Large or infinite collections

Proof by exhaustion requires a genuinely finite and complete collection of cases. Checking the first hundred integers does not exhaust all integers.

Presenting a rigorous proof

A clear proof should let another mathematician verify every link in the argument. Use complete sentences around your algebra and define all variables.

You should normally:

begin with an arbitrary object satisfying the conditions;
translate definitions into algebraic forms;
justify why newly formed quantities are integers where necessary;
cover every case if you split the argument;
finish with a sentence matching the original claim.

Exam technique

In the exam

Identify the exact hypothesis and conclusion before beginning the algebra.
Define variables precisely, including statements such as “where $k$ is an integer”.
For deduction, ensure that every line follows logically from the previous information.
For exhaustion, state all possible cases and explain why the list is complete.
End by interpreting your final expression and explicitly stating the required conclusion.

Self review

Check yourself

Why does checking several numerical examples usually fail to prove a universal statement?
How would you represent two different even integers algebraically?
What cases would you need to consider when classifying an integer by its remainder after division by 4?

What you'll learn

What is a mathematical proof?

The basic structure of a proof

1. The claim

2. The assumptions

3. The logical argument

4. The conclusion

Implication and equivalence

Proof by deduction

Choosing useful algebraic forms

Proof by exhaustion

Presenting a rigorous proof

Review 1.1.1 Structure of mathematical proof by teaching Genie

1.1.1 Structure of mathematical proof

What you'll learn

What is a mathematical proof?

The basic structure of a proof

1. The claim

2. The assumptions

3. The logical argument

4. The conclusion

Implication and equivalence

Proof by deduction

Choosing useful algebraic forms

Proof by exhaustion

Presenting a rigorous proof

Review 1.1.1 Structure of mathematical proof by teaching Genie

1.1.1 Structure of mathematical proof

What you'll learn

What is a mathematical proof?

The basic structure of a proof

1. The claim

2. The assumptions

3. The logical argument

4. The conclusion

Implication and equivalence

Proof by deduction

Choosing useful algebraic forms

Proof by exhaustion

Presenting a rigorous proof

Review 1.1.1 Structure of mathematical proof by teaching Genie

1.1.1 Structure of mathematical proof Revision Guide

1.1.1 Structure of mathematical proof

What you'll learn

What is a mathematical proof?

The basic structure of a proof

1. The claim

2. The assumptions

3. The logical argument

4. The conclusion

Implication and equivalence

Proof by deduction

Choosing useful algebraic forms

Proof by exhaustion

Presenting a rigorous proof

Review 1.1.1 Structure of mathematical proof by teaching Genie

1.1.1 Structure of mathematical proof Revision Guide