6: Infinity - Recursion, Induction, Infinite Descent

Mathematical induction – i.e. proof by recurrence – is... imposed on us, because it is... the affirmation of a property of the mind itself.

Henri Poincaré (1854–1912)

Allez en avant, et la foi vous viendra. (Press on ahead, and understanding will follow.)

Jean le Rond d’Alembert (1717–1783)

Mathematics has been called “the science of infinity”. However, infinity is a slippery notion, and many of the techniques which are characteristic of modern mathematics were developed precisely to tame this slipperiness. This chapter introduces some of the relevant ideas and techniques.

There are aspects of the story of infinity in mathematics which we shall not address. For example, astronomers who study the night sky and the movements of the planets and stars soon note its immensity, and its apparently ‘fractal’ nature – where increasing the detail or magnification reveals more or less the same level of complexity on different scales. And it is hard then to avoid the question of whether the stellar universe is finite or infinite.

In the mental universe of mathematics, once counting, and the process of halving, become routinely iterative processes, questions about infinity and infinitesimals are almost inevitable. However, mathematics recognises the conceptual gulf between the finite and the infinite (or infinitesimal), and rejects the lazy use of “infinity” as a metaphor for what is simply “very large”. Large finite numbers are still numbers; and long finite sums are conceptually quite different from sums that “go on for ever”. Indeed, in the third century BC, Archimedes (c. 287–212 BC) wrote a small booklet called The Sand Reckoner, dedicated to King Gelon, in which he introduced the arithmetic of powers (even though the ancient Greeks had no convenient notation for writing such numbers), in order to demonstrate that – contrary to what some people had claimed – the number of grains of sand in the known universe must be finite (he derived an upper bound of approximately 8×10⁶³ The influence wielded by ideas of infinity on mathematics has been profound, even if we now view some of these ideas as flights of fancy –

• from Zeno of Elea (c. 495 BC – c. 430 BC), who presented his paradoxes to highlight the dangers inherent in reasoning sloppily with infinity,
• through Giordano Bruno (1548–1600), who declared that there were infinitely many inhabited universes, and who was burned at the stake when he refused to retract this and other “heresies”,
• to Georg Cantor (1845–1918) whose groundbreaking work in developing a true “mathematics of infinity” was inextricably linked to his religious beliefs.

In contrast, we focus here on the delights of the mathematics, and in particular on how an initial doorway into “ideas of infinity” can be forged from careful reasoning with finite entities. Readers who would like to explore what we pass over in silence could do worse than to start with the essay on “infinity” in the MacTutor History of Mathematics archive:

http://www-history.mcs.st-and.ac.uk/HistTopics/Infinity.html.

The simplest infinite processes begin with recursion – a process where we repeat exactly the same operation over and over again (in principle, continuing for ever). For example, we may start with 0, and repeat the operation “add 1”, to generate the sequence:

0, 1, 2, 3, 4, 5, 6, 7,….

Or we may start with 2⁰ = 1 and repeat the operation “multiply by 2”, to generate:

$$\begin{array}{cc}& \mathrm{1,\; 2,\; 4,\; 8,\; 16,\; 32,\; 64,\; 128,\dots .}\hfill \end{array}$$

Or we may start with 1.000000 ⋯, and repeat the steps involved in “dividing by 7” to generate the infinite decimal for $\frac{1}{7}$ :

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{1}{7}=0.1428571428571428571\cdots .\hfill \end{array}$$

We can then vary this idea of “recursion” by allowing each operation to be “essentially” (rather than exactly) the same, as when we define triangular numbers by “adding n” at the n^th stage to generate the sequence:

$$\begin{array}{cc}& \mathrm{0,\; 1,\; 3,\; 6,\; 10,\; 15,\; 21,\; 28,\dots .}\hfill \end{array}$$

In other words, the sequence of triangular numbers is defined by a recurrence relation:

$T_0=\mathrm{0;}$ and

when $n\ge \mathrm{1,}$ $T_n={}_{}$Tn-1+n.

We can vary this idea further by allowing more complicated recurrence relations – such as that which defines the Fibonacci numbers:

$F_0=\mathrm{0,}$ $F_1=\mathrm{1;}$ and
when $n\ge 1$ $F_{n+1}=F_n+{}_{}$Fn-1.

All of these “images of infinity” hark back to the familiar counting numbers.

• We know how the counting numbers begin (with 0, or with 1); and
• we know that we can “add 1” over and over again to get ever larger counting numbers.

The intuition that this process is, in principle, never–ending (so is never actually completed), yet somehow manages to count all positive integers, is what Poincaré called a “property of the mind itself”: that is, the idea that we can define an infinite sequence, or process, or chain of deductions (involving digits, or numbers, or objects, or statements, or truths) by

• specifying how it begins, and by then
• specifying in a uniform way “how to construct the next term ”, or “how to perform the next step”.

This idea is what lies behind “proof by mathematical induction”, where we prove that some assertion P(n) holds for all $n\ge 1$ – so demonstrating infinitely many separate statements at a single blow. The validity of this method of proof depends on a fundamental property of the positive integers, or of the counting sequence

$$\begin{array}{cc}& \mathrm{“1,\; 2,\; 3,\; 4,\; 5,\; \dots ”,}\hfill \end{array}$$

namely:

The Principle of Mathematical Induction: If a subset S of the positive integers

• contains the integer “1”,
  and has the property that
• whenever an integer k is in the set S, then the next integer $k+1$ is always in S too,

then S contains all positive integers.