Lesson Mathematical Induction

Source code of 'Mathematical Induction'

This Lesson (Mathematical Induction) was created by by richard1234(7193)

: View Source, Show
About richard1234: BS in mathematics w/ computer science. Previous tutoring experience, and I have participated in the USAMO.

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, {{{sum(2^i, i = 0, n) = 2^(n+1) - 1}}}.

The base case n = 1 satisfies, as {{{2^0 + 2^1 = 2^2 - 1}}}. Now, suppose that the identity satisfies for some arbitrary n = k. In other words, if

{{{sum(2^i, i = 0, k) = 2^(k+1) - 1}}},

we want to show that the case n = k + 1 satisfies. If we assume that

{{{sum(2^i, i = 0, k) = 2^(k+1) - 1}}}, and add {{{2^(k+1)}}} to both sides, we obtain

{{{sum(2^i, i = 0, k+1) = 2^(k+1) - 1 + 2^(k+1) = 2(2^(k+1)) - 1 = 2^(k+2) - 1}}}

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 {{{5^n}}} 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 {{{5^n}}} divides {{{sum(a[i]10^i, i=0, n)}}}, then

{{{5^(n+1)}}} divides {{{sum(a[i]10^i, i=0, n+1)}}} where {{{a[i]}}} are odd digits.

Proof: Let {{{sum(a[i]10^i, i=0, n-1) = k5^n}}} for some k (The upper bound is n-1 because a 4 digit number has maximum exponent {{{10^3}}}, etc.). It is clear that {{{sum(a[i]10^i, i=0, n) = sum(a[i]10^i, i=0, n-1) + a[n]10^(n) = k5^n + a[n]10^(n)}}}. Now, we wish to show that {{{k5^n + a[n]10^(n)}}} is divisible by {{{5^(n+1)}}}, which is equivalent to showing that {{{k + a[n]2^n}}} is divisible by 5 (by dividing by {{{5^n}}}.

When {{{a[n]}}}&#8801;{{{k(-3^n)}}} (mod 5) then {{{k + a[n]2^n}}}&#8801;{{{k + k(-6^n)}}}&#8801;0 (mod 5). Since {{{3^n}}} 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 {{{sum (i^3, i = 1, n) = (sum(i, i = 1, n))^2}}}.

2. Prove that the sum of the numbers in row n of Pascal's triangle is equal to {{{2^n}}}.

3. Prove that {{{cos (x) cos (2x) cos (4x)}}}...{{{cos (2^(n-1)x) = (sin (2^(n) x))/((2^n)sin (x))}}} for all n > 1 (Assume sin (x) is not equal to zero).