|
Mathematical induction is used to prove something true for all n, n being an integer. If it is known that A(n) is true, and also that A(n) implies A(n+1), then A(n+1) is true, and this implies A(n+2) is true, etc., thus proving that A(k) is true for all k>=n.
For example, consider the sum 1+2+3+...+n. Claim A(n)=n(n+1)/2. So 1+...+n=n(n+1)/2. Add n+1 to both sides to reach:
1+...+(n+1) = n(n+1)/2 + (n+1)
1+...+(n+1) = (n+1)[n/2 + 1]
1+...+(n+1) = (n+1)(n+2)/2 = A(n+1)
Hence A(n)=n(n+1)/2 implies A(n+1)=(n+1)(n+2)/2 both by variable substitution and algebraically. Therefore A(1)=1, A(2)=3, A(3)=6, and so on.
|