Proof by Deduction

Constructing logical arguments from assumptions to conclusions

SPEC 1.1 • PROOF

What is Mathematical Proof?

Definition

A mathematical proof is a logical argument that establishes the truth of a statement beyond all doubt, using only accepted facts, definitions, and previously proven results.

Unlike other subjects where evidence supports a conclusion, in mathematics we must prove statements are always true - not just show they work for some examples.

Key Concept

Proof by Deduction is the most common method of proof. We start with known facts and use logical steps to reach our conclusion. Each step must follow logically from the previous ones.

Important

Checking that a statement works for specific values (e.g., "it works for n = 1, 2, 3") is NOT a proof. We must show it works for all possible values.

Structure of Deductive Proof

Every deductive proof follows a clear structure:

Proof Structure

1. State your assumption - Define variables and starting conditions

2. Apply logical steps - Use algebra, known results, or definitions

3. Reach conclusion - Show that the required result follows

4. Write concluding statement - State clearly what has been proven

Exam Tip

Always end your proof with a clear statement such as "Therefore, the sum of two even numbers is always even" or "Hence, the statement is proven." Examiners look for this conclusion.

Algebraic Representations

To prove statements about integers, we need to represent them algebraically:

Type of IntegerAlgebraic FormExamples

Even number

2 n

where

n

is an integer2, 4, 6, 8, ...

Odd number

2 n + 1

where

n

is an integer1, 3, 5, 7, ...

Consecutive integers

n, n + 1, n + 2, ...

5, 6, 7, ...

Consecutive even

2 n, 2 n + 2, 2 n + 4, ...

4, 6, 8, ...

Consecutive odd

2 n + 1, 2 n + 3, 2 n + 5, ...

5, 7, 9, ...

Why This Works

Any even number can be written as

2 n

because even numbers are exactly those divisible by 2. Similarly, odd numbers are always 1 more than an even number, hence

2 n + 1

.

Worked Example01

Prove that the sum of any two even numbers is always even.

1

Let the two even numbers be

2 m

and

2 n

, where

m

and

n

are integers.

2

Their sum is:

2 m + 2 n = 2 (m + n)

3

Since

m

and

n

are integers,

(m + n)

is also an integer.

4

Therefore

2 (m + n)

is a multiple of 2, so it is even.

Conclusion: The sum of any two even numbers is always even.

Worked Example02

Prove that the product of any two odd numbers is always odd.

1

Let the two odd numbers be

2 m + 1

and

2 n + 1

, where

m

and

n

are integers.

2

Their product is:

(2 m + 1) (2 n + 1)

3

Expanding:

= 4 mn + 2 m + 2 n + 1

4

Factorising:

= 2 (2 mn + m + n) + 1

5

Since

m

and

n

are integers,

(2 mn + m + n)

is an integer. Let this equal

k

.

6

So the product is

2 k + 1

, which is in the form of an odd number.

Conclusion: The product of any two odd numbers is always odd.

Worked Example03

Prove that $n^{2} + n$ is always even for any integer $n$ .

1

We can factorise:

n^{2} + n = n (n + 1)

2

Now

n

and

n + 1

are consecutive integers.

3

Of any two consecutive integers, exactly one must be even and one must be odd.

4

Therefore the product

n (n + 1)

includes an even factor.

5

Any integer multiplied by an even number gives an even result.

Conclusion: Therefore

n^{2} + n

is always even for any integer

n

.

Completion of the Square

To prove that a quadratic expression is always positive or always negative, we use completion of the square.

Method

Convert

a x^{2} + b x + c

into the form

a (x + p)^{2} + q

Since

(x + p)^{2} \geq 0

for all real

x

, the minimum or maximum value depends on the sign of

a

.

Key Results

If

a > 0

and

q > 0

, then

a (x + p)^{2} + q > 0

for all

x

(always positive)

If

a < 0

and

q < 0

, then

a (x + p)^{2} + q < 0

for all

x

(always negative)

Remember

A squared term is always greater than or equal to zero:

(anything)^{2} \geq 0

Worked Example04

Prove that $- n^{2} + 4 n - 8$ is negative for all values of $n$ .

1

Factor out

- 1

:

- n^{2} + 4 n - 8 = - (n^{2} - 4 n + 8)

2

Complete the square inside the bracket:

n^{2} - 4 n + 8 = (n - 2)^{2} - 4 + 8

3

Simplify:

= (n - 2)^{2} + 4

4

So:

- n^{2} + 4 n - 8 = - [(n - 2)^{2} + 4] = - (n - 2)^{2} - 4

5

Since

(n - 2)^{2} \geq 0

, we have

- (n - 2)^{2} \leq 0

6

Therefore

- (n - 2)^{2} - 4 \leq 0 - 4 = - 4 < 0

Conclusion: Hence

- n^{2} + 4 n - 8

is negative for all values of

n

(in fact, always at most

- 4

).

Proving Identities

An identity is an equation that is true for all values of the variable. We use the symbol

\equiv

to denote "is identically equal to".

Method

To prove an identity

A \equiv B

:

Start with one side (usually the more complicated one)

Use algebraic manipulation to transform it

Arrive at the other side

Important

Never start by assuming the identity is true and working on both sides simultaneously. This is circular reasoning. Always work from one side to reach the other.

Common Techniques

Expanding brackets, factorising, using algebraic identities such as

(a + b)^{2} = a^{2} + 2 ab + b^{2}

and

(a - b)^{2} = a^{2} - 2 ab + b^{2}

Worked Example05

Prove that $(a + b)^{2} - (a - b)^{2} \equiv 4 ab$

1

Start with the LHS:

(a + b)^{2} - (a - b)^{2}

2

Expand

(a + b)^{2} = a^{2} + 2 ab + b^{2}

3

Expand

(a - b)^{2} = a^{2} - 2 ab + b^{2}

4

Substitute:

(a^{2} + 2 ab + b^{2}) - (a^{2} - 2 ab + b^{2})

5

Simplify:

a^{2} + 2 ab + b^{2} - a^{2} + 2 ab - b^{2}

6

= 4 ab

= RHS

Conclusion: Hence

(a + b)^{2} - (a - b)^{2} \equiv 4 ab

as required.

Worked Example06

Prove that $n^{3} - n$ is divisible by 6 for all positive integers $n$ .

1

Factorise:

n^{3} - n = n (n^{2} - 1) = n (n - 1) (n + 1)

2

This is the product of three consecutive integers:

(n - 1), n, (n + 1)

3

Of any three consecutive integers, at least one must be divisible by 2 (even).

4

Of any three consecutive integers, exactly one must be divisible by 3.

5

Therefore the product is divisible by both 2 and 3.

6

Since 2 and 3 are coprime, the product is divisible by

2 \times 3 = 6

.

Conclusion: Hence

n^{3} - n

is divisible by 6 for all positive integers

n

.

Common Pitfalls in Proof

Mistake 1

Using examples instead of proof

Showing "it works for n = 1, 2, 3" is verification, not proof. You must prove it for ALL values.

Mistake 2

Not defining variables

Always write "Let n be an integer" or "Let 2m and 2n be even numbers where m, n are integers".

Mistake 3

Missing conclusion

Always end with a statement like "Therefore..." or "Hence..." that directly states what was proven.

Mistake 4

Circular reasoning

Never assume what you're trying to prove. Start from given information only.

Practice

Question 1: Prove that the sum of any three consecutive integers is divisible by 3.

1

Let the three consecutive integers be

n

,

n + 1

, and

n + 2

, where

n

is an integer.

2

Their sum is:

n + (n + 1) + (n + 2) = 3 n + 3

3

Factorising:

3 n + 3 = 3 (n + 1)

4

Since

n

is an integer,

(n + 1)

is an integer.

Conclusion: Therefore

3 (n + 1)

is a multiple of 3, so the sum is divisible by 3.

Practice

Question 2: Prove that

(2 n + 1)^{2} - (2 n - 1)^{2}

is a multiple of 8 for all positive integers

n

.

1

Expand

(2 n + 1)^{2} = 4 n^{2} + 4 n + 1

2

Expand

(2 n - 1)^{2} = 4 n^{2} - 4 n + 1

3

Subtract:

(4 n^{2} + 4 n + 1) - (4 n^{2} - 4 n + 1)

4

Simplify:

= 4 n^{2} + 4 n + 1 - 4 n^{2} + 4 n - 1 = 8 n

5

Since

n

is an integer,

8 n

is a multiple of 8.

Conclusion: Hence

(2 n + 1)^{2} - (2 n - 1)^{2}

is always a multiple of 8.

Practice

Question 3: Prove that

n^{2} + 2

is not divisible by 4 for any integer

n

.

1

Consider two cases:

n

is even or

n

is odd.

2

Case 1: If

n = 2 k

(even), then

n^{2} + 2 = 4 k^{2} + 2 = 4 k^{2} + 2

3

This gives remainder 2 when divided by 4, so not divisible by 4.

4

Case 2: If

n = 2 k + 1

(odd), then

n^{2} + 2 = (2 k + 1)^{2} + 2 = 4 k^{2} + 4 k + 1 + 2

5

= 4 k^{2} + 4 k + 3 = 4 (k^{2} + k) + 3

6

This gives remainder 3 when divided by 4, so not divisible by 4.

Conclusion: In both cases,

n^{2} + 2

is not divisible by 4.

Summary

Key Concepts

ConceptDescription

Proof by DeductionStart from known facts, use logical steps to reach conclusion

Even numbers

2 n

where

n

is an integer

Odd numbers

2 n + 1

where

n

is an integer

Always positive/negativeComplete the square and analyse the result

IdentitiesTransform one side to equal the other

Exam Checklist

Define all variables clearly at the start

Show every algebraic step - never skip working

Write a clear concluding statement

Use correct notation:

\equiv

for identities

Never use specific examples as proof