Proof

Board	Paper	Notes
AQA	Paper 1	Proof by deduction, contradiction, exhaustion, counterexample
Edexcel	P1, P2	Similar; induction in P2
OCR (A)	Paper 1, 2	Proof is integrated throughout
CIE (9709)	P1, P2, P3	Various methods across papers

---

Proof by deduction starts from known axioms, definitions, or previously proved results, and uses Logical steps to arrive at the desired conclusion.

Theorem. $S_n = \dfrac{n}{2}(a + l) = \dfrac{n}{2}[2a + (n-1)d]$.

Proof. Write out the sum forwards and backwards:

$$\begin{aligned} S_n &= a + (a+d) + (a+2d) + \cdots + (a+(n-1)d) \\ S_n &= (a+(n-1)d) + (a+(n-2)d) + \cdots + a \end{aligned}$$

Adding the two rows term by term, each pair sums to $2a + (n-1)d$And there are $n$ such pairs:

$2S_n = n[2a + (n-1)d] \implies S_n = \frac{n}{2}[2a + (n-1)d] \quad \blacksquare$

Theorem. $a^2 - b^2 = (a-b)(a+b)$ for all $a, b \in \mathbb{R}$.

Proof. Expanding the right-hand side:

$(a-b)(a+b) = a^2 + ab - ab - b^2 = a^2 - b^2 \quad \blacksquare$

---

To prove a statement $P$ by contradiction:

1. Assume $\neg P$ (the negation of $P$).
2. Derive a logical contradiction.
3. Conclude that $P$ must be true.

Theorem (Euclid). There are infinitely many prime numbers.

Proof. Suppose, for contradiction, that there are only finitely many primes: $p_1, p_2, \ldots, p_n$.

Consider $N = p_1 p_2 \cdots p_n + 1$.

• $N$ is not divisible by any $p_i$: if $p_i \mid N$Then $p_i \mid (N - p_1 \cdots p_n) = 1$ which is impossible since $p_i \geq 2$.

So $N$ is either prime itself or divisible by a prime not in our list. Either way, there exists a Prime not among $p_1, \ldots, p_n$. This contradicts our assumption that the list was complete. $\blacksquare$

Theorem. $\sqrt{2}$ is irrational.

Proof. Suppose $\sqrt{2} = \dfrac{a}{b}$ where $a, b \in \mathbb{Z}$, $b \neq 0$And $\gcd(a,b) = 1$ (the fraction is in lowest terms).

$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$

So $a^2$ is even, which means $a$ is even (since the square of an odd number is odd). Write $a = 2k$.

$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$

So $b^2$ is even, meaning $b$ is even. But then $\gcd(a,b) \geq 2$Contradicting $\gcd(a,b) = 1$. $\blacksquare$

Theorem. $\log_2 3$ is irrational.

Proof. Suppose $\log_2 3 = \dfrac{a}{b}$ where $a, b \in \mathbb{Z}^+$ and $\gcd(a,b) = 1$.

$2^{a/b} = 3 \implies 2^a = 3^b$

Since $2^a$ is even and $3^b$ is odd, this is a contradiction. $\blacksquare$

---

When the number of cases is finite and small enough, prove each case individually.

Claim. All primes less than 10 are odd.

Proof. The primes less than 10 are: 2, 3, 5, 7.

• 2 is even (the only even prime).
• 3, 5, 7 are odd.

So not all primes less than 10 are odd. The claim is false. The counterexample is 2.

Claim. For all integers $n$ with $1 \leq n \leq 5$, $n^2 + (n+1)^2$ is odd.

Proof. Check each case:

$n$	$n^2 + (n+1)^2$	Odd?
1	1 + 4 = 5	Yes
2	4 + 9 = 13	Yes
3	9 + 16 = 25	Yes
4	16 + 25 = 41	Yes
5	25 + 36 = 61	Yes

All five cases confirmed. $\blacksquare$

Caution: Warning Manageable. You cannot use exhaustion for “all integers” or “all real numbers.”

---

To disprove a universal statement, it suffices to find one example where the statement fails.

Claim. “For all real $x$, $x^2 \gt x$.” Counterexample: $x = 0.5$Since $0.25 \not> 0.5$.

Claim. “All quadratics have two distinct real roots.” Counterexample: $x^2 + 1 = 0$ has no real Roots (discriminant $= -4 \lt 0$).

Claim. “If $n$ is prime, then $2^n - 1$ is prime.” Counterexample: $n = 11$ is prime, but $2^{11}-1 = 2047 = 23 \times 89$.

---

To prove a statement $P(n)$ for all integers $n \geq n_0$:

1. Base case: Prove $P(n_0)$ is true.
2. Inductive hypothesis: Assume $P(k)$ is true for some $k \geq n_0$.
3. Inductive step: Using the hypothesis, prove $P(k+1)$ is true.
4. Conclusion: By the principle of mathematical induction, $P(n)$ is true for all $n \geq n_0$.

### 5.2 Sum of the first $n$ integers

Theorem. $\displaystyle\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$ for all $n \in \mathbb{N}$.

Proof.

Base case ($n=1$): $\displaystyle\sum_{r=1}^{1} r = 1 = \frac{1 \times 2}{2}$. ✓

Inductive hypothesis: Assume $\displaystyle\sum_{r=1}^{k} r = \frac{k(k+1)}{2}$ for some $k \geq 1$.

Inductive step:

$$\begin{aligned} \sum_{r=1}^{k+1} r &= \sum_{r=1}^{k} r + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \quad \mathrm{(by hypothesis)} \\ &= \frac{k(k+1) + 2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{aligned}$$

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

Conclusion: By induction, the formula holds for all $n \in \mathbb{N}$. $\blacksquare$

Theorem. $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$.

Proof.

Base case ($n=1$): $1 = \dfrac{1 \times 2 \times 3}{6} = 1$. ✓

Inductive hypothesis: Assume $\displaystyle\sum_{r=1}^{k} r^2 = \frac{k(k+1)(2k+1)}{6}$.

Inductive step:

$$\begin{aligned} \sum_{r=1}^{k+1} r^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} \\ &= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \\ &= \frac{(k+1)[2k^2+k+6k+6]}{6} \\ &= \frac{(k+1)(2k^2+7k+6)}{6} \\ &= \frac{(k+1)(k+2)(2k+3)}{6} \end{aligned}$$

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

Theorem. $3^n - 1$ is divisible by 2 for all $n \in \mathbb{N}$.

Proof.

Base case ($n=1$): $3^1 - 1 = 2$Which is divisible by 2. ✓

Hypothesis: Assume $3^k - 1 = 2m$ for some integer $m$.

Step: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(2m+1) - 1 = 6m + 3 - 1 = 6m + 2 = 2(3m+1)$.

This is divisible by 2. ✓ $\blacksquare$

Theorem. $4^n - 1$ is divisible by 3 for all $n \in \mathbb{N}$.

Proof.

Base case ($n=1$): $4-1 = 3$Divisible by 3. ✓

Hypothesis: $4^k - 1 = 3m$.

Step: $4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(3m+1)-1 = 12m+4-1 = 12m+3 = 3(4m+1)$. ✓ $\blacksquare$

Theorem. $2^n \gt n$ for all $n \in \mathbb{N}$.

Proof.

Base case ($n=1$): $2 \gt 1$. ✓

Hypothesis: $2^k \gt k$.

Step: $2^{k+1} = 2 \cdot 2^k \gt 2k \geq k + 1$ (since $k \geq 1$ implies $k \geq 1$).

So $2^{k+1} \gt k + 1$. ✓ $\blacksquare$

Theorem. $n! \gt 2^n$ for all $n \geq 4$.

Proof.

Base case ($n=4$): $24 \gt 16$. ✓

Hypothesis: $k! \gt 2^k$ for $k \geq 4$.

Step: $(k+1)! = (k+1) \cdot k! \gt (k+1) \cdot 2^k \geq 5 \cdot 2^k \gt 2 \cdot 2^k = 2^{k+1}$.

Since $k \geq 4$We have $k+1 \geq 5 \gt 2$. ✓ $\blacksquare$

---

• ”$P$ is necessary for $Q$” means $Q \implies P$.
• ”$P$ is sufficient for $Q$” means $P \implies Q$.
• ”$P$ if and only if $Q$” (written $P \iff Q$) means both $P \implies Q$ and $Q \implies P$.

• The converse of $P \implies Q$ is $Q \implies P$ (not logically equivalent).
• The contrapositive of $P \implies Q$ is $\neg Q \implies \neg P$ (logically equivalent).

---

Problem 1

Prove that the product of two odd numbers is odd.

Solution 1

Let the two odd numbers be $2m+1$ and $2n+1$ where $m, n \in \mathbb{Z}$.

$(2m+1)(2n+1) = 4mn + 2m + 2n + 1 = 2(2mn+m+n) + 1$.

This is of the form $2k+1$ (with $k = 2mn+m+n$), hence odd. $\blacksquare$

If you get this wrong, revise: Proof by Deduction — Section 1.

Problem 2

Prove by contradiction that there is no greatest even integer.

Solution 2

Suppose $N$ is the greatest even integer. Then $N = 2k$ for some $k \in \mathbb{Z}$.

But $N + 2 = 2k + 2 = 2(k+1)$ is also even, and $N+2 \gt N$. This contradicts $N$ being the Greatest even integer. $\blacksquare$

If you get this wrong, revise: Proof by Contradiction — Section 2.

Problem 3

Prove by induction that $\displaystyle\sum_{r=1}^{n} r^3 = \left[\frac{n(n+1)}{2}\right]^2$ for all $n \in \mathbb{N}$.

Solution 3

*Base case ($n=1$):* $1^3 = 1 = \left[\dfrac{1 \cdot 2}{2}\right]^2 = 1$. ✓

Hypothesis: $\displaystyle\sum_{r=1}^{k} r^3 = \left[\frac{k(k+1)}{2}\right]^2$.

Step:

$$\begin{aligned} \sum_{r=1}^{k+1} r^3 &= \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3 \\ &= \frac{k^2(k+1)^2}{4} + (k+1)^3 \\ &= \frac{(k+1)^2[k^2 + 4(k+1)]}{4} \\ &= \frac{(k+1)^2(k^2+4k+4)}{4} \\ &= \frac{(k+1)^2(k+2)^2}{4} \\ &= \left[\frac{(k+1)(k+2)}{2}\right]^2 \quad \blacksquare \end{aligned}$$

If you get this wrong, revise: Proof by Mathematical Induction — Section 5.

Problem 4

Prove that $\sqrt{3}$ is irrational.

Solution 4

Suppose $\sqrt{3} = a/b$ in lowest terms with $a, b \in \mathbb{Z}^+$, $\gcd(a,b) = 1$.

$3 = a^2/b^2 \implies a^2 = 3b^2$So $3 \mid a^2$Hence $3 \mid a$. Write $a = 3k$.

$9k^2 = 3b^2 \implies b^2 = 3k^2$So $3 \mid b^2$Hence $3 \mid b$.

But $\gcd(a,b) \geq 3$Contradicting $\gcd(a,b) = 1$. $\blacksquare$

If you get this wrong, revise: $\sqrt{2}$ is irrational — Section 2.3.

Problem 5

Disprove by counterexample: "For all real $x$, $\sin(2x) = 2\sin x$."

Solution 5

Let $x = \pi/4$. $\sin(\pi/2) = 1$ but $2\sin(\pi/4) = 2 \times \dfrac{\sqrt{2}}{2} = \sqrt{2} \neq 1$.

(The correct identity is $\sin(2x) = 2\sin x\cos x$.)

If you get this wrong, revise: Disproof by Counterexample — Section 4.

Problem 6

Prove by induction that $5^n + 3$ is divisible by 4 for all $n \geq 1$.

Solution 6

*Base case ($n=1$):* $5 + 3 = 8$Divisible by 4. ✓

Hypothesis: $5^k + 3 = 4m$.

Step: $5^{k+1} + 3 = 5 \cdot 5^k + 3 = 5(4m-3) + 3 = 20m - 15 + 3 = 20m - 12 = 4(5m-3)$.

Divisible by 4. ✓ $\blacksquare$

If you get this wrong, revise: Divisibility — Section 5.4.

Problem 7

Prove by contradiction that $\log_3 5$ is irrational.

Solution 7

Suppose $\log_3 5 = a/b$ where $a, b \in \mathbb{Z}^+$, $\gcd(a,b)=1$.

$3^{a/b} = 5 \implies 3^a = 5^b$.

$3^a$ is odd and $5^b$ is odd, so no immediate parity contradiction. But: $3^a$ is divisible only by 3, while $5^b$ is divisible only by 5. A positive integer cannot have prime factorisation using only 3s and also only 5s (by the Fundamental Theorem of Arithmetic, prime factorisation is unique). Contradiction. $\blacksquare$

If you get this wrong, revise: $\log_2 3$ is irrational — Section 2.4.

Problem 8

Use proof by exhaustion to show that all integers $n$ with $1 \leq n \leq 6$ satisfy: if $n$ is prime, then $n^2 - 1$ is divisible by 24 or $n = 2$ or $n = 3$.

Solution 8

Primes in range: 2, 3, 5.

$n=2$: $n^2-1 = 3$Not divisible by 24 (special case $n=2$). $n=3$: $n^2-1 = 8$Not divisible by 24 (special case $n=3$). $n=5$: $n^2-1 = 24$Divisible by 24. ✓

So the claim holds: primes 2 and 3 are exceptions, and $5^2 - 1 = 24$ is divisible by 24.

If you get this wrong, revise: Proof by Exhaustion — Section 3.

Problem 9

Prove by induction that $n^3 - n$ is divisible by 6 for all $n \geq 1$.

Solution 9

*Base case ($n=1$):* $1-1=0$Divisible by 6. ✓

Hypothesis: $k^3 - k = 6m$.

Step: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k = 6m + 3k(k+1)$.

Since $k(k+1)$ is always even (product of consecutive integers), $3k(k+1)$ is divisible by 6. So $(k+1)^3 - (k+1) = 6m + 6n = 6(m+n)$. ✓ $\blacksquare$

If you get this wrong, revise: Divisibility — Section 5.4.

Problem 10

Prove that if $a^2 + b^2 = c^2$ for integers $a, b, c$Then at least one of $a, b$ is even.

Solution 10

Proof by contradiction. Suppose both $a$ and $b$ are odd. Write $a = 2m+1$, $b = 2n+1$.

$a^2 + b^2 = (2m+1)^2 + (2n+1)^2 = 4m^2+4m+1 + 4n^2+4n+1 = 2(2m^2+2m+2n^2+2n+1)$

This is even but not divisible by 4. So $c^2$ is even but not divisible by 4, meaning $c$ is even (if $c = 2p$, $c^2 = 4p^2$Which IS divisible by 4). Contradiction. $\blacksquare$

If you get this wrong, revise: Proof by Contradiction — Section 2.

Problem 11

Prove by induction that $\displaystyle\sum_{r=1}^{n}\frac{1}{r(r+1)} = \frac{n}{n+1}$.

Solution 11

*Base case ($n=1$):* $\dfrac{1}{1 \times 2} = \dfrac{1}{2} = \dfrac{1}{1+1}$. ✓

Hypothesis: $\displaystyle\sum_{r=1}^{k}\frac{1}{r(r+1)} = \frac{k}{k+1}$.

Step:

$$\begin{aligned} \sum_{r=1}^{k+1}\frac{1}{r(r+1)} &= \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} \\ &= \frac{k(k+2)+1}{(k+1)(k+2)} \\ &= \frac{k^2+2k+1}{(k+1)(k+2)} \\ &= \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2} \quad \blacksquare \end{aligned}$$

If you get this wrong, revise: Proof by Mathematical Induction — Section 5.

---

• Numerical Methods — Proof techniques complement numerical verification methods, with proof by exhaustion analogous to finite iteration.
• Binomial Expansion — Induction proofs frequently rely on binomial coefficient identities and summation formulas.
• Functions — Understanding domain restrictions and logical quantifiers supports the rigorous setup of proof arguments.
• Differentiation — First principles proofs of derivative rules apply the same deductive structure covered in this topic.