Mathematical Patterns, Induction, and Mathematical Induction

An important part of a mathematician’s work is the perception of patterns involving numbers. Occasionally, a mathematician encounters some equations and perceives the presence of a general regularity in them. For example, look at the following simple identities: 4^1-1=3*1, 4^2-1=3*5, 4^3-1=3*21, 4^4-1=3*85, etc. Anyone can recognize the general pattern: multiply 4 with itself as many times as you like and subtract 1 from it, you will always get a multiple of 3. Similarly, 1+2+3=3*4/2, 1+2+3+4=4*5/2, etc. Here again you can perceive a pattern: add all the natural numbers from 1 to any number you like, the result you get is always the same as the half of its product by its successor. Mathematicians have got a certain way of writing such general patterns. The first one is written as “4*n-1 is always divisible by 3”, and the second one as 1+2+3+… +n=n(n+1)/2. Similarly the pattern in the identities 1+3+5=3^2, 1+3+5+7=4^2, 1+3+5+7+9=5^2, etc. is written as 1+3+5+… +O_n=n^2, O_n here means the nth odd number. Mathematicians perceive patterns involving numbers and write them in the way described above. They have discovered a whole range of interesting patterns and a mere glance over the variety is enough to fill one with wonder and awe. Let us have a look at some of them.

A set with 3 elements has 2^3=8 possible subsets, a set with 4 elements has 2^4=16 subsets,… , a set with n elements has 2^n subsets. 2^3-2=6*1, 3^3-3=6*4, 4^3-4=6*10,… , n^3-n is a multiple of 6. Let us leave the intermediate steps and write the final expressions of the patterns from now on. x^3-7x+3 is a multiple of 3. 7^n-5^n is a multiple of 2. a^n-b^n is a multiple of a-b, a and b are different natural numbers. nC1+nC2+… +nCn=2n. The list is virtually endless.

One should not be too hasty in drawing the conclusion that the pattern he perceives indeed carries over to all natural numbers. Let us take the classic example of the expression n^2+n+41. It was widely believed years ago that this expression always gives you a prime number no matter what natural number you put in it in the place of n. 1^2+1+41=43, a prime number; 2^2+2+41=47, a prime number; 3^3+3+41=53, again a prime number,… , 39^2+39+41=1601. One really begins to feel that this pattern should carry over to all natural numbers; confirming something 39 times raises one’s confidence almost to certainty. But Euler, one of the most prolific mathematicians of history, pointed out in 1772 that this was not true in general. 40^2+40+41=40(40+1)+41=40*41+41=41(40+1)=41*41, a composite number instead of a prime! Similarly, 41^2+41+41=41(41+1+1), again a composite number. So, what do we conclude? We come to realize that a repeated confirmation of a certain pattern does not necessarily imply that the pattern in question will carry over to all numbers. One begins to feel the need of something else that should serve as a test for the validity of statements involving number patterns.

Perceiving a pattern and generalizing it to all possible situations is called induction. A vast amount of what we call knowledge depends upon the process of induction. How do we know, for example, that if you lose hold of something, it will fall on earth instead of flying away? Induction provides the answer; since the time we were born, we have seen this happen hundreds of times, and this repeated observation has given us confidence that it will always happen whenever someone will lose hold of anything. Are you doubtful? Lose hold of something and see what happens! Fire burns, poison kills, trees give us fruit, sun shines to give us light and rises daily, etc. are a few of the things we believe because of induction. Not only in physics and everyday life, this is applicable in the case of number patterns also. We make some observations, perceive a pattern, and begin to feel that the thing we observed in the case of certain selected numbers, should be true for all numbers that are there. It is one of the strongest tools of a working mathematician. But… there is something more stronger which is not available in the case of our everyday experiences: mathematicians have got the Method of Mathematical Induction.

Mathematical Induction is a tool that is used to supplement the lack that is inherent in the process of induction, so vividly exposed by the observation made by Euler in 1772. His observation clearly shows that we need some other method to confirm whether the pattern we perceive carries over to all numbers or not, and that whether the final statement, involving n, we have written is true for all numbers or not. This is accomplished by the use of the Method of Mathematical Induction. It serves as a test of the validity of a general statement about natural numbers. If a claim or a statement passes this test, it is certainly true for all numbers that can be put for n in the final expression. Keep in mind that not all of the expressions concern all natural numbers. “4n-1 is a multiple of 3” is true for all natural numbers, but n! > n^2 is true for all natural numbers that are greater than 3, instead of being true for all natural numbers. So, while talking about patterns, we should keep an eye over its range of applicability. For the sake of simplicity, we will be concerned in this article with only those patterns that involve all natural numbers. Now let us take a look at the steps of the method.

The method of mathematical induction consists only of two steps. The first step is to see whether the statement is true for the first natural number 1 or not. The second is a bit intricate; we check the following: if the claim is true for a certain number, is it true for the next one as well? That is, we consider the successors of those numbers for which the pattern is true and check whether the claim is true for all the successors or not. When a mathematician confirms these two things, he writes his findings as a proof consisting of two steps: First he proves that the claim is true for 1, and secondly, he goes on to prove that if the claim is true for any number, it must be true for its successor too. From these two proofs the mathematical community begins to accept the general validity of the claim made. The question that arises here is “Why”. How do we know that a statement which passes these two steps must be true in general? Well, there are a number of ways of “seeing” this.

Imagine a long row of tiles standing so close to each other that if anyone of them falls, its neighbor will also fall. Now, if someone lets the first one fall, we can see clearly that all the tiles will fall. Similar is the case with numbers. If a statement is true for 1 and is true for the successor of every number for which it is true, it must be true for all numbers. There is another way too: We know that the statement is true for 1, so from step two we know that it must be true for its successor, which is 2 – after all, we have proved in step two that the claim is true for the successors of all those numbers for which it is true, hence it must be true for the successor of 1 as well, which is 2. Now that it is true for 2, from step two, it must be true for 3 as well; and for 4, and for 5,… , and for 1000, and for 1000 000,… ,… and… Well, for all natural numbers.

There is a roundabout way of looking at it too, and, personally speaking, I find it more interesting. It depends upon a very simple fact about natural numbers: If you choose certain natural numbers, no matter how many of them, there must be a smallest one among them. For example, if I choose the admission numbers of the students of my class, everyone can see that there must be a student with the smallest admission number. Very simple. This is called the Well Ordering Property of Natural Numbers. Does this simple fact deserve a separate title? Yes, and you will see “why” in a short while.

Well Ordering Property of Natural Numbers implies that the Method of Mathematical Induction is indeed a valid test of the truth of general statements involving numbers. Suppose, on the contrary, that there is a statement that has passed this test and still is false for some natural numbers. If any such numbers exist, there must be a smallest such number. Call it s. It cannot be 1 by virtue of the step one. So it must have a predecessor; call it p. Since s is the smallest of those for which the statement is false, it must be true for p, and so, by step two, it must be true for its successor s as well! This is impossible; so the existence of those numbers for which the claim is false is impossible – their existence will imply the existence of a smallest one among them, whose existence is impossible, since for it the claim should be both true and false at the same time. A very clever argument, indeed.

The idea of this method is a truly ingenious one and one cannot help admiring the talent of the person who introduced it. I would like to conclude this article by listing some interesting applications of this method. The details of these applications can be found in Rosen’s book Discrete Mathematics and its Applications. It can be applied to postage problems. For example, we can prove using this method that any amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps. Similarly, we can prove that any postage of.8 cents or more can be formed using just 3-cent and 5-cent stamps. It can be applied to games. For example, we can prove that in a certain two-player game the second player can guarantee a win. It can be applied to prove certain facts about round-robin tournaments. It is extensively used in Number Theory and many other branches of mathematics. It can be applied to prove that certain floors can be tiled using certain tiles… The variety of applications is endless.

Article Source: http://EzineArticles.com/9395771