Geometry and Induction Tidbit (09/19/2003)
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451
Email: firstname.lastname@example.org (for additions, suggestions, and corrections)
Very often in mathematics one is trying to verify (prove) that a certain statement is true, but the statement involves a parameter and, therefore, asserts infinitely many statements. How can one verify infinitely many statements in only a finite amount of time?
First a few examples:
1 + 3 + 5 + .... + (2n - 1) = n2
This assertion states in words that if one add up the first n odd numbers one obtains n2. Note that this statement is being asserted for every choice of n where n is a positive integer.
In particular, when n is 4, it is being asserted that 1 + 3 + 5 +7 = 42 = 16, which is, in fact, the case.
Suppose S is a grid of squares (that is, a chessboard), with 2n squares on each side, but with exactly one square of the grid removed. We conclude that S can be covered (tiled) with the polyomino below:
This polyomino is known as the L-tromino, since it is "L" shaped and has three squares.
It seems remarkable that no matter what square is removed from a chessboard that has a power of two squares on each side, that such a tiling is possible.
Again this assertion is being claimed for infinitely many situations and so how does one verify such an assertion?
One important tool is that of mathematical induction.
Intuitively, the idea behind mathematical induction is that if one has a statement which one hopes is true for all integers from some integer on, one can produce a proof as follows:
Verify the statement for the "start" value. Now, assuming that one knows the statement is true for any integer value, verify it for the next value.
To make an analogy, to climb a ladder requires one be able to get to the starting rung, and given that one is on any particular rung, one can climb to the next one. If both of these things are true then one can climb the whole ladder.
The formal statement of mathematical induction is:
Given a collection of statements S(n) where for each value of n we get an a statement which we would like to verify is true.
1. If S(1) is true
2. If the truth of S(k) implies the truth of S(k+1)
S(n) is true for every value of n.
Note that if we can prove the geometric theorem above, we can also prove a result in number theory as well. Since the polyomino shape has three squares, if it is to tile our chessboard having a side length a power of 2 with one square removed the number of squares of the modified chessboard must be divisible by 3. Thus: 3|(22n -1).
An interesting question is if a chessboard with 1 square removed has a covering by L-trominoes. The easiest special case to consider is whether or not the 5 x 5 chessboard with 1 square removed can be covered by L-trominoes. The answer is yes for some choices of where the square is removed but no for others! (You should verify this for yourself.)
The inductive proof of the Theorem 2 is very attractive. Can you find it for yourself?
Another lovely geometric result that can be solved using mathematical induction is to verify that number of regions that the plane is divided into using n straight lines, no two of which are parallel and no three of which pass through a single point. The key to studying this question is to first consider the question concerning how many sections a line is divided into when n points on the line are selected. After answering the question about lines, one can look at the question concerning how many regions planes divide 3-dimensional space into. After that you can take on 4-dimensions and higher!
Here are some interesting and informative geometric problems that can be solved using mathematical induction.
1. Any tree has one more vertex than edge.
2. Any polyomino has even perimeter.
3. Find a formula for the number of regions that n lines in the plane none of which are parallel and where no three lines pass through a single point. Prove that your formula is correct using mathematical induction.
Chu, I-Ping and R. Johnsonbaugh, Tiling deficient boards with trominoes, Mathematics Magazine, 59 (1986) 34-40.
Fredrickson, G., Dissections: Plane and Fancy, Cambridge U. Press, New York, 1997.
Golomb, S. Polyominoes, second edition, Princeton U. Press, Princeton, 1994.
Martin, G., Polyominoes, Mathematical Association of America, Washington, 1991.
Thanks to Arthur Benjamin for the first reference.
Back to list of tidbits