Induction/Line configurations/Introduction/Section

The natural numbers have the characteristic property that one can reach every natural number starting from ${}0$ 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.

Example

We consider in the plane ${}E$ a configuration of ${}n$ 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 ${}\mathbb {R} ^{2}$ (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 ${}n$ is small, it is easy to find the answer.

${}n$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}n$
${}S(n)$	${}0$	${}0$	${}1$	${}3$	${}6$	${}?$	${}?$

But as soon an ${}n$ gets a bit larger (${}n=5,10,\ldots$?), 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 ${}n$ lines we consider ${}n+1$ lines. Suppose that, for some reason, we know what the maximal number of intersection points for ${}n$ 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 ${}n+1$ 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 ${}n$ 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 ${}n$ new intersection points. Hence, we deduce the (preliminary) formula

${}S(n+1)=1+2+3+\cdots +n-2+n-1+n\,$

or

${}S(n)=1+2+3+\cdots +n-3+n-2+n-1\,,$

so just the sum of the first ${}n-1$ 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 ${}a_{1},\ldots ,a_{n}$ we define

${}\sum _{k=1}^{n}a_{k}:=a_{1}+a_{2}+\cdots +a_{n-1}+a_{n}\,.$

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

${}\prod _{k=1}^{n}a_{k}:=a_{1}\cdot a_{2}\cdots a_{n-1}\cdot a_{n}\,.$

Example

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

${}\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,$

holds. For small numbers ${}n$, 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 ${}n$ to ${}n+1$, like we have added in example another line to a line configuration. On the left-hand side, we just have the additional summand ${}n+1$. On the right-hand side, we go from ${}{\frac {n(n+1)}{2}}$ to ${}{\frac {(n+1)(n+1+1)}{2}}$. If we can show that the difference between these fractions is ${}n+1$, then the right-hand side behaves like the left-hand side. Then we can conclude: the identity holds for small ${}n$, say for ${}n=1$. By comparing the differences, it also holds for the next ${}n$, so it holds for ${}n=2$, then again for the next ${}n$ 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.

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

Theorem

Suppose that for every natural number ${}n$ a statement ${}A(n)$ is given. Suppose further that the following conditions are fulfilled.

1. ${}A(0)$ is true.
2. For all ${}n$ we have: if ${}A(n)$ holds, then also ${}A(n+1)$ holds.

Then ${}A(n)$ holds for all ${}n$.

Proof

Due to the first condition, ${}A(0)$ holds. Due to the second condition, we get that also ${}A(1)$ holds. Therefore also ${}A(2)$ holds. Therefore also ${}A(3)$ holds. Because we can move on step by step and reach every natural number, we conclude that the statement ${}A(n)$ holds for every natural number ${}n$

$\Box$

The verification of ${}A(0)$ is called the base case, and the conclusion from ${}A(n)$ to ${}A(n+1)$ is called the induction step. Within the induction step, the validity of ${}A(n)$ is called the induction hypothesis. In some situations, the statement ${}A(n)$ is only valid (or defined) for ${}n\geq n_{0}$ for a certain ${}n_{0}$. Then the base case is the statement ${}A(n_{0})$ and the induction step has to be done for ${}n\geq n_{0}$.

We prove now the equality

${}\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,.$

by induction.

The base case is for ${}n=1$, here the sum on the left consists of just one summand, which is ${}1$, and so the sum equals ${}1$. The right-hand side is ${}{\frac {1\cdot 2}{2}}=1$, so the formula holds for ${}n=1$.

For the induction step we assume that the formula holds for some ${}n\geq 1$. We have then to show that the formula also holds for ${}n+1$. Here ${}n$ is arbitrary. We have

${}{\begin{aligned}\sum _{k=1}^{n+1}k&={\left(\sum _{k=1}^{n}k\right)}+n+1\\&={\frac {n(n+1)}{2}}+n+1\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+2)(n+1)}{2}}.\end{aligned}}$

In the second equation, we have used the induction hypothesis. The last term is the right hand side of the formula for ${}n+1$, so the formula is proven.

Remark

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 ${}n$. This natural number ${}n$ is called the induction variable, we do induction over the induction variable ${}n$. In the statement itself, arbitrary mathematical objects may occur and the natural number ${}n$ 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).