Recurrences

Some counts have no obvious formula, yet are easy to describe in terms of smaller versions of themselves: the moves needed for ten discs are easy to relate to the moves needed for nine.

The previous lessons counted a set directly, by a product, a binomial coefficient, or the inclusion and exclusion formula that corrects for overlap. This lesson writes the answer for size $n$ in terms of the answers for smaller sizes, which is a recurrence, and then turns the recurrence into a formula by one of two methods: unrolling, or guessing and proving the guess by induction (show the first case, then show that each case implies the next). It ends with a famous recurrence that defeats both.

The Tower of Hanoi

In 1883 Édouard Lucas put a puzzle on sale under the name N. Claus de Siam, an anagram of Lucas d'Amiens. Eight discs of different sizes sit on one of three pegs, largest at the bottom, and the task is to move the tower to another peg one disc at a time, never placing a disc on a smaller one. A legend published with it told of priests moving a tower of sixty-four golden discs, with the world to end when they finished.

Let $T_{n}$ be the fewest moves that transfer $n$ discs. Plainly $T_{0} = 0$ and $T_{1} = 1$ , while $T_{2} = 3$ : the small disc steps aside, the large one moves, the small one returns. For the general case, watch the largest disc. It can only move when all $n - 1$ others are stacked on the third peg, out of its way. So one solution moves the top $n - 1$ discs to the spare peg, moves the largest disc, then moves the $n - 1$ discs back on top of it. Sitting at the bottom, the largest disc never obstructs those smaller towers, so this uses $2 T_{n - 1} + 1$ moves.

That is only an upper bound, so it remains to show nothing shorter exists. The largest disc must move at least once. Before its first move, the other $n - 1$ discs must be gathered into one stack on another peg, which takes at least $T_{n - 1}$ moves, and after its last move they must all be brought back on top of it, at least $T_{n - 1}$ more. So every solution uses at least $2 T_{n - 1} + 1$ moves, and

T_{n} = 2 T_{n - 1} + 1 for n \geq 1, T_{0} = 0

The rule produces $1, 3, 7, 15, 31$ , and Lucas's eight discs need $T_{8} = 255$ moves. The rule alone is not enough: $a_{n} = 2 a_{n - 1} + 1$ with $a_{0} = 5$ is a different sequence. A recurrence comes with initial conditions, as many as the number of earlier terms each step looks back to.

Unrolling

The values $1, 3, 7, 15, 31, 255$ are each one less than a power of two. To prove it, substitute the recurrence into itself:

T_{n} = 2 T_{n - 1} + 1 = 4 T_{n - 2} + 2 + 1 = 8 T_{n - 3} + 4 + 2 + 1

After $k$ steps, $T_{n} = 2^{k} T_{n - k} + 2^{k - 1} + \dots + 2 + 1$ . At $k = n$ the initial condition $T_{0} = 0$ appears, and the geometric series left behind sums to

T_{n} = 2^{n} - 1

This is unrolling: expand until the initial condition appears, then add up what has accumulated. It works when each term depends on one earlier term and the leftover sum can be evaluated. The priests' tower needs $2^{64} - 1 = 18 446 744 073 709 551 615$ moves, which at one a second takes about $585$ billion years, over forty times the present age of the universe.

Example. In a stricter version the pegs stand in a row and a disc may only move to a neighbouring peg. How many moves does the natural strategy use to carry $n$ discs from one end peg to the other?

Call it $a_{n}$ . The largest disc must go left to middle, then middle to right, and each time the other $n - 1$ discs must be on the peg it is not using. So move them left to right ( $a_{n - 1}$ moves), the largest disc to the middle ( $1$ ), the others right to left ( $a_{n - 1}$ ), the largest to the right ( $1$ ), and the others left to right ( $a_{n - 1}$ ). That is $a_{n} = 3 a_{n - 1} + 2$ with $a_{0} = 0$ . Unrolling gives $a_{n} = 3^{k} a_{n - k} + 2 (3^{k - 1} + \dots + 1)$ , and at $k = n$ the series sums to $\frac{3^{n} - 1}{2}$ , so $a_{n} = 3^{n} - 1$ . Three discs need $26$ moves instead of $7$ , and a computer search confirms nothing shorter exists.

Now you. A double tower has two identical discs of each of $n$ sizes, and a disc may rest on one of equal size. Set up a recurrence for the fewest moves $H_{n}$ that carry it to another peg, unroll it, and find $H_{5}$ .

Answer

The argument runs as before with the bottom pair in place of the largest disc: move the top $n - 1$ pairs aside, move the two largest discs, bring the pairs back. So $H_{n} = 2 H_{n - 1} + 2$ with $H_{0} = 0$ , which unrolls to $H_{n} = 2 (2^{n - 1} + \dots + 1) = 2^{n + 1} - 2$ , twice the single tower. So $H_{5} = 62$ .

Bit strings with no two consecutive 1s

How many bit strings of length $n$ have no two 1s side by side? For length $3$ , five of the eight qualify: $000$ , $001$ , $010$ , $100$ and $101$ . No product rule applies, because whether a bit may be $1$ depends on its neighbour.

Let $b_{n}$ count the good strings of length $n$ , and sort them by their last bit. A good string ending in $0$ is any good string of length $n - 1$ with a $0$ added, since a final $0$ cannot create a forbidden pair: $b_{n - 1}$ of those. A good string ending in $1$ has a $0$ just before it, so it is a good string of length $n - 2$ followed by $01$ : $b_{n - 2}$ of those. By the sum rule,

b_{n} = b_{n - 1} + b_{n - 2} for n \geq 2

Each step looks back two terms, so two initial conditions are needed: the empty string is good, so $b_{0} = 1$ , and both strings of length $1$ are good, so $b_{1} = 2$ . The recurrence then gives $3, 5, 8, 13, 21, 34, 55, 89, 144$ , so $b_{10} = 144$ , as a computer check of all $1024$ strings confirms.

These are the Fibonacci numbers, here defined by $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ , so the sequence runs $0, 1, 1, 2, 3, 5, 8, \dots$ . The indexing matters because books differ, some starting from $1, 2$ . With this one, $b_{n}$ and $F_{n + 2}$ obey the same recurrence and agree at $n = 0$ and $n = 1$ , since $b_{0} = 1 = F_{2}$ and $b_{1} = 2 = F_{3}$ , so they agree forever: $b_{n} = F_{n + 2}$ . The name is that of Leonardo of Pisa, whose Liber Abaci of 1202 counted breeding rabbits and found $377$ pairs after a year, though Hemachandra had met the same numbers around 1150, counting rhythms in Sanskrit verse built from syllables of one beat and two.

Example. How many strings of length $5$ over ${a, b, c}$ have no two consecutive $a$ s?

Let $t_{n}$ count them and sort by the last letter. If it is $b$ or $c$ , the rest is any good string of length $n - 1$ , giving $2 t_{n - 1}$ . If it is $a$ , the letter before is $b$ or $c$ , preceded by any good string of length $n - 2$ , giving $2 t_{n - 2}$ . So $t_{n} = 2 t_{n - 1} + 2 t_{n - 2}$ with $t_{0} = 1$ and $t_{1} = 3$ . Then $t_{2} = 8$ , which is all nine pairs except $a a$ , followed by $t_{3} = 22$ , $t_{4} = 60$ and $t_{5} = 164$ .

Now you. How many bit strings of length $7$ contain no three consecutive 1s?

Answer

A good string ends in $0$ , $01$ or $011$ , preceded by a good string of length $n - 1$ , $n - 2$ or $n - 3$ . So $c_{n} = c_{n - 1} + c_{n - 2} + c_{n - 3}$ with $c_{0} = 1$ , $c_{1} = 2$ , $c_{2} = 4$ , and the sequence continues $7, 13, 24, 44, 81$ . So $c_{7} = 81$ .

Regions cut by lines

Into how many regions can $n$ straight lines cut the plane? The most comes when the lines are in general position: no two parallel and no three through one point. Jakob Steiner answered the question in 1826; it also counts the pieces a large pizza yields to $n$ straight cuts.

Let $R_{n}$ be the number of regions. No lines leave the whole plane, so $R_{0} = 1$ ; one line makes two regions, two crossing lines make four, and three make seven, a triangle with three regions on its sides and three at its corners.

Add the lines one at a time. The $n$ th line crosses each of the $n - 1$ earlier lines once, since none is parallel to it, at $n - 1$ distinct points, since no three lines meet. Those points cut it into $n$ pieces, two rays and $n - 2$ segments, and each piece crosses one old region from side to side and splits it in two. So

R_{n} = R_{n - 1} + n for n \geq 1, R_{0} = 1

and the values run $1, 2, 4, 7, 11, 16, 22$ . Both assumptions were used: a line parallel to an old one would add only $n - 1$ regions, and one through an existing crossing would be cut into fewer pieces. That is why general position gives the maximum.

Guessing and proving

This recurrence unrolls to $1 + (1 + 2 + \dots + n)$ , but there is a second method, useful whenever unrolling leaves a sum you cannot evaluate: compute some values, guess a formula, and prove it by induction.

The values $1, 2, 4, 7, 11, 16, 22$ have differences $1, 2, 3, 4, 5, 6$ , whose own differences are constant. Constant second differences mark a quadratic, so try $R_{n} = A n^{2} + B n + C$ . From $R_{0} = 1$ , $C = 1$ ; from $R_{1} = 2$ , $A + B = 1$ ; from $R_{2} = 4$ , $4 A + 2 B = 3$ . So $A = B = \frac{1}{2}$ , and the guess is

R_{n} = \frac{n (n + 1)}{2} + 1

A formula fitted to three values proves nothing, but induction does. It holds at $n = 0$ . If $R_{n - 1} = \frac{(n - 1) n}{2} + 1$ , the recurrence gives $R_{n} = \frac{n^{2} - n + 2 n}{2} + 1 = \frac{n (n + 1)}{2} + 1$ , the formula for $n$ . So ten cuts divide a pizza into at most $56$ pieces, and a hundred lines cut the plane into $5051$ regions. The induction step is one line of algebra; the hard part is the guess.

Example. Draw $n$ circles so that every two cross at two points and no three pass through one point. Find the number of regions $C_{n}$ .

One circle makes $2$ regions. The $n$ th circle crosses each of the $n - 1$ others twice, at $2 (n - 1)$ distinct points, which cut it into $2 (n - 1)$ arcs when $n \geq 2$ , and each arc splits an old region in two. So $C_{n} = C_{n - 1} + 2 (n - 1)$ with $C_{1} = 2$ , giving $2, 4, 8, 14, 22$ . The second differences are constant, and fitting a quadratic to $n = 1, 2, 3$ gives the guess $C_{n} = n^{2} - n + 2$ . It holds at $n = 1$ , and if $C_{n - 1} = (n - 1)^{2} - (n - 1) + 2 = n^{2} - 3 n + 4$ , then $C_{n} = n^{2} - 3 n + 4 + 2 n - 2 = n^{2} - n + 2$ . The formula fails at $n = 0$ , giving $2$ for an empty plane, so the base case matters. It also shows why Venn diagrams stop at three circles: four circles make only $14$ regions, short of the $2^{4} = 16$ that four sets need.

Now you. The $n$ lines of a general position arrangement are themselves cut into pieces, segments and rays, by their crossing points. Let $s_{n}$ be the total number of pieces. Set up a recurrence, guess a closed form and prove it.

Answer

The $n$ th line is cut into $n$ pieces, and it splits one piece of each of the $n - 1$ old lines in two. So $s_{n} = s_{n - 1} + n + (n - 1) = s_{n - 1} + 2 n - 1$ with $s_{1} = 1$ . The values $1, 4, 9, 16$ suggest $s_{n} = n^{2}$ , and indeed $(n - 1)^{2} + 2 n - 1 = n^{2}$ . It can also be seen directly: each of the $n$ lines is cut into $n$ pieces.

Where both methods stall

Turn both methods on the bit string recurrence, $F_{n} = F_{n - 1} + F_{n - 2}$ . Unrolling replaces the largest index each time:

F_{n} = F_{n - 1} + F_{n - 2} = 2 F_{n - 2} + F_{n - 3} = 3 F_{n - 3} + 2 F_{n - 4} = 5 F_{n - 4} + 3 F_{n - 5}

The coefficients $1, 2, 3, 5$ are Fibonacci numbers again, and in general $F_{n} = F_{k + 1} F_{n - k} + F_{k} F_{n - k - 1}$ . That is a true identity, but as a solution it goes in a circle: reaching the initial conditions means carrying coefficients that are the very numbers being sought. Each substitution replaces one unknown by two, and what accumulates is a copy of the original problem.

Guessing fares no better. The differences of $0, 1, 1, 2, 3, 5, 8, 13$ are $1, 0, 1, 1, 2, 3, 5$ , the same sequence shifted, so they never settle and no polynomial fits. The growth looks exponential: consecutive ratios run $\frac{8}{5} = 1.6$ , $\frac{13}{8} = 1.625$ , $\frac{21}{13} \approx 1.615$ and $\frac{144}{89} \approx 1.618$ . But ${1.618}^{n}$ is not an integer, so the exact answer is subtler than a single power, and nothing in a table of integers suggests what it is.

The ratio is the clue. If a sequence growing like $r^{n}$ is to obey $F_{n} = F_{n - 1} + F_{n - 2}$ , substituting $r^{n}$ forces a condition on $r$ with two solutions, not one. The next lesson follows that clue to the characteristic equation, which solves every recurrence of this shape, and gives the Fibonacci numbers an exact formula in which $\sqrt{5}$ appears and then cancels to leave an integer every time.