# Proof¶

## 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 comparison¶

### 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}