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 -- if we can get on the ladder somewhere and whenever we are at one rung we have a process that gets us up to the next rung, then we can climb the whole thing!

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 = ⁿ⁽ⁿ⁺¹⁾/₂ (which hardly needs an inductive proof)

or

show 1² + 2² + 3² + ... + n² = ^n(n+1)(2n+1)/₆.

Rather than always saying prove this or that we should be presenting students with situations where they have to make the correct induction hypothesis and then test it. What I propose to look at here is a few less routine problems varying from fairly simple to quite difficult. In each case the choice of the correct induction hypothesis is crucial.

A Fibonacci Example

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.

Factorials

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²? Like n³? Does it grow exponentially? Suppose we try to show it grows faster than say the exponential function 2ⁿ. Let's first try the statement

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ⁿ for n ≥ 4.

Suppose we have checked the truth of this statement for n = 4, ..., k, i.e. we assume P(k): k! > 2^k, up to some k ≥ 4. Is P(k+1) true? We have (k+1)! = (k+1)k! > (k+1)2^k by the induction hypothesis. Now (k+1) > 2 thus (k+1)! > (2)2^k = 2^(k+1) as required, i.e. P(k+1) is true. It follows that n! > 2ⁿ for all n ≥ 4.

As an exercise one might ask the students to consider showing n! > 3ⁿ or 4ⁿ etc. In each case what extra condition on n is required? (It can actually be shown that n! > (n/e)ⁿ for n sufficiently large where e is Euler's constant (e = 2.71828...).)

Making the hypothesis strong enough

Consider a simple inequality -- for a given, fixed x > 0 prove (1+x)ⁿ > nx for n ≥ 1. We'll try an inductive proof. Let's define

P(n): for x > 0, (1+x)ⁿ > nx for n ≥ 1.

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)^k > kx for some k ≥ 1. What about P(k+1)? (1+x)^(k+1) = (1+x)(1+x)^k > (1+x)(kx) by the induction hypothesis. However is (1+x)(kx) > (k+1)x as required? Is (1+x)(kx) = kx² + kx > (k+1)x = kx + x? Only if kx² > x (equivalently, only if kx > 1) but this is not necessarily true; it depends upon the size of k and of x (remember that x is a fixed number). Hence we cannot conclude that the truth of P(k) implies the truth of P(k+1).

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)ⁿ ≥ 1 + nx for n ≥ 1.

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)^k ≥ 1+kx for some k ≥ 1. What about P(k+1)? (1+x)^(k+1) = (1+x)(1+x)^k ≥ (1+x)(1+kx) by the induction hypothesis. Thus (1+x)^(k+1) ≥ 1+(k+1)x+kx² which obviously exceeds 1+(k+1)x as required. Since P(1) is true and the assumption that P(k) is true implies the truth of P(k+1), we have that P(n) is true for all n.

The point illustrated here is extremely important in inductive proofs -- make the hypothesis strong enough!

A Challenge for the advanced students

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ⁿ but we can do better? Try to prove 2nCn < 4ⁿ/SQRT(3n) by induction. The induction step will fail. Does this mean we have a false inequality? Not at all; but what do we need to make it true? Surprisingly we can make a very small change and prove a stronger inequality 2nCn < 4ⁿ/SQRT(3n+1) by induction. The hypotheses is very sensitive in this example and I suspect that finding the correct approach to this problem will be found by only the best students. (It is actually true that the 3 in our inequality can be replaced by pi but this is far too difficult to prove at this level.)