Induction
Mathematical Induction Example 1 --- Sum of Evens
Problem: For any natural number n ,
2 + 4 + ... + 2n = n( n + 1 ).
Proof:
Basis Step:
If n = 0,
then LHS = 0, and RHS = 0 * (0 + 1) = 0 .
Hence LHS = RHS.
Induction: Assume that for an arbitrary natural number n,
0 + 2 + ... + 2n
= n( n + 1 ) . --------
Induction Hypothesis
To prove this for n+1, first try to express LHS for
n+1 in terms of LHS
for n, and somehow use the induction hypothesis.
Here let us try
LHS for n + 1 =
0 + 2 + ... + 2n + 2(n + 1) =
(0 + 2 + ... + 2n) + 2(n + 1) .
Using the induction hypothesis, the last expression can be rewritten as
n( n + 1 ) + 2(n + 1) .
Factoring (n + 1) out, we get
(n + 1)(n + 2) ,
which is equal to the RHS for n+1.
Thus LHS = RHS for n+1.
End of Proof.