1.6 Simple deductive proof

Why mathematics needs proof

Patterns and conjectures

Mathematics often begins with a pattern. Mark points on a circle and join every pair of points with a straight line (a chord), placing the points so that no three chords meet at one point. Count the regions the circle is divided into.

With 1, 2, 3, 4 and 5 points the circle has 1, 2, 4, 8 and 16 regions. The numbers double each time, so a natural guess is that $n$ points always give $2^{n-1}$ regions. A statement like this, which fits the evidence but has not been proved, is a conjecture.

The conjecture $2^{n-1}$ fails at the very next step: six points give 31 regions, not 32. Five cases in a row agreed with the pattern, and the sixth did not. (The correct number of regions is given by a different formula, which happens to match $2^{n-1}$ for $n \le 5$.) A single case where a statement fails is enough to show that it is false; disproof by counterexample is developed in 1.15.

Deductive reasoning

Since examples cannot show that a statement holds in every case, a different kind of argument is needed. A deductive proof starts from facts that are already accepted (definitions, earlier theorems and the rules of algebra) and moves forward in logical steps, each one following from the steps before. If every step is valid, the conclusion must be true in every case the starting facts cover.

The difference is easy to see with a simple statement such as "the sum of two odd numbers is even". Checking $3 + 5 = 8$, $7 + 11 = 18$ and $101 + 99 = 200$ shows that the statement is plausible. It does not show that it is true for the infinitely many pairs that have not been checked. A proof covers all of them at once by working with general odd numbers written in algebra, as shown later in the section on integers.

Equations and identities

Two kinds of equality

Not every statement with an equals sign has the same meaning. The equation $2x + 1 = 7$ is true only when $x = 3$. The statement $2(x + 3) = 2x + 6$ is true for every value of $x$, because one side is just a rearrangement of the other. Statements of the second kind are called identities.

Many identities are written with an ordinary $=$ sign when it is clear from the context that they hold for all values, such as the laws of exponents in 1.5. The symbol $\equiv$ is used when the difference matters, for example when finding unknown constants or when a question asks for an identity to be proved.

Part (a) is based on a common expansion error: $(x + 3)^2$ is not $x^2 + 9$. The two expressions are equal only at $x = 0$, so substituting one value cannot tell an equation from an identity. Substituting several values can show quickly that a statement is not an identity, which is a useful check, but it can never prove that it is one.

Finding unknown constants in an identity

If two polynomials are identically equal, they must have the same coefficient for every power of $x$. Otherwise their difference would be a non-zero polynomial, which can be zero for only a few values of $x$, not all of them. This principle, called comparing (or equating) coefficients, gives a way to find unknown constants.

Setting out a proof of an identity

Working from one side to the other

To prove that $A \equiv B$, start with one side, usually the more complicated one, and transform it step by step, using only valid algebra, until it becomes the other side. The proof is written as a chain of equalities:

where LHS and RHS stand for the left-hand side and the right-hand side. Each line must equal the line before it for every value of the variable, so the chain shows that the two sides are always equal.

A clear proof has three parts:

1. A starting point: "LHS $=$" followed by the left-hand side (or the right-hand side, if it is easier to start there).

2. A sequence of steps, one change per line, with a short reason where it is not obvious ("expanding", "common denominator", "factorising").

3. An ending that reaches the other side exactly, followed by a statement such as "$=$ RHS, so the identity is proved" or "which is the right-hand side".

Sometimes neither side is clearly simpler. Then both sides can be simplified separately until they reach the same expression. The working must still be kept as two separate chains, one starting from each side, so that no step assumes the result being proved.

Why a proof does not start from the result

A common but invalid way to "prove" $A \equiv B$ is to write down $A = B$, do the same thing to both sides, and arrive at something true, such as $0 = 0$. The trouble is that a true conclusion can be reached from a false starting point. For example, start from the false statement $-1 = 1$ and square both sides: the result $1 = 1$ is true. Working from the statement to be proved assumes the very thing the proof is meant to establish, and some steps (like squaring) cannot be reversed.

More identities

The same method works for any algebraic identity. Choosing which side to start from is part of the skill: expanding brackets is usually easier than factorising, so starting with the side that has brackets is often the better choice.

Numerical proofs

A numerical proof shows that a statement about specific numbers is true using exact arithmetic, never a calculator approximation. A calculator display such as $8.660254038$ cannot prove that two irrational numbers are equal, because it shows only finitely many digits. The laws of exponents and the rules for simplifying surds are the usual tools.

Proofs about integers

Writing integers in algebra

To prove a statement about all integers of a certain kind, write a general integer of that kind in algebraic form. Every even number is $2$ times an integer, every odd number is $1$ more than an even number, and consecutive integers follow one another without gaps.

To show that a result is even, write it as $2 \times (\text{an integer})$. To show that it is a multiple of $k$, write it as $k \times (\text{an integer})$. To show that it is odd, write it as $2 \times (\text{an integer}) + 1$. In each case the expression in the bracket must be shown to be an integer, which is usually true because sums and products of integers are integers.

Sums and products of odd and even numbers

The proof has a simple picture. An odd number is a set of pairs with one left over. When two odd numbers are added, the two left-over items form a new pair, so nothing is left over.

Consecutive integers and multiples

Some proofs need cases. An integer is either even or odd, and if a statement can be proved for each case separately, it is true for all integers. This is still a deductive proof, because the two cases together cover every integer.

Squares of consecutive integers

The identity $(n + 1)^2 - n^2 \equiv 2n + 1$ says that the gap between consecutive square numbers is always odd and increases by 2 each time: $1, 4, 9, 16, 25, \ldots$ have gaps $3, 5, 7, 9, \ldots$ The algebra is short:

The same fact can be seen geometrically. A square of side $n + 1$ is a square of side $n$ with an L-shaped strip added along two edges. The strip contains $n + n + 1$ unit squares.

Read the other way, the identity proves that every odd number $2n + 1$ (with $n \ge 0$) is the difference of two consecutive squares. For example, $13 = 2 \times 6 + 1 = 7^2 - 6^2 = 49 - 36$.

A proved result can be used as a step in later proofs. This is how mathematics builds up: each theorem becomes a tool for the next.

Exam-style questions on proof

Proof questions use the command terms "show that" and "prove". Both need every step written out, starting from one side or from a general case, and ending with a clear conclusion. They often come in two or three linked parts, where a "hence" part uses an identity proved earlier.

Further points that earn or lose marks on proof questions:

• Define every letter used: "Let $n \in \mathbb{Z}$", "where $m$ and $n$ are integers".

• Substituting numbers is never a proof. Numerical checks may be written at the end, but they earn no proof marks.

• Never start from the statement to be proved and work on both sides at once.

• Use $\equiv$ when the question uses it, and keep it in the final line.

Self-check

• To do:

  I can explain the difference between an equation and an identity, and use $\equiv$ correctly.

• To do:

  I can explain why checking examples, however many, does not prove a general statement.

• To do:

  I can prove an identity by starting from one side and transforming it into the other.

• To do:

  I can find unknown constants in an identity by comparing coefficients.

• To do:

  I can write even numbers, odd numbers, consecutive integers and multiples in algebraic form, using different letters for numbers that can differ.

• To do:

  I can prove that a sum, difference or product of integers is even, odd or a multiple of a given number.

• To do:

  I can split a proof into cases when an integer may be even or odd.

• To do:

  I can finish a proof with a clear statement of what has been proved.

1. (a)

   Show that $f(x) = 1 - \sin 2x$.

   [2]2 marks

   Markscheme (a)

   $f(x) = \cos^2 x - 2\sin x\cos x + \sin^2 x$ M1

   $= 1 - 2\sin x\cos x$ A1

   $= 1 - \sin 2x$ AG

   Note: Award M1 for a correct expansion, A1 for using both $\sin^2 x + \cos^2 x = 1$ and $\sin 2x = 2\sin x\cos x$

2. (b)

   Hence, solve $f(x) = \dfrac{3}{2}$, for $0 \le x \le \pi$.

(b) Expanding the left side gives exactly the right side, so this is an identity: $(x + 3)^2 \equiv x^2 + 6x + 9$.

(c) Expanding gives $3x - 6 = 3x - 2$, so $-6 = -2$, which is never true. This is an equation with no solutions.

(d) For $x \neq 0$, factorise the numerator: $\frac{x(x + 2)}{x} = x + 2$. The statement is true for every $x$ for which the left side is defined, so it is an identity (for $x \neq 0$).

The identity is $x^2 + 6x + 11 \equiv x^2 + 2ax + (a^2 + b)$. Compare coefficients.

Coefficient of $x$: $2a = 6$, so $a = 3$.

Constant term: $a^2 + b = 11$, so $9 + b = 11$ and $b = 2$.

Check with any value, for example $x = 1$: the left side is $1 + 6 + 11 = 18$ and the right side is $(1 + 3)^2 + 2 = 18$.

So $x^2 + 6x + 11 \equiv (x + 3)^2 + 2$. This is the completed square form, used for quadratics in 2.6.

The condition $x \neq \pm 1$ is there because both sides involve division by zero at $x = 1$ and $x = -1$. An identity only needs to hold where both sides are defined.

Hence $x^3 - 1 \equiv (x - 1)(x^2 + x + 1)$. This is the factorisation of a difference of two cubes.

which is the result to be shown.

(b) Use $3^{n+2} = 3^n \times 3^2$ (a law of exponents from 1.5) and take out the common factor $3^n$.

Since $3^n$ is an integer when $n$ is a positive integer, $3^{n+2} - 3^n$ is $8$ times an integer, so it is a multiple of 8.

Check with $n = 1$: $3^3 - 3^1 = 24 = 8 \times 3$.

(b) Any two consecutive even numbers can be written $2k$ and $2k + 2$ with $k \in \mathbb{Z}$. By part (a), the difference between their cubes is $8(3k^2 + 3k + 1)$. Since $3k^2 + 3k + 1$ is an integer, the difference is a multiple of 8.

(c) Write $3k^2 + 3k + 1 = 3k(k + 1) + 1$. The product $k(k + 1)$ of two consecutive integers is even, say $k(k + 1) = 2j$ with $j \in \mathbb{Z}$, so

which is odd. The difference is therefore $8 \times (\text{an odd number})$. A multiple of 16 is $8 \times (\text{an even number})$, so the difference is never a multiple of 16.

Check: $4^3 - 2^3 = 56 = 8 \times 7$, and $7$ is odd.

Coefficient of $x$: $-2p = -6$, so $p = 3$.

Constant term: $p^2 + q = 13$, so $q = 13 - 9 = 4$.

(b) By part (a), $x^2 - 6x + 13 = (x - 3)^2 + 4$. The square of a real number is never negative, so $(x - 3)^2 \ge 0$ for all real $x$. Therefore

for all real $x$.

(c) The minimum value is $4$, reached when $x = 3$.

[3]3 marks

[4]4 marks