# 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

*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*:

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

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).