Mathematical Argument Structure

Structure of Mathematical Arguments

A mathematical argument is a sequence of logically connected statements leading from known truths to a conclusion.

Building Blocks

Logical Implications

• $P \Rightarrow Q$: if $P$ then $Q$
• Contrapositive: $\neg Q \Rightarrow \neg P$ (equivalent to $P \Rightarrow Q$)
• Converse: $Q \Rightarrow P$ (NOT equivalent in general)
• $P \Leftrightarrow Q$: $P$ iff $Q$ (both $P \Rightarrow Q$ and $Q \Rightarrow P$)

Proof by Contradiction

1. Assume $\neg P$.
2. Derive a known falsehood.
3. Conclude $P$ is true.

Example: Prove $\sqrt{2}$ is irrational.

Assume $\sqrt{2} = p/q$ in lowest terms. Then $p^2 = 2q^2$, so $p$ is even; write $p = 2m$. Then $4m^2 = 2q^2 \Rightarrow q^2 = 2m^2$, so $q$ is also even. This contradicts $p/q$ being in lowest terms. $\square$

Proof by Contrapositive

Example: Prove: if $n^2$ is odd then $n$ is odd.

Contrapositive: if $n$ is even then $n^2$ is even. Let $n = 2k$; then $n^2 = 4k^2 = 2(2k^2)$, which is even. $\square$

Mathematical Induction

Standard induction: Base case + assuming $P(k)$ to prove $P(k+1)$.

Strong induction: Assume $P(1), \ldots, P(k)$ all hold; prove $P(k+1)$. Useful when $P(k+1)$ depends on earlier cases.

Example (strong induction): Every integer $n \geq 2$ is prime or a product of primes.

Base case: $n=2$ is prime. True.

Inductive step: Assume every \$2 \leq m \leq k$ is prime or a product of primes. If $k+1$ is prime, done. Otherwise $k+1 = ab$ with \$2 \leq a, b \leq k$, and by hypothesis both $a, b$ factor into primes, so $k+1$ does too. $\square$

Example (inequality): Prove $2^n > n$ for all $n \geq 1$.

Base case: $2^1 = 2 > 1$. True.

Inductive step: Assume $2^k > k$. Then $2^{k+1} = 2 \cdot 2^k > 2k \geq k+1$ (since $k \geq 1$). $\square$

Disproving Universal Statements

To disprove $\forall x,\, P(x)$, provide one counterexample.

Example: Disprove “all primes are odd.” Counterexample: $2$ is prime and even.

EXAM TIP: Always write “Base case” and “Inductive step” as headings in your proof. Many marks are lost for missing structure.

COMMON MISTAKE: In the inductive step, stating “let $n = k+1$” without first explicitly writing the inductive hypothesis $P(k)$.

REMEMBER: The contrapositive is logically equivalent; the converse is not. Proving the converse does not prove the original statement.

VCAA FOCUS: VCAA frequently asks for proofs by induction on divisibility (\$3 | n^3 - n$), inequalities, and closed-form summation formulas. Know all three types.