After reading this and this I realized something is really, really wrong about mathematical concepts out there. Proof by induction is a really, really simple yet powerful proof method. In this post, I will talk about induction for natural numbers.

Induction is based on two steps, usually called **basis** and **inductive step**. I will proof that 1+2+…+n=n(n+1)/2 for all natural numbers using induction.

**Basis** or **base case** consists on proving the predicate for an initial value, usually a small one. In the example 1=1*2/2=1.
**Inductive step** consists on supposing the *if* the predicate holds for *n*, then it also holds for n+1. In the example:

1+2+…+n+(n+1)=(n+1)+n(n+1)/2 because we supposed that predicate held for *n*. We need to prove that this expression is equivalent to (n+1)(n+2)/2. Indeed,

(n+1)+n(n+1)/2=(n+1)(1+n/2)=(n+1)((2+n)/2)=(n+1)(2+n)/2

so the predicate has been proofed for all natural numbers.

**Why does induction work?**

Think of any natural number, as big as you want. Got it? We know that the predicate holds for 1, and that if the predicate holds for a number it holds for its successor. So it holds for 2, and for 3 and so on until it reach your number.

**Other types of induction.**

There are several types of inductions. Two of these types are **structural induction** and **complete induction**.

photo credit: hartboy

## Author: Serabe

Mathematician, and Ruby and JavaScript programmer.
Sometimes I speak at conferences and local meetups.
View all posts by Serabe