Proof by induction

A proof by induction is useful when given some statement P(n) which you want to prove is true for all n.

There are two stages in a proof by induction. The first step is to prove that P(1) is true; this is called the basis step. The second step is to prove that P(n+1) is true; this is called the inductive step.

Proof of the binomial theorem (still in progress)

A binomial coefficient – \binom{n}{k} – (read "n choose k") is defined as $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$.

The binomial theorem states that

(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k

Basis step: $$ \sum_{k=0}^1 \binom{1}{k} x^{1-k} y^k = \binom{1}{0} xy^0 + \binom{1}{1} x^0y = (x+y)^1 $$

Inductive step:

\begin{align} (x+y)^{n+1} & = (x+y)(x+y)^n \\ & = (x+y)\sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^{k} \\ & = \sum_{k=0}^n [\binom{n}{k}x(x^{n-k}y^{k}) + \binom{n}{k}y(x^{n-k}y^{k})] \end{align}

Proof by grouping

Proof by exploiting symmetry

Proof by brute force

Proof by comparison

Proof by contradiction

Proof that \sqrt{2} is irrational

A rational number can be written as the quotient of two numbers \frac{a}{b}. If \sqrt{2} is rational then the statement

\sqrt{2} = \frac{a}{b}

should be true.

Here \frac{a}{b} is defined to be in its simplest terms (it has been cancelled down as far as is possible).

\begin{align} 2 & = (\frac{a}{b})^2 \\ & = (\frac{a^2}{b^2}) \\ \end{align}

Proof by exhaustion

Proof by counterexample

Proof by generalising

Proof through the pigeon-hole principle

Proof by adding zero or multiplying by one