PDF version of this article

Appendix: Proof by induction

Proof that the sum of all integers less than or equal to $k$ is ${k\times(k+1)}\over 2$.

1. Proof for 0: ${{0\times(0+1)}\over2}= 0$.
2. Proof that if it is true for $n$ it must be true for $n+1$.
   1. Assume we have for any $n$ that that the sum of all integers less than $n$ is ${n\times(n+1)}\over 2$.
   2. Then the sum of all integers less than $n+1$ must be $n+1 + {{n\times(n+1)}\over 2}$.
   3. Put the $n+1$ in the numerator of the fraction producing ${{2 \times (n+1) +n \times (n+1)}\over{2}}$.
   4. Simplify using the common factor $n+1$ to get ${{(n+2) \times (n+1)}\over 2}$.
   5. Substituting $k$ for $n+1$ in the above equation yields ${k\times(k+1)}\over 2$.
3. This completes the proof that if the equation is true for $n$ it must be true for $n+1$ and that completes the proof by induction.