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

1. Prove the statement P for n=1
2. 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∈ℕ