IB AA: Proof Techniques

Mastering proof techniques is the cornerstone of success in IB Mathematics: Analysis and Approaches, particularly at Higher Level. These methods transform you from a calculator of answers into a rigorous mathematical thinker, capable of constructing logical arguments that verify universal truths. Understanding when and how to apply different proof strategies is essential for tackling exam problems and for developing the analytical skills valued in university STEM courses.

The Logical Structure of Mathematical Arguments

Every valid proof rests on a foundation of clear logic. A mathematical argument is a sequence of statements, each following logically from previous ones, that demonstrates the truth of a proposition. You must begin by understanding the statement to be proven, often in the form "If P, then Q" (implication). The hypothesis (P) is what you assume to be true, and the conclusion (Q) is what you must show follows. The logical connective "if-then" is crucial; proving an implication does not require proving P is true, only that Q is true whenever P is true.

The building blocks are axioms (accepted truths), definitions, and previously proven theorems. For example, to prove a statement about even numbers, you would use the definition: an integer $n$ is even if there exists an integer $k$ such that $n=2k$. A logical argument often uses deductive reasoning: if all humans are mortal (major premise), and Socrates is human (minor premise), then Socrates is mortal (conclusion). In mathematics, this structure is implicit but must be meticulously followed. A failure in logic, such as affirming the consequent (assuming Q true implies P is true), invalidates the entire proof.

Direct Proof: The Straightforward Approach

Direct proof is the most intuitive method, where you start with the hypothesis and manipulate it using established rules until you arrive at the conclusion. It is a linear chain of reasoning. For instance, prove that the sum of two even integers is even.

1. Hypothesis: Let $a$ and $b$ be even integers.
2. Definition: By definition, $a=2m$ and $b=2n$ for some integers $m$ and $n$.
3. Manipulation: Their sum is $a+b=2m+2n=2(m+n)$.
4. Conclusion: Since $m+n$ is an integer, $2(m+n)$ is even. Therefore, the sum is even.

The power of direct proof lies in its clarity. You assume P, use algebra, definitions, and theorems, and directly show Q. This method is ideal for proving properties of numbers, sets, and identities. Always ensure each step is justified; skipping a step because it "seems obvious" can introduce gaps. In IB AA, you will frequently use direct proof for algebraic and calculus-based statements where a sequence of inequalities or derivatives leads to the desired result.

Proof by Contradiction: Assuming the Opposite

When a direct path is elusive, proof by contradiction (or reductio ad absurdum) is a powerful alternative. You start by assuming the negation of the statement you want to prove is true. Then, through logical deduction, you show that this assumption leads to an impossibility—a contradiction with a known fact or with the assumption itself. This contradiction proves that your initial assumption (the negation) must be false, and therefore the original statement is true.

A classic example is proving that $\sqrt{2}$ is irrational.

1. Assume the negation: Suppose $\sqrt{2}$ is rational. Then it can be written as $\sqrt{2}=\frac{a}{b}$ for integers $a$ and $b$ with no common factors (in simplest form).
2. Deduce: Squaring both sides gives $2=\frac{a^2}{b^2}$, so $a^2=2b^2$. This implies $a^2$ is even, so $a$ must be even (a lemma proven separately). Let $a=2k$.
3. Substitute: Then $(2k{)}^2=2b^2$ → $4k^2=2b^2$ → $b^2=2k^2$. This implies $b^2$ is even, so $b$ is even.
4. Contradiction: Both $a$ and $b$ are even, contradicting our assumption that they have no common factors. Therefore, the original assumption is false, and $\sqrt{2}$ is irrational.

This method is excellent for proving uniqueness ("there is only one..."), non-existence, or statements where the negation gives you something concrete to work with. The key is to deduce a contradiction that is logically unavoidable.

Proof by Mathematical Induction

Proof by mathematical induction is the standard technique for proving statements that are asserted for all natural numbers (e.g., "For all $n\in \mathbb{N}$, $S(n)$ is true"). It works like dominoes: if you can knock the first one down and prove that each domino knocks down the next, then all dominoes fall. The process has two critical steps:

1. Base Case: Verify the statement is true for the initial value, usually $n=1$.
2. Inductive Step: Assume the statement is true for some arbitrary natural number $k$ (this is the inductive hypothesis). Then, using this assumption, prove that the statement must also be true for $n=k+1$.

Consider proving that the sum of the first $n$ odd numbers is $n^2$: $1+3+5+...+(2n-1)=n^2$.

• *Base Case ($n=1$):* Left side is $1$, right side is $1^2=1$. True.
• Inductive Hypothesis: Assume true for $n=k$: $1+3+...+(2k-1)=k^2$.
• *Inductive Step ($n=k+1$):* We need to show $1+3+...+(2k-1)+(2(k+1)-1)=(k+1{)}^2$.

Starting with the left side: $[1+3+...+(2k-1)]+(2k+1)=k^2+(2k+1)$ (by the inductive hypothesis). Simplify: $k^2+2k+1=(k+1{)}^2$. This equals the right side. Since both steps hold, by mathematical induction, the statement is true for all $n\in \mathbb{N}$.

Induction is indispensable for sequences, series, divisibility claims, and inequalities. Remember, both steps are mandatory; a missing base case or a flawed inductive step renders the proof invalid.

Disproving Statements with Counterexamples

Not all conjectures are true, and part of mathematical reasoning is recognizing falsehoods. To disprove a universal statement ("For all x, P(x) is true"), you only need to find a single counterexample—a specific instance where the statement fails. This is often simpler than proving something true, as one exception destroys a universal claim.

For example, consider the statement: "For all prime numbers $p$, $2^p-1$ is prime." This seems plausible for small primes: $2^2-1=3$ (prime), $2^3-1=7$ (prime), $2^5-1=31$ (prime). However, for $p=11$, we find $2^{11}-1=2047$. Since $2047=23\times 89$, it is composite. Thus, $p=11$ is a counterexample that disproves the universal statement. This demonstrates the danger of extrapolating from a few cases; rigorous proof requires general reasoning, while disproof requires only one verified counterexample.

When hunting for counterexamples, test edge cases: very small numbers, very large numbers, zero, negative numbers if the domain allows, and unusual values. In IB AA, you might encounter conjectures about function behavior or derivative properties where a counterexample quickly resolves a true/false question.

Common Pitfalls

1. Circular Reasoning: Accidentally assuming what you are trying to prove. For instance, in a proof that ${\sin }^{2}x+{\cos }^{2}x=1$, starting with this identity to derive itself. Correction: Always begin with the hypothesis or known truths independent of the conclusion. Use definitions and axioms as your starting point.

1. Incorrect Base Case in Induction: Verifying the base case for the wrong starting value or skipping it entirely. If your statement is claimed for $n\ge 5$, your base case must be $n=5$. Correction: Carefully identify the smallest integer for which the statement is asserted and prove it explicitly.

1. Misapplying the Inductive Hypothesis: Using the assumption for $n=k$ to prove the case for $n=k+1$ incorrectly, often by not aligning the expressions properly. Correction: In the inductive step, clearly state the hypothesis and show algebraically how it leads to the $k+1$ case. Write out the sum or formula for $k+1$ and explicitly substitute using the hypothesis.

1. Overlooking Hidden Assumptions in Contradiction: Introducing an extra, unjustified assumption when negating the statement, leading to a flawed contradiction. Correction: Precisely formulate the logical negation. For "if P then Q," the negation is "P and not Q." Ensure your contradiction arises from this, not from an unrelated error.

Summary

• Direct proof constructs a linear chain of logical deductions from hypothesis to conclusion, ideal for algebraic and identity-based statements.
• Proof by contradiction establishes truth by showing the negation leads to an impossibility, powerful for proving irrationality or uniqueness.
• Mathematical induction proves statements for all natural numbers via a base case and an inductive step, essential for sequences and divisibility.
• Counterexamples are single instances that disprove universal claims, highlighting the importance of testing conjectures rigorously.
• Every proof rests on a logical structure of definitions, axioms, and theorems; clarity in stating hypotheses and justifications is non-negotiable.
• For IB AA Higher Level, mastering these techniques is not just about exam success but about developing the rigorous, analytical thought processes required for advanced mathematics.