Mathematical induction is used to prove a statement P for all n∈ℕ. It goes like this:

- Prove the statement P for n=1
- k→k+1:
**assuming P(k)**, show that P(k+1) also holds

Sometimes it can be helpful to do a complete induction which changes step 2 a bit: assume P(2..k) is true and show that P(k+1) also holds. But, note that the two variants are equivalent.

To show that 1+2+...+n ≤ n^2:

n=1: 1 ≤ 1^2=1 is true k→k+1: assuming 1+..+k ≤ k^2: 1+..+k+(k+1) ≤ (k+1)^2 ⇔ 1+..+k+(k+1) ≤ k^2+2k+1 (1st binomial) ⇔ k+1 ≤ 2k+1 (induction hypothesis) ⇒ the statement holds for all n∈ℕ