STEP (Sixth Term Examination Paper)

A proof is a chain of logical steps that starts from accepted facts or stated assumptions and ends at the result, with every step following from the ones before it. Examples never prove a general statement, however many there are, but a single counter-example disproves it. Most of the methods below appear in unfamiliar settings, so what matters is knowing why each one works.

Notation for logic

The symbol $\Rightarrow$ means "implies": $P \Rightarrow Q$ says that whenever $P$ is true, $Q$ is true. $P \Leftarrow Q$ is the same statement read the other way, and $P \Leftrightarrow Q$ means both hold, which is read "$P$ if and only if $Q$".

$P$ is a sufficient condition for $Q$ when $P \Rightarrow Q$, because knowing $P$ is enough to be sure of $Q$. $P$ is a necessary condition for $Q$ when $Q \Rightarrow P$, because $Q$ cannot hold without $P$. When each implies the other, $P$ is necessary and sufficient, and the two statements are equivalent.

For example, $x = 2$ is sufficient for $x^2 = 4$ but not necessary, since $x = -2$ also works. And $x^2 = 4$ is necessary for $x = 2$ but not sufficient.

A statement and its converse are different claims. "If $n$ is a multiple of 6 then $n$ is even" is true and its converse "if $n$ is even then $n$ is a multiple of 6" is false. To prove $P \Leftrightarrow Q$ there are two separate tasks, $P \Rightarrow Q$ and $Q \Rightarrow P$, and a proof that only does one of them is incomplete. The contrapositive of $P \Rightarrow Q$ is $\text{not } Q \Rightarrow \text{not } P$, which is logically the same statement and is sometimes easier to prove.

Proof by deduction

Deduction starts from known facts and applies algebra step by step. A general integer is written with a letter, so that the argument covers every case at once. An even number is $2k$ and an odd number is $2k+1$ for an integer $k$.

To show that the difference of the squares of two consecutive integers is odd, let the integers be $n$ and $n+1$:

which has the form $2k+1$ with $k = n$, so it is odd. Proving something for a few particular values of $n$ would not be a proof, and the letter is what makes this one general.

Two different integers must be given two different letters. To show that the product of two odd numbers is odd, write them as $2a+1$ and $2b+1$ and multiply: $(2a+1)(2b+1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1$, which is odd.

Proof by exhaustion

Exhaustion splits the possibilities into a finite number of cases that cover everything, and proves the result in each case.

To show that the square of any integer leaves remainder 0 or 1 when divided by 3, every integer has one of the forms $3k$, $3k+1$ or $3k+2$:

The remainders are 0, 1 and 1. The cases must be complete, which is why the three forms above are used rather than "a few values of $n$". Exhaustion is practical only when the number of cases is small, and it is often combined with a parity split or a split by sign.

Disproof by counter-example

One case where a statement fails is enough to show it is false. The claim that $n^2 + n + 41$ is prime for every positive integer $n$ is true for $n = 1, 2, \dots, 39$, but for $n = 41$:

which is not prime. A counter-example has to satisfy the conditions of the claim and break its conclusion, so it should be checked against both.

Proof by contradiction

Assume the statement is false, follow the consequences and reach something impossible; the assumption must then have been wrong. The "something impossible" may be a contradiction of the assumption itself, of a known fact, or of two of the derived statements.

The square root of 2 is irrational

Suppose $\sqrt{2} = \dfrac{p}{q}$ where $p$ and $q$ are integers with no common factor. Then $p^2 = 2q^2$, so $p^2$ is even, and therefore $p$ is even (an odd number squared is odd). Write $p = 2m$. Then $4m^2 = 2q^2$, so $q^2 = 2m^2$ and $q$ is even too. Both $p$ and $q$ are even, which contradicts the assumption that they have no common factor. So $\sqrt{2}$ is irrational.

There are infinitely many primes

Suppose there were only finitely many primes, $p_1, p_2, \dots, p_k$. Let $N = p_1 p_2 \cdots p_k + 1$. Dividing $N$ by any $p_i$ leaves remainder 1, so none of the listed primes divides $N$. But $N > 1$ has a prime factor, since it is either prime or a product of primes, and that prime is not on the list. This contradicts the assumption that the list held every prime.

Using contradiction in new settings

The same pattern solves many unfamiliar problems: state the negation of the claim carefully, use it, and look for an inequality that cannot hold, a parity clash or a number that would be both rational and irrational. Negating a statement needs care. The negation of "all $x$ satisfy $P$" is "some $x$ fails $P$", and the negation of "$a$ and $b$ are both positive" is "at least one of $a$, $b$ is not positive".

Proof by induction

Induction proves a statement $P(n)$ for every integer $n \ge n_0$. There are two parts.

1. Base case: show $P(n_0)$ is true.
2. Inductive step: show that if $P(k)$ is true for some $k \ge n_0$, then $P(k+1)$ is true.

The base case starts the chain and the inductive step keeps it going, so $P(n_0)$ gives $P(n_0+1)$, which gives $P(n_0+2)$, and so on. A conclusion sentence finishes the argument: "$P(n)$ is true for all integers $n \ge n_0$ by induction". Both parts are required. A step with no base case proves nothing, since for example "$n = n + 1$" passes every inductive step.

A summation

To prove $\displaystyle \sum_{r=1}^{n} r^3 = \frac{n^2(n+1)^2}{4}$:

For $n = 1$ the left side is 1 and the right side is $\dfrac{1 \times 4}{4} = 1$.

Assume the result for $n = k$. Then for $n = k+1$:

which is the formula with $n = k+1$.

Divisibility

To show that $7^n - 1$ is divisible by 6 for every $n \ge 1$, write $f(n) = 7^n - 1$. Then $f(1) = 6$. If $f(k) = 6m$ for an integer $m$, then

so $f(k+1)$ is divisible by 6.

Strong and two-step induction

When a statement about $n+1$ depends on earlier cases and not only the last one, assume several earlier cases. For the sequence $u_{n+2} = 5u_{n+1} - 6u_n$ with $u_0 = 2$ and $u_1 = 5$, the claim is $u_n = 2^n + 3^n$. The base cases are $n = 0$ and $n = 1$, where $2^0 + 3^0 = 2$ and $2 + 3 = 5$. Assuming the formula for $n = k$ and $n = k+1$:

Two base cases are needed here because the inductive step uses two previous terms.

Induction can also be applied to inequalities, to derivatives such as $\dfrac{d^n}{dx^n}\left(x e^x\right)$ and to results about matrices and complex numbers. In every case the inductive step should show where the assumption $P(k)$ is used, since a step that never uses it has proved something else.