Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers.
To proof the formula A(n) for all natural numbers n ≥ m, two steps are necessary:
1. the base case, to show that A(m) is true.
2. the inductive step, show that if A(n) holds, then also A(n+1) for n ≥ m holds.
Usually applies m=0 or m=1. In special cases can be m>1.
Example: The proof of 1+2+3+…+n.
- 2n³ + 3n² + n is divisible by 6
- The n-th derivative
- (n^p – n) is divisible by p
- The power set of a set with n elements contains 2^n elements
- Recursive Sequence
- Bernoulli’s inequality
- Just another inequality
- n and sqrt(n)
- n! > 2^n
- 2^n > n^3
- A sum
- A product
- Every integer n >= 2 is a product of prime numbers