Induction/Line configurations/Introduction/Section

From Wikiversity
Jump to navigation Jump to search

The natural numbers have the characteristic property that one can reach every natural number starting from by just counting step by step (by taking the successor). Therefore, mathematical statements which refer to the natural numbers can be proven with the proof principle complete induction. The following example is supposed to explain this scheme of argumentation.

We consider in the plane a configuration of lines, and we ask ourselves what the maximal number of intersection points of such a configuration might be. It does not make a difference whether we think of the plane as (a Cartesian plane with real coordinates), or simple of a plane in the sense of elementary geometry. The only important thing is that two lines either intersect in exactly one point, or they are parallel. If is small, it is easy to find the answer.

But as soon an gets a bit larger (?), the answer is not so clear anymore, as it gets very difficult to imagine the situation in a precise way. The imagination becomes just a rough idea of many lines with many intersection points, but it is not possible to draw any precise conclusion from this. A useful approach to understand the problem is to understand what may happen when we add a new line to a given line configuration, when instead of lines we consider lines. Suppose that, for some reason, we know what the maximal number of intersection points for lines is, maybe we have even a formula for this. If we then can understand how many new intersection points we may get by adding a new line, then we know the maximal number of intersection points for lines.

Now, this passage is indeed easy to understand. The new line can at most intersect every old line in exactly one point, therefore at most new intersection points may occur. If we choose the new line in such a way that it is not parallel to any of the given lines (what is possible since there are infinitely many directions) and such that the intersection points of the new line do not coincide with old intersection points (what is possible by possibly taking a line parallel to the direction found), we get exactly new intersection points. Hence, we deduce the (preliminary) formula


so just the sum of the first natural numbers.

In the preceding example we are dealing with a sum where the number of summands is variable. For such a situation, the sum sign(or sigma sign) is appropriate. For given real numbers we define

In general, the depend in some way (say, by a formula) on , in the example we just have , but it could also be something like or . The -th summand in the sum is , the number is called the index of the summand. Accordingly, the product sign is defined by

We would like to find an easy formula for the sum of the first natural numbers, which equals the maximal number of intersection points of a configuration of lines. We claim that

holds. For small numbers , this is easy to check just by computing the left-hand and the right-hand side. To prove the identity in general, we try to understand what happens on the left and on the right, if we increase to , like we have added in example another line to a line configuration. On the left-hand side, we just have the additional summand . On the right-hand side, we go from to . If we can show that the difference between these fractions is , then the right-hand side behaves like the left-hand side. Then we can conclude: the identity holds for small , say for . By comparing the differences, it also holds for the next , so it holds for , then again for the next and so on. Since this argument always works, and since one arrives at every natural number by taking the successor again and again, the formula holds for every natural number.

A visualisation of the induction principle. If the stones are close enough to each other and the first stone falls, then all stones will fall.
A visualisation of the induction principle. If the stones are close enough to each other and the first stone falls, then all stones will fall.

The following statement gives the foundation for the principle of complete induction.

Suppose that for every natural number a statement is given. Suppose further that the following conditions are fulfilled.

  1. is true.
  2. For all we have: if holds, then also holds.
Then holds for all .

Due to the first condition, holds. Due to the second condition, we get that also holds. Therefore also holds. Therefore also holds. Because we can move on step by step and reach every natural number, we conclude that the statement holds for every natural number

The verification of is called the base case, and the conclusion from to is called the induction step. Within the induction step, the validity of is called the induction hypothesis. In some situations, the statement is only valid (or defined) for for a certain . Then the base case is the statement and the induction step has to be done for .

We prove now the equality

by induction.

The base case is for , here the sum on the left consists of just one summand, which is , and so the sum equals . The right-hand side is , so the formula holds for .

For the induction step we assume that the formula holds for some . We have then to show that the formula also holds for . Here is arbitrary. We have

In the second equation, we have used the induction hypothesis. The last term is the right hand side of the formula for , so the formula is proven.

Proofs by induction occur again and again. The condition, that this method of proof can be applied, is that we have a scheme of statements, which depend on the (variable) natural number . This natural number is called the induction variable, we do induction over the induction variable . In the statement itself, arbitrary mathematical objects may occur and the natural number can have many different meanings. It can be the exponent of a real number (see fact or fact), the degree of a polynomial (as in fact), the degree of differentiability (see exercise) or the number of vectors (as in fact).