Lesson Mathematical Induction

In the following lessons we will learn some basic proof techniques beyond the two-column proof (such as induction, contradiction, bijection, etc.) and use these to solve advanced problems.
My personal opinion with the two-column proof is that it can be very difficult to express a lengthy proof that might require unusual theorems or logic. For example, if I was solving a geometry problem and mapped all the points to points in the complex plane -- how would I denote that in a two-column proof? This is why I refrain from using two-column proofs when I solve proof questions, and instead write out the proofs in essay style.
==Induction==
Induction works well when you want to prove some equation or identity satisfies for all numbers. The basic idea of induction is to show that a base case (for example, n = 1) satisfies. Then, assume that the identity holds for some arbitrary integer k and try to show that k+1 must satisfy. If it does, then it works for all numbers.
Let's say that in a certain city in a certain universe, if it rains one day, it will always rain the following day. By a simple induction argument, if it rains today, then it will rain tomorrow, and the day after that, etc.
We'll start with a simple induction problem.

Example 1:
Prove that for all n > 0, .
The base case n = 1 satisfies, as . Now, suppose that the identity satisfies for some arbitrary n = k. In other words, if
,
we want to show that the case n = k + 1 satisfies. If we assume that
, and add to both sides, we obtain

This is the same result we would have obtained if we plugged in n = k+1. Hence the induction works, and we are done.

The next example is a more challenging problem that also uses mathematical induction.

Example 2:
Prove that for every positive integer n there exists an n-digit number divisible by whose digits are all odd (USAMO, 2003).
Solution:
We can check and see that the base cases n = 1, 2, 3, 4 work (producing 5, 75, 375, 9375). In general, we will prove that, using induction:
If divides , then
divides where are odd digits.
Proof: Let for some k (The upper bound is n-1 because a 4 digit number has maximum exponent , etc.). It is clear that . Now, we wish to show that is divisible by , which is equivalent to showing that is divisible by 5 (by dividing by .
When ≡ (mod 5) then ≡≡0 (mod 5). Since covers all residues modulo 5, we can easily show that there is an odd digit that satisfies the identity, since the odd digits (1, 3, 5, 7, 9) also cover all residues modulo 5. Hence the induction is complete.



Here are a few induction problems for you to try on your own:
1. For any positive integer n, show that .
2. Prove that the sum of the numbers in row n of Pascal's triangle is equal to .
3. Prove that ... for all n > 1 (Assume sin (x) is not equal to zero).