Proof by induction - but not the electrical sort...

by Prof Herbert Fleischner

Sharai didn't like her older brother because he was roughly 15 months older then she was. So he was always one year ahead of her in school. ``I'm in Grade 4, and he is in Grade 5'', she reasoned, ``so what? In one year I'll also be in Grade 5!'' - ``And then I'll be in Grade 6,'' he said calmly, but the tone of his voice contained a mixture of irony and arrogance. `` And when I'll be in Grade 6, you'll be in Grade 7,'' she said, and she sounded slightly discouraged. ``And when I'll be in Form 4, he'll be in Form 5''- this time she kept her thoughts to herself, as she had no desire to hear his ironic replies. ``Okay, okay, let it be - you'll always be one year ahead of me'', she said, in a matter-of-fact tone. She was ready to face this fact.

Now, believe it or not, a proof by induction works along the same lines. Suppose you have a mathematical formula (an inequality, or an equation, etc.) defined in terms of the members n of N, the set of positive integers. Call the formula A_n. Suppose you know that A₁ (the statement that A_n holds for n = 1) is true, and suppose that you can prove that ``if, for some integer k,  A<sub>k</sub> is true, then  A<sub>k+1</sub> is also true''. Then you may conclude that ``A_n holds for all n Î N'' is a true statement.

``Sounds rather abstract, this explanation!'' Tawanda, the maths student (who likes to play the maths lecturer), had glanced over my shoulder at what I had scribbled on the paper. ``How about a concrete example?'' Well, here is one:

Consider the inequality n! < 2ⁿ.

It is true for n = 0, 1, 2, 3; so one could suspect it is true for all n Î N. This guess is wrong, since, for n = 4, 4! = 24 > 16 = 2⁴  holds. And what happens for larger n, that is, n > 4? Perhaps the inequality to prove is n! > 2ⁿ,  for all n ³ 4. Let's see... Suppose we have shown that, for n equal to some k ³ 4, k! > 2^k holds (we call this the induction hypothesis), and let's consider the inequality for n = k+1. Then we can write (and this we call the induction step):

because:

To have a little exercise along the way, try to prove that, if you are given a fixed non-negative integer r, then

where n₀ should be determined by you (take logs and use trial-and-error). For r = 0 we have seen that n₀ = 4 will do. You will need higher values of n₀ for higher values of r. Likewise, try to prove that, if you are given a positive number a, then

Take another example. We want to show that

Tawanda had come back, glanced over and said: ``The initial step is trivial, so you proceed to the induction step right away.'' I allowed him to distract me and said to myself:

Okay, let's suppose we have proved -2k < -3k  for  some  k Î N,  k ³ 1. Then, by this inductive hypothesis, -2(k+1) = -2k-2 < -3k-2 and since we are dealing with integers it follows that -2(k+1) £ -3k-3. But, if equality held here, you can easily check that k = -1, contrary to our hypothesis about k being positive. Hence we have:

Just wait a minute! Is -2 < -3? Is -4 < -6, -6 < -9 etc? By no means! So, where is the problem? We can be sure that there's nothing wrong with the induction step. Phrased more generally, we have presented a correct proof of the statement ``If A<sub>k</sub> is true, then A<sub>k+1</sub> is true'', where A<sub>n</sub> is the formula -2n < -3n. The problem rests with the little word ``if'' and our negligence in not bothering to prove the formula for k = 1. We would have found no proof of -2 < -3, since it is a false inequality to begin with. It is like saying:

This is definitely a true statement - the only problem being that a lion cannot fly. We have learnt an important lesson: so trivial as the initial step of a proof by mathematical induction may appear, one cannot skip it. In fact, there are many proofs of mathematical statements by induction, where the hard part of the proof is the initial step, whereas the induction step is comparatively easy; in other instances it is the other way around.

The examples I have given so far have been numerical, but this does not have to be the case. Consider the following statement, which we can call A_n.

If n circles are drawn in the plane then the regions of the plane thus formed can be coloured with two colours so that no two neighbouring regions have the same colour.

Notice that we make no claims about the radii of the circles, apart possibly from the fact that they are all finite. Also we should clarify the point that two regions that only meet at a point are not considered to be neighbouring.

Clearly A₁ is true - just colour the regions inside and outside the circle with different colours as shown. Now assume A_k is true. Given, k+1 circles in the plane, throw out one circle, call it C, and (since A_k is true) colour with two colours the regions produced by the remaining k circles. Now chuck C back in. Now some of the regions will be split in two, others will be unaffected. Leave the colours of all regions `outside' C unchanged and switch the colours of all regions `inside' C. This procedure produces a 2-colouring of the plane with k+1 circles, so A_k+1 is true. Now we can conclude by induction that A_n is true for all positive integers n.

Why not try a couple more problems?

Exercises.

1. Show that 7ⁿ-1 is a multiple of 6, for any positive integer n .
2. Show that for any positive integer n, the sum of the numbers in the n^th row of Pascal's triangle is 2ⁿ. For instance the sum of the numbers in the fifth row is 1+5+10+10+5+1 = 32 = 2⁵.

More will follow in the next issue of . In the meantime, have a nice day, or evening, have nice dreams - but don't hibernate, although the cold season draws nearer and nearer...