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