## Mathematical Induction
## Penelope Nom
In Math B30 we consider mathematical induction, a concept that goes back at
least to the time of Blaise Pascal (1623 - 1662) when he was developing his
"Triangle". The basic idea is quite simple and is often thought of a process
akin to climbing an infinite ladder -- A bit more formally, if we have a proposition P that is true for some integer m, i.e. P(m) is true, and if for each integer k ≥ m the truth of P(k+1) follows from the truth of P(k), then P(n) is true for all integers k ≥ n. I'm sure that we're all more than familiar and probably tired of the standard problems on induction such as:
show 1 + 2 + 3 + ... + n = or
show 1
Rather than always saying prove this or that we should be presenting
students with situations where
Take the well known Fibonacci numbers, a sequence 1, 1, 2, 3, 5, 8, ... where the nth such number F(n), starting at the third, is defined to be the sum of the previous two, i.e. F(n+2) = F(n+1) + F(n), n ≥ 1. If we look at sums of these terms we see: 1 = 1 1 + 1 = 2 1 + 1 + 2 = 4 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 + 5 = 12 etc., generating a new sequence 1, 2, 4, 7, 12, ... . What are these numbers? That is, what is F(1) + F(2) + ... + F(n)? Let the students guess it. It shouldn't take long for some student to hypothesize that this sum may be F(n+2) - 1. Let's test this proposition i.e. P(n): F(1) + F(2) + ... + F(n) = F(n+2) - 1 for n ≥ 1. Clearly P(1) is a true. Suppose we have checked the truth of the statement for n = 1, 2, ... , k -- this is our induction hypothesis. What about P(k+1)? We have, using the induction hypothesis, F(1) + F(2) + ... + F(k) + F(k+1) = [F(k+2)-1] + F(k+1) but, by the definition of the Fibonacci numbers, F(k+2) + F(k+1) = F(k+3) hence we have, as required, that F(1) + F(2) + ... + F(k) + F(k+1) = F(k+3)-1. Thus, since P(1) is true and the assumption that P(k) is true implies the truth of P(k+1), we have that the truth of P(1) implies P(2) is true, in turn the truth of P(2) implies P(3) is true, in turn the truth of P(3) implies ..., i.e. P(n) is true for all n.
Often in mathematics and computing science we run into n factorial: n! (the
product n(n-1)(n-2)...(3)(2)(1)). It is very important to understand the growth
of this function. The growth starts simply enough 1, 2, 6, 24, 120, 720, 5040,
... but very soon these numbers are astronomical in size -- for example 20! is
of the order of 10 to the 18th power. Does n! grow like n
P(n): n! > 2 Well, our first observation is that P(1) is false. Should we stop? How about P(2)? Also false. Should we stop? P(3) is false too! However we see that P(4) is true. Thus we shall attempt to prove that
P(n): n! > 2
Suppose we have checked the truth of this statement for n = 4, ..., k, i.e.
we assume P(k): k! > 2
As an exercise one might ask the students to consider showing n! > 3
Consider a simple inequality -- for a given, fixed x > 0 prove (1+x)
P(n): for x > 0, (1+x)
P(1) is true as 1+x > x. Assume we have checked P(n) for n = 1, 2, ...,
k, in particular P(k) is true, i.e. (1+x) Does the above mean the inequality is not true? No! One can show it is indeed true in many ways -- if you know the Binomial Theorem for example, but that would be a much too complicated solution. So what has gone wrong with our induction? The problem lies in the induction hypothesis actually not being strong enough. Oddly enough we can prove a stronger inequality by induction. Let's see.
Define P(n): for x > 0, (1+x)
Clearly this is a stronger inequality than we asked for earlier so that its
truth implies what we asked for earlier. P(1) is true as 1+x ≥ 1+x. Assume
we have checked P(n) for n = 1, 2, ..., k, and in particular P(k) is true, i.e.
(1+x)
The point illustrated here is extremely important in inductive proofs --
Recall from earlier studies of permutations and combinations that
nCr = n!/(r!(n-r)!) How big is 2nCn, the number of ways to choose n of 2n
distinct objects? It is easy to show that 2nCn < 4
To return to the previous page use your browser's back button. |