# Proof techniques (HL only)

> IB Mathematics: Analysis and Approaches HL · Number & Algebra
> Source: https://www.owlsprep.com/study/ib-math-aa-hl-u1-proof-techniques/

This sub-topic covers core proof techniques required for IB Mathematics AA HL, including direct proof, proof by contrapositive, contradiction, and mathematical induction. You will learn to construct logically valid proofs for algebraic and number theory statements.

**Prerequisites:** [Basic logic and set theory](https://www.owlsprep.com/study/ib-math-aa-hl-u1-basic-logic-sets/); [Algebraic manipulation](https://www.owlsprep.com/study/ib-math-aa-hl-u2-algebraic-expressions/)

## Learning objectives

- Distinguish between core proof techniques for mathematical statements
- Apply direct proof, contrapositive, contradiction, and induction correctly
- Identify common logical errors in invalid proofs
- Construct complete, exam-compliant proofs for assessment questions

## Direct Proof & Proof by Contrapositive

**Direct Proof** — A proof that starts from accepted true axioms or assumptions, and uses sequential logical steps to reach the desired conclusion.

*Example:* Proving the sum of two even integers is even

For statements of the form $P \Rightarrow Q$, direct proof assumes $P$ is true, then shows $Q$ must follow. This works best when assumptions are easy to work with directly. When the negation of $P$ and $Q$ are simpler to use, we use proof by contrapositive.

**Proof by Contrapositive** — Uses the logical equivalence $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$. Instead of proving the original statement, we prove the contrapositive is true.

*Example:* Proving if $n^2$ is even, $n$ is even

**Worked example:** Prove that if $n^2$ is even, then $n$ is even.

1. Original statement is $P \Rightarrow Q$, where $P: n^2$ even, $Q: n$ even. The contrapositive is $\neg Q \Rightarrow \neg P$: if $n$ is odd, then $n^2$ is odd.
2. Assume $n$ is odd, so we can write it as:
3. $$n = 2k + 1 \text{ for some integer } k$$
4. Square both sides:
5. $$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$
6. Since $2k^2 + 2k$ is an integer, $n^2$ is odd. The contrapositive is true, so the original statement is true.

> **tip**
>
> Always explicitly state you are using contrapositive at the start of your proof — examiners look for this step to award full marks.

## Proof by Contradiction

**Proof by Contradiction** — To prove a statement $P$ is true, you first assume $P$ is false, then show this assumption leads to a clear logical contradiction. This means the original assumption is wrong, so $P$ must be true.

*Example:* Proving $\sqrt{2}$ is irrational

Contradiction is particularly useful for proving statements about irrationality, infinity, and non-existence, which are hard to prove directly. The method works by ruling out the only alternative to your claim.

**Worked example:** Prove that $\sqrt{2}$ is irrational.

1. Assume for contradiction that $\sqrt{2}$ is rational, so we can write it in lowest terms as:
2. $$\sqrt{2} = \frac{p}{q}, \quad p,q \text{ coprime integers}, q > 0$$
3. Square both sides and rearrange:
4. $$p^2 = 2q^2$$
5. This means $p^2$ is even, so $p$ must be even. Let $p=2k$ for some integer $k$, substitute back:
6. $$(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies q^2 = 2k^2$$
7. By the same logic, $q^2$ is even so $q$ is even. This is a contradiction: we assumed $p$ and $q$ are coprime, but both are even so share a factor of 2.
8. Therefore, the original assumption that $\sqrt{2}$ is rational is false, so $\sqrt{2}$ is irrational.

> **tip**
>
> Always explicitly name the contradiction you found, then state your final conclusion. Missing this step costs marks.

## Principle of Mathematical Induction

**Mathematical Induction** — A technique to prove statements that hold for all integers $n \geq n_0$, consisting of three core logical steps: base case, inductive hypothesis, and inductive step.

Induction is one of the most frequently tested proof techniques in IB AA HL, used for summation formulas, divisibility statements, inequalities, and recursive sequence results.

**Worked example:** Prove by induction that for all positive integers $n$, $\sum_{r=1}^n r = \frac{n(n+1)}{2}$.

1. Step 1: Base case, test $n=1$:
2. $$\text{LHS} = 1, \quad \text{RHS} = \frac{1(1+1)}{2} = 1$$
3. The statement holds for $n=1$, so base case is proven.
4. Step 2: Inductive hypothesis: assume the statement holds for $n=k$, for some positive integer $k$:
5. $$\sum_{r=1}^k r = \frac{k(k+1)}{2}$$
6. Step 3: Inductive step: prove the statement holds for $n=k+1$:
7. $$\sum_{r=1}^{k+1} r = \sum_{r=1}^k r + (k+1)$$
8. Substitute the inductive hypothesis and simplify:
9. $$= \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$$
10. This matches the formula for $n=k+1$, so if the statement holds for $k$, it holds for $k+1$. By the principle of mathematical induction, the statement is true for all positive integers $n$.

> **warning**
>
> Never skip writing the inductive hypothesis or the final concluding statement. These are explicitly marked in IB exams.

## Identifying Invalid Proofs

IB exams often ask you to spot errors in incomplete or invalid proofs. The most common invalid arguments rely on incorrect logic, even if the final conclusion is right.

**Check your understanding**

Which of the following is a valid proof that the sum of two even numbers is even?

1. 

   - I tested 2+4=6 (even), 8+12=20 (even), so the rule is true
   - If $a$ and $b$ are even, $a=2k$ and $b=2m$ for integers $k,m$, so $a+b=2(k+m)$, which is even by definition
   - All even numbers I checked work, so the statement must be true

   *Answer:* If $a$ and $b$ are even, $a=2k$ and $b=2m$ for integers $k,m$, so $a+b=2(k+m)$, which is even by definition

   *Why:* Correct! This is a general direct proof that works for all even numbers. Testing specific cases never proves a general statement.

## Common pitfalls

- **Wrong:** Prove a general statement by checking specific examples
  - Why it fails: A statement is only proven if it holds for all cases, not just the ones you tested
  - Correct: Use a general argument that applies to all values satisfying the problem's assumptions
- **Wrong:** Skip writing the inductive hypothesis or final conclusion for induction
  - Why it fails: IB examiners award explicit marks for these steps, even if the algebra is correct
  - Correct: Always write 'assume the statement holds for $n=k$' and end with 'by induction, the statement holds for all $n \geq n_0$'
- **Wrong:** Divide by a variable without checking it cannot equal zero
  - Why it fails: Division by zero is undefined, which creates a fatal flaw in your proof
  - Correct: Explicitly confirm the variable is non-zero before dividing, or handle the zero case separately
- **Wrong:** Mix up contrapositive and contradiction
  - Why it fails: They are logically related but distinct methods, misapplication leads to invalid proofs
  - Correct: Remember: contrapositive proves $P \Rightarrow Q$ by proving $\neg Q \Rightarrow \neg P$; contradiction assumes $\neg P$ and derives a contradiction
- **Wrong:** Assume what you are trying to prove (circular reasoning)
  - Why it fails: This means your proof does not actually demonstrate the result
  - Correct: Always start from known true statements and work towards the conclusion you need to prove

## Cheatsheet

| Proof Technique | When to Use | Core Steps |
| --- | --- | --- |
| Direct Proof | Working forward from assumptions is straightforward | 1. Assume $P$ true 2. Derive $Q$ logically |
| Contrapositive | Prove $P \Rightarrow Q$, negation is easier to use | 1. State contrapositive $\neg Q \Rightarrow \neg P$ 2. Prove directly |
| Contradiction | Prove irrationality, non-existence, or negative claims | 1. Assume claim false 2. Derive contradiction 3. Conclude original claim true |
| Induction | Prove for all integers $n \geq n_0$ | 1. Prove base case 2. Assume true for $n=k$ 3. Prove for $n=k+1$ 4. Conclude by induction |

## What's next

Proof techniques are the foundation of all advanced mathematics, and they appear throughout the IB AA HL course, from calculus to complex numbers. Mastering these techniques will help you construct logical arguments for extended response questions, which carry a large proportion of marks in HL papers. You will encounter induction again when working with sequences, series, and recursive functions, while contradiction and contrapositive are used in topics like number theory and calculus. Building a strong understanding of proof will also prepare you for university-level mathematics studies.

- [Complex numbers fundamentals](https://www.owlsprep.com/study/ib-math-aa-hl-u1-complex-numbers-fundamentals/)
- [Polar and exponential form of complex numbers](https://www.owlsprep.com/study/ib-math-aa-hl-u1-polar-and-exponential-form-of/)
- [De Moivre's theorem](https://www.owlsprep.com/study/ib-math-aa-hl-u1-de-moivre-s-theorem/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/ib-math-aa-hl-u1-proof-techniques/