Sequences and induction

The last chapter began with a chessboard: one grain on the first square, two on the second, four on the third, and so on up to the sixty-fourth. In all, as we said there, there are $2^{64} - 1$ grains. We took this sum on trust. Nobody was going to add sixty-four numbers one by one, the last of them nineteen digits long. But the terms follow a rule, each twice the one before, and a sum that follows a rule can be found at once, without adding the terms one at a time. In this chapter we'll learn how.

There's a more serious question too. A formula for a sum is easy to check for $n = 1, 2, 3$ and even for $n = 1000$, but there are infinitely many values of $n$, and no computer can try them all. How can we be sure the formula is always true? The answer looks like a children's game. Stand dominoes in a row so that each one, as it falls, knocks the next, and push the first. They'll all fall, however many there are, and you don't need to look at each one: it's enough to know that the first will fall and that any falling domino knocks over its neighbour. This picture runs through the whole chapter. We'll first find each formula, by a trick, a picture or a guess, and then prove it for all $n$ at once.

A hundred terms

The most famous sum in the history of mathematics is told like this. At a school in Braunschweig, a teacher who wanted to keep the class busy for a long time told them to add all the numbers from $1$ to $100$. He had barely sat down when the nine-year-old Carl Friedrich Gauss put his slate in front of him with a single number on it: $5050$. The other pupils' answers came only at the end of the lesson, and nearly all of them were wrong.

Whatever the series, the trick the boy most likely used is worth knowing. Write the sum twice: first in increasing order, then in decreasing order, one line under the other.

$$\begin{array}{rcccccccccccc} S &=& 1 &+& 2 &+& 3 &+& \dots &+& 99 &+& 100 \\ S &=& 100 &+& 99 &+& 98 &+& \dots &+& 2 &+& 1 \\ \hline 2S &=& 101 &+& 101 &+& 101 &+& \dots &+& 101 &+& 101 \end{array}$$

In each column one term is one more than in the previous column and the other one less, so the column sum doesn't change: it's $101$ everywhere. There are a hundred columns, so $2S = 100 \cdot 101 = 10{,}100$ and $S = 5050$. One addition, one multiplication, one division.

Nothing in this trick depends on the number $100$. It can be drawn, and then it proves the formula for any number of terms at once.

The idea: fit the sum against itself so as to get a shape whose area is easy to count. Lay the terms out as columns of cells: the first column has $1$ cell, the second $2$, the last $n$. We get a staircase of area $S = 1 + 2 + \dots + n$. Take a second, identical staircase. Its area is also $S$, so the two staircases together have $\p3{2}S$. Turn the copy upside down and stand it on the first staircase. The copy's columns now go in reverse order, from $n$ to $1$, so above the column of height $k$ stands a column of height $n + 1 - k$. So every column of the shape has height $k + (n + 1 - k) = \p2{n + 1}$, the same for every $k$, and there are $\p1{n}$ columns. The two staircases have filled an $n \times (n + 1)$ rectangle with no gaps or overlaps. The area of the rectangle, $n(n + 1)$, equals $2S$, so $S = \frac{n(n + 1)}{2}$. We never used the value of $n$, so the formula holds for every $n$.

A striking clock strikes every hour as many times as the hour hand shows: once at one o'clock, twelve times at twelve. How many times does it strike in a day?

In one turn of the hand the clock strikes $1 + 2 + \dots + 12 = \frac{12 \cdot 13}{2} = 78$ times, and in a day the hand goes round the dial twice: $2 \cdot 78 = 156$ strikes.

Gauss was lucky: his sum had a trick that works for all $n$ at once. We aren't always that lucky. Often a formula can be guessed from a few examples, but no trick that explains it is in sight. Then we need the dominoes.

How to topple an infinite row

Let's add up the first odd numbers:

$$1 = 1, \qquad 1 + 3 = 4, \qquad 1 + 3 + 5 = 9, \qquad 1 + 3 + 5 + 7 = 16.$$

We get squares: $1^2$, $2^2$, $3^2$, $4^2$. In chapter 0 we saw how such coincidences deceive, and promised that this one wouldn't. It's time to prove it. Write $P(n)$ for the statement "the sum of the first $n$ odd numbers is $n^2$". There are really infinitely many statements, $P(1)$, $P(2)$, $P(3)$, …, and each is a domino in an infinite row.

All the dominoes can be toppled in two moves. First push the first one: check $P(1)$. Then make sure the row is set up properly: any falling domino knocks over the next, that is, $P(k)$ implies $P(k + 1)$, for every $k$, not just for some particular one.

The base, $n = 1$: on the left there's one term, $1$, on the right $1^2 = 1$. In the picture it's one cell, a $1 \times 1$ square. The first domino has fallen. The hypothesis: suppose that for some $k$ we already know $1 + 3 + \dots + (2k - 1) = k^2$, that is, the first $k$ odd numbers fit into a $k \times k$ square. Whatever $k$ is (the slider changes it), the argument is the same. The next odd number is $\p1{2k + 1}$. Lay out its cells as a corner: $k$ cells along the right side of the square, $k$ cells along the bottom and one cell in the corner. That's $k + k + 1 = 2k + 1$ in all. Fit the corner to the square. Both sides have grown by one, and we get a $(k + 1) \times (k + 1)$ square. In letters this is $k^2 + (2k + 1) = (k + 1)^2$, the square of a sum from the chapter on letters. So $P(k)$ implies $P(k + 1)$. The base holds, and the step is proved for every $k$. By the principle of induction, stated below, the formula holds for all $n$.

We've used a rule that it's time to state explicitly.

The idea: if the chain broke somewhere, the break would have a beginning, and that's exactly where the step would fail. Suppose the opposite: the base and the step hold, but $P(n)$ isn't true for all $n$. In domino terms, some dominoes are left standing. Among the numbers of the standing dominoes there's a smallest one: every non-empty set of natural numbers has a smallest element. Call it $m$. This is the first standing domino: $P(m)$ is false, and all the $P$'s with smaller numbers are true. $m \ne 1$, because by the base $P(1)$ is true: the first domino has fallen. So $m \ge 2$, and $m - 1$ is also a natural number. Domino $m - 1$ stands before the first standing one, so it has fallen: $P(m - 1)$ is true. The step applied with $k = m - 1$ says: $P(m - 1)$ implies $P(m)$. The fallen domino $m - 1$ must knock over domino $m$, but we chose $m$ to be standing. A contradiction. So there are no standing dominoes: $P(n)$ is true for all natural $n$.

To be honest: the proof relies on the property "every non-empty set of natural numbers has a smallest element". It and the principle of induction can each be derived from the other; they're two faces of one property of the natural numbers. In 1889 Giuseppe Peano put induction straight into the axioms of arithmetic; axioms are covered in the chapter on logic and sets.

The step often arouses suspicion: aren't we proving what we assumed? No. We don't claim that $P(k)$ is true; we prove a connection: if domino $k$ falls, it will knock over domino $k + 1$. Whether it actually falls is decided by the base and the chain of steps leading up to it.

Induction can prove Gauss's formula again. Base: $1 = \frac{1 \cdot 2}{2}$. Step: add $k + 1$ to both sides of $1 + 2 + \dots + k = \frac{k(k+1)}{2}$:

$$\frac{k(k + 1)}{2} + (k + 1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k + 1)(k + 2)}{2},$$

and this is Gauss's formula for $n = k + 1$. The staircase explains why the formula is what it is; induction checks that it's true. It's good to have both.

Which of these proves that a statement $P(n)$ is true for all natural $n$?

$P(1), P(2), \dots, P(10^{9})$ have been checked by computer $P(1)$ is true, and $P(k)$ implies $P(k + 1)$ for every $k$ $P(k)$ implies $P(k + 1)$ for every $k$ $P(1)$ is true, and $P(1)$ implies $P(2)$

Both parts are needed: the base starts the chain, and the step, proved for an arbitrary $k$, passes it on without end.

In everyday language "induction" means reasoning from the particular to the general: the sun has risen every morning, so it will rise tomorrow. Mathematical induction is different: it's a rigorous deduction, only its chain of steps is infinite.

A progression with a step

In Gauss's sum each term was one more than the one before. The step can be different, and such rows are easiest to discuss in general.

A sequence can be given by a formula for its $n$th term, for example $a_n = n^2$: $1, 4, 9, 16, \dots$ Or by a rule that gets the next term from the previous ones. For example, $a_1 = 1$ and $a_{n+1} = 2a_n + 1$ give $1, 3, 7, 15, 31, \dots$

A recurrence is a ready-made row of dominoes: the first term is the base, the rule is the step. That's the main way of proving things about such sequences.

Examples: $5, 8, 11, 14, \dots$ (difference $3$); $10, 7, 4, 1, -2, \dots$ (difference $-3$, a decreasing progression); $7, 7, 7, \dots$ (difference $0$). The house numbers on the even side of a street form a progression with difference $2$.

The idea: from the first term to the $n$th we go in steps, and each step adds the same number. We start from the first term, $\p1{a_1}$. By the definition of a progression each next term is the previous one plus $\p3{d}$: $a_2 = a_1 + d$, $a_3 = a_2 + d = a_1 + 2d$, and so on. From $a_1$ to $a_n$ there are $\p2{n - 1}$ steps: one fewer steps than terms, just as a fence has one fewer gaps than posts. Each step added $d$, so $(n - 1)d$ was added in all. So $a_n = a_1 + (n - 1)d$. Induction makes the words "and so on" rigorous: for $n = 1$ the formula gives $a_1$, and if $a_k = a_1 + (k - 1)d$, then $a_{k+1} = a_k + d = a_1 + kd$.

Why is the progression called arithmetic? Each of its terms except the first is the arithmetic mean of its neighbours: $a_n = \frac{a_{n-1} + a_{n+1}}{2}$, because the left neighbour is $d$ less and the right one $d$ more. In the row $5, 8, 11$ the eight is exactly in the middle: $\frac{5 + 11}{2} = 8$.

Now the sum. Gauss's staircase works here too, only the steps can be of any height.

The idea is the same as Gauss's. Lay out the terms of the progression as columns: heights $a_1, a_2, \dots, a_n$, each $d$ more than the one before. The area of the staircase is $S_n$. The sliders change $a_1$, $d$ and $n$; the picture has $d \ge 0$, but the sign of $d$ doesn't matter anywhere in the calculation below. Take an identical staircase; its area is also $S_n$. Turn it over and stand it on top. The copy's columns go from $a_n$ to $a_1$, so above the column $a_k$ stands the column $a_{n+1-k}$. By the $n$th-term formula $a_k = a_1 + (k - 1)d$, and $a_{n+1-k} = a_1 + (n - k)d$, that is, $a_n - (k - 1)d$. Add them: $a_k + a_{n+1-k} = \p1{a_1 + a_n}$. However far the original staircase rises above $a_1$, the copy drops the same amount below $a_n$, and all the columns have the same height. There are $\p2{n}$ columns: we've got a rectangle. The area of the rectangle, $(a_1 + a_n) \cdot n$, is two staircases, $2S_n$. Halve it and we have the formula.

An amphitheatre has $20$ rows. The first row has $12$ seats, and each following row has $3$ more than the one before. How many seats does the amphitheatre have in all?

The seats by row form a progression with $a_1 = 12$ and $d = 3$. The last row has $a_{20} = 12 + 19 \cdot 3 = 69$ seats. In all $S_{20} = \frac{(12 + 69) \cdot 20}{2} = 81 \cdot 10 = 810$.

A progression with a factor

Back to the chessboard. Each square has twice as many grains as the one before: here the step isn't added, it's multiplied.

Examples: $1, 2, 4, 8, \dots$ ($q = 2$, the chessboard); $3, -6, 12, -24, \dots$ ($q = -2$, the signs alternate); $1000, 100, 10, 1, 0.1, \dots$ ($q = \frac{1}{10}$). Zeros are forbidden: after a zero there would be nothing but zeros, and the ratio couldn't be recovered. The name is explained the same way as for the arithmetic kind: each term of a positive geometric progression except the first is the geometric mean of its neighbours, $b_n = \sqrt{b_{n-1} b_{n+1}}$. In the row $2, 4, 8$ the four is $\sqrt{2 \cdot 8}$.

The idea is the same as for an arithmetic progression, only the step is a multiplication. We start from the first term, $\p1{b_1}$. Each next term is the previous one times $\p2{q}$: $b_2 = b_1 q$, $b_3 = b_2 q = b_1 q^2$, and so on. From $b_1$ to $b_n$ there are $\p3{n - 1}$ steps, and each one brings a factor $q$: $\underbrace{q \cdot q \cdot \ldots \cdot q}_{n - 1} = q^{n-1}$ in all. So $b_n = b_1 q^{n-1}$. By induction: $b_1 = b_1 q^0$, and $b_k = b_1 q^{k-1}$ implies $b_{k+1} = b_k q = b_1 q^k$.

A geometric progression is the exponential growth of the last chapter, seen in whole steps. Now the sum all this was for. Gauss's trick doesn't help here: turning the row $1 + 2 + 4 + \dots + 2^{63}$ round won't give equal columns. We need another trick.

The idea: multiplying by the common ratio shifts the progression by one place, and the sum and its shift have almost all their terms in common. Write the sum as a row: $S = b_1 + b_1 q + \dots + b_1 q^{n-1}$. In the picture $b_1 = 1$; for another $b_1$ each cell is simply multiplied by $b_1$. Multiply the sum by $q$ by multiplying each term by $q$ (the distributive law): $qS = b_1 q + b_1 q^2 + \dots + b_1 q^n$. Each term has turned into the next one, and the row has shifted one place to the right. The terms $b_1 q, \dots, b_1 q^{n-1}$ appear in both rows. When we subtract, $qS - S$, they cancel out. Only the ends remain: the last cell of the bottom row, $\p2{b_1 q^n}$, and the first cell of the top row, $\p1{b_1}$. We get $qS - S = b_1 q^n - b_1$, that is, $S(q - 1) = b_1(q^n - 1)$. If $q \ne 1$, divide both sides by $\p3{q - 1}$ and get $S_n = b_1 \cdot \frac{q^n - 1}{q - 1}$.

For the board $b_1 = 1$, $q = 2$, $n = 64$, and the sum is $2^{64} - 1 = 18{,}446{,}744{,}073{,}709{,}551{,}615$. The last chapter's debt is paid.

You get a chain letter and send it on to three people you know. Each of them also sends it to three people, and so on for six rounds: in each round every new recipient writes to three new people. How many letters are sent in all, counting your three?

By round, the letters number $3, 9, 27, \dots$: a geometric progression with $b_1 = 3$ and $q = 3$, six terms long. In all $S_6 = 3 \cdot \frac{3^6 - 1}{3 - 1} = 3 \cdot \frac{728}{2} = 1092$. With twenty-one rounds instead of six there would be $S_{21} = \frac{3(3^{21} - 1)}{2} \approx 1.6 \cdot 10^{10}$ letters, twice as many as there are people on Earth.

Achilles and the tortoise

About two and a half thousand years ago Zeno of Elea came up with an argument that has come down to us as retold by Aristotle. Swift-footed Achilles is chasing a tortoise. By the time he reaches the place where the tortoise was, it has crawled a little further; while he covers that bit, a little further still, and so on without end. So, Zeno concluded, Achilles will never catch it.

Let's put in numbers. Say Achilles runs at $10$ m/s, the tortoise crawls ten times slower, at $1$ m/s (a very fast tortoise), and it has a $100$ m head start. Achilles runs $100$ m in $10$ s, and the tortoise has crawled $10$ m. He runs those $10$ m in $1$ s, and it has crawled another $1$ m. Then $0.1$ s, then $0.01$… There are infinitely many stages, and their durations form a geometric progression with ratio $\frac{1}{10}$:

$$10 + 1 + 0.1 + 0.01 + \dots = 11.111\dots = 11.\overline{1} \text{ s}.$$

Infinitely many terms have given a finite sum, $\frac{100}{9}$ seconds. The same answer comes out without any stages: Achilles gains $10 - 1 = 9$ m on the tortoise every second, and the hundred-metre head start is gone in $\frac{100}{9}$ s. Zeno was right that there are infinitely many stages, but wrong to think that infinitely many stages need infinitely much time.

Infinitely many terms can't be added one by one, but we can add the first $n$ and watch what these partial sums approach.

The idea: watch not the sum but how far short it falls of the number $L = \frac{b_1}{1 - q}$. The first term, $\p1{b_1}$, is the first bar. Note that $b_1 = (1 - q)L$: that's how $L$ was chosen. In the picture $b_1 = 1$, and the slider changes the ratio $q$. After the first term the shortfall to $L$ is $L - b_1 = L - (1 - q)L = qL$. By the sum formula from the last section $S_n = b_1 \cdot \frac{1 - q^n}{1 - q} = L(1 - q^n)$, so the shortfall after $n$ terms is $L - S_n = \p2{q}^n L$. Each new term shrinks it by a factor of $\frac{1}{|q|}$. With negative $q$ the sums jump across $L$, now to the right, now to the left: move the slider. If $\p3{|q| < 1}$, the number $|q|^n$ becomes smaller than any positive number once $n$ is large enough: $0.5^{10} < 0.001$, $0.5^{20} < 0.000001$. Why this happens for every $|q| < 1$ is in the fold-out below. So the shortfall $|L - S_n| = |q|^n |L|$ also becomes arbitrarily small. The sums $S_n$ come arbitrarily close to $L$, and by definition the sum of the infinite progression is $L = \frac{b_1}{1 - q}$.

Why $|q|^n$ gets arbitrarily small

Let $0 < |q| < 1$ (for $q = 0$ there's nothing to prove). Then $\frac{1}{|q|} > 1$; write $\frac{1}{|q|} = 1 + h$ with $h > 0$. Let's prove Bernoulli's inequality by induction: $(1 + h)^n \ge 1 + nh$. Base: $(1 + h)^1 = 1 + h$. Step: if $(1 + h)^k \ge 1 + kh$, multiply both sides by the positive number $1 + h$:

$$(1 + h)^{k+1} \ge (1 + kh)(1 + h) = 1 + (k + 1)h + kh^2 \ge 1 + (k + 1)h.$$

So $|q|^n = \frac{1}{(1 + h)^n} \le \frac{1}{1 + nh}$. However small a positive number $\varepsilon$ we're given, for $n > \frac{1}{h\varepsilon}$ we get $1 + nh > \frac{1}{\varepsilon}$ and $|q|^n < \varepsilon$. Arguments of the form "for every $\varepsilon$ there is an $n$" are the language of limits, covered in detail in the chapter on limits, and infinite sums of every kind get the chapter on series.

Now we can take another look at the equation that bothered many people in the chapter on fractions.

Write the repeating decimal $0.\overline{12} = 0.121212\dots$ as a fraction in lowest terms by adding up a geometric progression.

$0.\overline{12} = \frac{12}{100} + \frac{12}{10{,}000} + \dots$, a progression with $b_1 = \frac{12}{100}$ and $q = \frac{1}{100}$. Its sum is $\frac{12/100}{1 - 1/100} = \frac{12/100}{99/100} = \frac{12}{99} = \frac{4}{33}$. Check by division: $4 : 33 = 0.1212\dots$

What is the sum $1 + 2 + 4 + 8 + 16 + \dots$ (without end)?

$-1$, by the formula $\frac{1}{1 - 2}$ No number: the sums $2^n - 1$ grow without limit $2^{64} - 1$, as on the chessboard

The sum of the first $n$ terms is $2^n - 1$, and it becomes larger than any number given in advance. This series has no finite sum.

Cubes that make a square

The odd numbers added up to squares. Now let's add up cubes:

$$1^3 = 1, \quad 1^3 + 2^3 = 9, \quad 1^3 + 2^3 + 3^3 = 36, \quad 1^3 + 2^3 + 3^3 + 4^3 = 100.$$

Squares again, and squares of triangular numbers at that: $1 = 1^2$, $9 = 3^2$, $36 = 6^2$, $100 = 10^2$, and $1$, $3$, $6$, $10$ are $1$, $1 + 2$, $1 + 2 + 3$, $1 + 2 + 3 + 4$.

The idea: cut a square of side $\p1{1 + 2 + \dots + n}$ into pieces of area $1^3, 2^3, \dots, n^3$. Write $T_k = 1 + 2 + \dots + k$ and mark the side of the square in segments $1, 2, \dots, n$: the whole side is $T_n$, and the area of the square is $T_n^2$. From the top left corner mark squares of sides $T_1, T_2, \dots, T_{n-1}$. They cut the big square into L-shaped layers: layer $k$ is the $T_k \times T_k$ square minus the $T_{k-1} \times T_{k-1}$ square. Its width is $T_k - T_{k-1} = k$. Cut layer $k$ into two strips of width $k$: a vertical one of length $T_k$ and a horizontal one of length $T_{k-1}$. Its area is $k \cdot T_k + k \cdot T_{k-1} = k(T_k + T_{k-1})$. And $T_k + T_{k-1} = \frac{k(k+1)}{2} + \frac{(k-1)k}{2} = \frac{k \cdot 2k}{2} = k^2$: two neighbouring Gauss staircases make a square. So the area of the layer is $k \cdot k^2 = k^3$. The picture shows this even without calculation: layer $k$ is made up of exactly $k$ squares of size $k \times k$. When $k$ is even, one of them is cut in half, and the halves lie at the two ends of the layer. The whole square consists of the layers numbered $1, 2, \dots, n$, so $T_n^2 = 1^3 + 2^3 + \dots + n^3$ for every $n$.

A numerical road leads to the same formula. Nicomachus of Gerasa (around 100 AD) observed that cubes are made up of consecutive odd numbers: $1 = 1^3$, $3 + 5 = 2^3$, $7 + 9 + 11 = 3^3$, $13 + 15 + 17 + 19 = 4^3$. In the $k$th group, $k$ odd numbers stand symmetrically around $k^2$, so their sum is $k \cdot k^2$. The groups follow one another, so the first $n$ cubes are the first $1 + 2 + \dots + n$ odd numbers, and their sum is the square of how many there are.

The identity for the sum of cubes is often called Nicomachus's theorem. It also appears in the work of the Indian mathematician Aryabhata in the fifth century and of the Persian mathematician al-Karaji around the year 1000; historians regard al-Karaji's argument as one of the first glimmers of induction.

A broken domino

Induction is reliable as long as both its parts are. Break one and the row stays standing, however convincing the argument looks. Here's a famous example, usually associated with the Hungarian mathematician George Pólya.

The conclusion is plainly false, so there's a mistake. The base is right. The step for $k = 2, 3, 4, \dots$ really is right. But it has to work for $k = 1$ too, for going from one horse to two. Then "all but the last" is the first horse and "all but the first" is the second. There are no horses "in the middle", the two groups have nothing in common, and nothing links their colours. One domino stands too far away, and the chain breaks at the very first step.

At which step does the proof that all horses are the same colour break down?

From one horse to two From two horses to three The base is wrong A little at every step

For $k = 1$ the two groups of one horse each don't overlap. All the other steps are right, but without the step from one horse to two they achieve nothing: the chain breaks straight after the first domino.

The opposite breakdown is a step with no base. The statement "$n = n + 1$" is false for every $n$, and yet the step for it can be proved honestly: add one to both sides of $k = k + 1$ and get $k + 1 = k + 2$. Each domino would knock over the next if even one fell. But there's nothing to push the first one with.

The third breakdown is the most common: the base has been checked, and not once, but there's no step at all. The expression $n^2 + n + 41$ from chapter 0 gives primes for forty values of $n$ in a row: forty dominoes stood up separately, with no link between them. At $n = 40$ we get $40^2 + 40 + 41 = 41^2$, a composite number.

Fibonacci's rabbits

In 1202 Leonardo of Pisa, later nicknamed Fibonacci, finished his Book of Calculation (Liber Abaci), the very book that brought the Indian numerals to Europe (we told its story in the chapter on counting). Among its hundreds of problems is one about rabbits. A pair of rabbits produces a new pair every month, and a newborn pair starts breeding after a month. Rabbits don't die. How many pairs will there be after a year if we start with one adult pair?

Let's count month by month. At the start there's one pair, after a month two, after another month three: the adult pair has bred again, and the young pair has only grown up. Then five, eight, thirteen… The rule is this: next month there are as many pairs as this month plus the newborns, and there are as many newborns as there were pairs a month ago, since they're all adults by now. We get the row $1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377$, and Fibonacci's answer is $377$ pairs.

The pairs a month from now. The pairs now: all of them will live to next month. The pairs a month ago: by next month they're all adults, and each will produce a new pair. Example: $F_{13} = F_{12} + F_{11} = 144 + 89 = 233$, $F_{14} = 233 + 144 = 377$, the rabbit answer.

The sequence got its name in the nineteenth century from the French mathematician Édouard Lucas. Fibonacci numbers pop up everywhere: they show how many steps the Euclidean algorithm takes in the worst case, and they hide on the shallow diagonals of Pascal's triangle.

Induction for such sequences works a little differently: each domino falls from the blows of the two before it, so the first two have to be pushed.

Still, they grow fast, almost like a geometric progression. Lay out squares of sides $1, 1, 2, 3, 5, 8, \dots$, each new one along the long side of the rectangle built so far. The side of the new square is the sum of the two before it, so it always fits exactly, and we get a rectangle again, with sides $F_n$ and $F_{n+1}$.

The ratios of neighbouring Fibonacci numbers, $\frac11 = 1$, $\frac21 = 2$, $\frac32 = 1.5$, $\frac53 \approx 1.667$, $\frac85 = 1.6$, $\frac{13}{8} = 1.625$, oscillate and converge to the number $1.618\dots$ Johannes Kepler noticed this back in 1611. Which number it is can be found out without even proving that the ratios converge to anything.

The number $\varphi = \frac{1 + \sqrt5}{2} \approx 1.6180339887$ is called the golden ratio. That it's irrational, and in a certain sense "the most irrational" of all numbers, is told in the chapter on the square root of two. That the limit of the ratios really exists is proved carefully with limits (chapter 25). And the exact formula for $F_n$, Binet's formula, expresses it in terms of powers of $\varphi$ and of the other root of the same equation; it's easiest to derive with matrices, which is done in the chapter on eigenvectors.

Find the sum of the first ten Fibonacci numbers: $F_1 + F_2 + \dots + F_{10}$. Work out the sums of the first two, three, four numbers, and guess the pattern.

$1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143$. The sums of the first numbers, $1, 2, 4, 7, 12, 20, \dots$, are one less than every other Fibonacci number: $F_1 + \dots + F_n = F_{n+2} - 1$, and indeed $143 = F_{12} - 1 = 144 - 1$. By induction: the base is $F_1 = 1 = F_3 - 1$; for the step, add $F_{k+1}$ to $F_{k+2} - 1$ and get $F_{k+3} - 1$.

Practice

The trainer has three levels. The first is arithmetic progressions: find a term, a sum, the difference from two terms. The second is geometric ones. The third has harder problems: infinite sums, repeating decimals, the number of terms from the sum.

A progression problem of your own can be taken apart step by step in the solver, and all the course's trainers are collected on the practice page.

Where next

Time and again the sums in this chapter turned out to be polynomials in $n$: $1 + 2 + \dots + n = \frac{n^2 + n}{2}$, the sum of cubes is $\frac{n^4 + 2n^3 + n^2}{4}$, and the sum of squares $1^2 + 2^2 + \dots + n^2$ has a formula like that too: try to guess it and prove it by induction. The main question about polynomials is the same as for a quadratic: where are they zero? Here's a polynomial of degree three: $x^3 - 6x^2 + 11x - 6$. Substitute $x = 1$, $2$ and $3$, and you get zero every time. Does it have other roots? How do you look for them if guessing fails, and is there a formula for degree three, as there is for degree two? A lot can be learned about roots without any formula, if you understand how polynomials work. That's the subject of the chapter on polynomials, along with the Italian mathematicians of the sixteenth century who solved such equations in public duels.