# Proof by Induction example

Here is an example of proof by induction.

Proposition: $1+2+3+...+x = \frac{x(x+1)}{2}$

Proof: in order to prove this we will follow the instructions shown in the previous page. First let $x = 1$ for our base case. $P(1) = 1 = \frac{1(1+1)}{2}$. Therefore our base case is true.

Now for our inductive hypothesis. We now assume that $1+2+3+...+x = \frac{x(x+1)}{2}$ is true for $x=n$ and now we prove for the case $x= n+1$.

$1 + 2 + 3 + ... + n + n + 1$ $=$ $( 1 + 2 + 3 + ... + n ) + n + 1$

$= (\frac{n(n+1)}{2})+n+1$

We can collapse that part because of our inductive hypothesis.

$= \frac{n(n+1)}{2}+\frac{2(n+1)}{2}$

$= \frac{n^2+3n+2)}{2}$

$= \frac{(n+1)((n+1)+1)}{2}$

This proves that $1+2+3+...+x = \frac{x(x+1)}{2}$.

Induction proofs are used to prove closed forms and greedy algorithms which are both important components in the design and analysis of algorithms. Generally speaking proof of induction is used for statements of facts more often then for statements such as “if P then Q” or “P if and only if Q”.

Filed under : Mathematics