1.14 Induction

We are concerned here with statements about a positive integer $n\,$. The statement

$$1+2+3+\dots+n=2^{-1}n(n+1)$$

is a statement about an integer $n\,$. For instance, when $n=3\,$ it asserts that

$$1+2+3=2^{-1}\cdot 3\cdot 4;$$

when $n=7\,$, it asserts that

$$1+2+3+\dots+7=2^{-1}\cdot 7\cdot 8.$$

We write

$$P(n):\quad\quad 1+2+3+\dots+n=2^{-1}n(n+1),$$

where $n\geq 1\,$ is an integer. Instead of checking each case, we want a means of proving every case systematically – this is provided by the induction machine.