Proof | A-Level - Wyatt's Notes

------- | ---------- | ------------------------------------------------------------- | | AQA | Paper 1 | Proof by deduction,” date: 2025-06-02T16:25:28.480Z tags:

• Maths
• ALevel categories:
• Maths

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:

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

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

Proof. Expanding the right-hand side:

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).

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

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$.

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:

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$.

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:

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:

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).

• 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.