Proof

Proof by exhaustion and counter-example

A proof starts from stated assumptions and moves by logical steps to a conclusion. Every step must follow from the one before. Checking a few cases is not a proof.

Proof by exhaustion

If a statement concerns a small, finite set of cases, check every one.

Every integer is $3n$, $3n + 1$ or $3n + 2$, so check all three.

$(3n)^2 = 9n^2 = 3(3n^2)$

$(3n + 1)^2 = 9n^2 + 6n + 1 = 3(3n^2 + 2n) + 1$

$(3n + 2)^2 = 9n^2 + 12n + 4 = 3(3n^2 + 4n + 1) + 1$

Every case gives $3k$ or $3k + 1$, so the statement is true for all integers.

Direct proof with algebra

For a statement about all integers, let a general integer stand for any value. An even number is $2n$ and an odd number is $2n + 1$.

Let the integers be $n$ and $n + 1$.

$n^2 + (n + 1)^2 = 2n^2 + 2n + 1 = 2(n^2 + n) + 1$

This is $2k + 1$ with $k = n^2 + n$ an integer, so it is odd.

Disproof by counter-example

One case where a statement fails is enough to show it is false. This is the only way a single example can settle a question.

Try values until one fails. When $n = 11$:

$11^2 + 11 + 11 = 143 = 11 \times 13$

This is not prime, so the statement is false.

Proof by contradiction

To prove a statement, assume it is false and show that this leads to something impossible. The assumption must then be wrong.

Assume $\sqrt{2}$ is rational, so $\sqrt{2} = \dfrac{p}{q}$ where $p$ and $q$ are integers with no common factor.

Squaring, $2 = \dfrac{p^2}{q^2}$, so $p^2 = 2q^2$. Hence $p^2$ is even, so $p$ is even. Write $p = 2m$.

Then $4m^2 = 2q^2$, so $q^2 = 2m^2$. Hence $q^2$ is even, so $q$ is even.

Now $p$ and $q$ are both even, which contradicts "no common factor". The assumption was false, so $\sqrt{2}$ is irrational.

Assume there is a greatest odd integer $N$. Then $N + 2$ is also an odd integer, and it is larger than $N$. This contradicts $N$ being greatest, so there is no greatest odd integer.

Writing a contradiction proof

1. State the opposite of what is to be proved: "Assume that ... ".
2. Work forward with correct steps until two statements disagree, or a statement is plainly false.
3. Conclude: "This is a contradiction, so the assumption is false and the original statement is true."

Proof by induction

Induction proves a statement $P(n)$ for every positive integer $n$ in three parts.

1. Basis. Show $P(1)$ is true.
2. Assumption. Assume $P(k)$ is true for some positive integer $k$.
3. Inductive step. Using the assumption, show $P(k + 1)$ is true.

Then $P(1)$ is true, so $P(2)$ is true, so $P(3)$ is true, and so on. The conclusion is that $P(n)$ is true for all positive integers $n$.

A sum

Basis. When $n = 1$, the left side is 1 and the right side is $\dfrac{1 \times 2}{2} = 1$. It is true for $n = 1$.

Assumption. Suppose it is true for $n = k$:

$1 + 2 + \dots + k = \frac{k(k + 1)}{2}$

Step. For $n = k + 1$, add the next term to both sides:

$1 + 2 + \dots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}$

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

Conclusion. It is true for $n = 1$. If it is true for $n = k$ then it is true for $n = k + 1$. Hence it is true for all positive integers $n$.

Divisibility

For a statement such as "$f(n)$ is divisible by $d$", write $f(k + 1)$ in terms of $f(k)$ so that the assumption can be used.

Basis. For $n = 1$: $7 - 1 = 6$, which is divisible by 6.

Assumption. Suppose $7^k - 1$ is divisible by 6, so $7^k - 1 = 6m$ for an integer $m$.

Step.

$7^{k+1} - 1 = 7 \times 7^k - 1 = 7(6m + 1) - 1 = 42m + 6 = 6(7m + 1)$

This is divisible by 6.

Conclusion. True for $n = 1$, and true for $n = k + 1$ whenever it is true for $n = k$, so true for all positive integers $n$.

Writing the conclusion