Mathematical Proof

Definitions.

• $n$ is EVEN $\Leftrightarrow$ $n = 2k$ for some integer $k$.
• $n$ is ODD $\Leftrightarrow$ $n = 2k + 1$ for some integer $k$.

These definitions are the starting point of nearly every parity proof.

Worked example. Prove that the sum of two odd integers is even.

Let $m = 2a + 1$ and $n = 2b + 1$ for integers $a, b$.

$m + n = 2a + 1 + 2b + 1 = 2(a + b + 1)$.

Since $a + b + 1$ is an integer, $m + n$ is even. ✓

Worked example. Prove that if $n$ is odd, $n^2$ is odd.

Let $n = 2k + 1$. Then $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$.

Since $2k^2 + 2k$ is an integer, $n^2$ has form $2(\text{integer}) + 1$ — so $n^2$ is odd. ✓

Worked example. Prove that the product of two consecutive integers is even.

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

If $n$ is even, $n = 2k$, so $n(n+1) = 2k(n+1) = 2[k(n+1)]$ — even.

If $n$ is odd, $n + 1$ is even, so $n(n+1)$ is divisible by 2 — even.

In either case, $n(n + 1)$ is even. ✓

Structure. Define what 'odd' or 'even' means, substitute into the expression, factor out 2 (or the relevant divisor), and conclude.

Statement form. 'Prove that for all positive integers $n$, ___ is divisible by ___.'

To prove divisibility by $d$, write the expression as $d \cdot (\text{integer})$.

Worked example. Prove that the sum of any three consecutive integers is divisible by 3.

Let the three consecutive integers be $n$, $n + 1$, $n + 2$.

Sum: $n + (n + 1) + (n + 2) = 3n + 3 = 3(n + 1)$.

Since $n + 1$ is an integer, the sum is divisible by 3. ✓

Worked example. Prove that the sum of any five consecutive integers is divisible by 5.

Let $n - 2, n - 1, n, n + 1, n + 2$. (Centring at $n$ is a clean choice.)

Sum: $5n$. Divisible by 5. ✓

(Centring around $n$ is a common trick — the symmetric terms cancel.)

Worked example. Prove that $n^3 - n$ is divisible by 6 for every positive integer $n$.

Factorise: $n^3 - n = n(n^2 - 1) = n(n - 1)(n + 1) = (n - 1) n (n + 1)$.

This is a PRODUCT OF THREE CONSECUTIVE INTEGERS.

• Among any three consecutive integers, at least one is even (divisible by 2).
• Among any three consecutive integers, exactly one is divisible by 3.

So the product is divisible by both 2 and 3, hence by 6 (since $\gcd(2, 3) = 1$). ✓

This 'invoke a property of consecutive integers' is a common AA SL Paper 1 technique.

Worked example (algebraic identity). Show that $(2n + 1)^2 - (2n - 1)^2 = 8n$.

LHS $= 4n^2 + 4n + 1 - (4n^2 - 4n + 1) = 8n$. ✓

This proves the difference of squares of consecutive odd numbers is always divisible by 8 — a classic Paper 1 result.