Mathematical Induction — Formula Sheet

If P(1) is true and P(k) ⇒ P(k+1), then P(n) is true for all n ∈ ℕ

Sum of first n natural numbers: ∑n = n(n+1)/2

Sum of squares: ∑n² = n(n+1)(2n+1)/6

Sum of cubes: ∑n³ = [n(n+1)/2]²

Sum of first n odd numbers: n²

Divisibility: xⁿ − yⁿ is divisible by x − y

1/(1·4) + 1/(4·7) + ... + 1/[(3n−2)(3n+1)] = n/(3n+1)

(1+x)ⁿ ≥ 1 + nx for x > −1

If a statement p(n) is true for n = 1, and if the truth of p(k) implies the truth of p(k+1), then the statement is true for all natural numbers n.