Proof Techniques

A proof is a watertight argument that a statement must be true. Three staple techniques:

• Direct proof: assume the hypothesis and reason straight to the conclusion.
• Proof by contradiction: assume the statement is false, then derive an impossibility — so it must be true after all.
• Mathematical induction: prove a statement for all $n$ using a base case plus a step that carries truth from $n$ to $n+1$.

Induction has two parts:

1. Base case: show it holds for the first value (say $n=1$).
2. Inductive step: assume it holds for $n$, then prove it for $n+1$.

Worked example. The sum $1+2+\cdots+n = \dfrac{n(n+1)}{2}$. For $n=10$: $\dfrac{10\cdot 11}{2} = 55$, matching a direct count. Induction proves the formula for every $n$ at once, without checking them one by one.