Chapter 16

Recurrence Relations

Let us begin our discussion by considering the following counting problem.

Example 16.1 Figure 16.1 shows a 9-step staircase. A boy wishes to climb the staircase up to the highest step. Suppose that each time, the boy either climbs up one step or two steps. How many ways are there for the boy to climb the staircase?

Discussion and Solution We have learnt a number of principles and techniques to solve some counting problems. Naturally, we would like to try and see if any of these can be applied to solve the above problem without listing all the possible ways. After pondering for a while, however, we may be doubtful about it. Splitting into cases look daunting and so we will not use the Addition Principle. There does not seem to be any fixed set of stages from the ground to Step 9. That eliminates the Multiplication Principle. No bijection is obvious. We cannot easily find sets A_i,i = 1,2,...,n, such that either where A is the set to be counted. Thus, the General Principle of Inclusion and Exclusion is not good here either. Is there any new idea available to tackle the problem?

The number of steps of the staircase given in the problem, i.e. 9, may be a little too big. Why don’t we try some simpler cases to gain some “feeling” about the problem?

When the staircase consists of 1, 2 and 3 steps, the ways of climbing the staircase are shown in Figure 16.2, and the number of ways is respectively 1, 2 and 3, as well.

Figure 16.1

Figure 16.2

Figure 16.3

How about a 4-step staircase? Will the number be “4” also? No! The number of ways is now “5” and the 5 different ways of climbing are shown in Figure 16.3.

Let us hold the 4-step case for a while and analyse why we have “5” ways here. We begin by asking, “What can the boy do for his first move?” By assumption, he can cover 1 step or 2 steps. We now split our consideration into two cases accordingly.

 

(i) Suppose the first move covers 1 step. Then there are 3 steps left. How many ways are there to climb the remaining 3 steps? This question is crucial! Can we link it to the 3-step case? There are 3 ways to climb the 3-step staircase as shown in Figure 16.2(iii). Now, if we follow each of these 3 ways to climb the remaining 3 steps of our 4-step staircase, we will get 3 different ways (and no more) to climb the 4-step staircase as shown in (1)–(3) of Figure 16.3.

(ii) Suppose the first move covers 2 steps. Then there are 2 steps left. There are 2 ways to climb the 2-step staircase as shown in Figure 16.2(ii). If we follow each of these 2 ways to climb the remaining 2 steps of our 4-step staircase, we will get 2 different ways (and no more) to climb the 4-step staircase as shown in (4)–(5) of Figure 16.3.

It is now clear that by applying (AP), we will have 3 + 2, i.e. 5 different ways to climb the 4-step staircase.

What have we learnt from the above analysis? We have learnt that the problem of bigger size (4-step) depends on the same problem but of smaller size (3-step and 2-step), and the solution of the problem of bigger size can be obtained from the solutions of the same problem but of smaller size. This is a “new” idea for us. It works for “4-step”. Does it work for any “n-step”?

Now, given any integer n ≥ 3, for convenience, let us denote by a_n, the number of ways to climb an n-step staircase. Thus, our previous records show that a₁ = 1, a₂ = 2, a₃ = 3 and a₄ = 5. Indeed, we have just witnessed that a₄ = a₃ + a₂ and you may also check that a₃ = a₂ + a₁. Can we get a similar “equality” for a_n?

Imagine now the boy is to climb an n-step staircase. His first move can cover, by assumption, either 1 step or 2 steps. Divide our consideration into two cases as follows.

Case (1) The first move covers 1 step.

Then there are n – 1 steps left. How many ways are there to climb these remaining n – 1 steps? By definition, there are a_{n – 1} ways.

Case (2) The first move covers 2 steps.

Then there are n – 2 steps left. How many ways are there to climb these remaining n – 2 steps? By definition, there are a_{n – 2} ways.

Combining the results of these two cases by applying (AP), we conclude that a_n = a_{n – 1} + a_{n – 2} for n ≥ 3.

The original problem asks for the determination of a₉. We shall evaluate it from the general result “a_n = a_{n – 1} + a_{n – 2}” together with some “initial” values (for instance, a₁ = 1,a₂ = 2,a₃ = 3 and a₄ = 5). Applying our general result successively, we have:

and finally

as required.

In the example above, we obtain a sequence of numbers, namely,

and in general, a_n = a_{n – 1} + a_{n – 2}. The relation a_n = a_{n – 1} + a_{n –2}which expresses a_n, for a general n, in terms of some preceding numbers in the sequence (in this case, a_{n – 1} and a_{n – 2}) is called a recurrence relation. As we have witnessed just now, deriving a recurrence relation is a way of solving a class of counting problems.

The sequence of numbers 1,2,3, 5,8,... as given above is called the sequence of Fibonacci numbers, named after the Italian mathematician Leonardo Fibonacci (1170–1250), a great mathematical innovator during the Middle Ages. Fibonacci was born in Pisa. Around 1192, his father was the director of the Pisan trading colony in Algeria. Hoping that his son would become a businessman, the father brought Fibonacci to Algeria to study mathematics with an Arab master. A few years later, sent by the father on business trips, Fibonacci had several occasions to visit places such as Egypt, Syria, Greece and Sicily, where he took the opportunity to learn various numerical systems and methods of calculation. Around 1200, after returning to Pisa, Fibonacci started to write a book entitled “Liber abbaci” (Book of the Abacus). The book was completed in 1202. In this book, one finds the following counting problem about rabbits.

If we write F_n to denote the number of pairs of rabbits at the end of the nth month, then one can see from Figure 16.4 that F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, etc. Indeed, it can be shown (see Problem 16.5) in general that F_n = F_{n – 1} + F_{n – 2} for all n ≥ 3, which is essentially the same as the recurrence relation a_n = a_{n –1} + a_{n – 2}that we derived in Example 16.1. Note that in Example 16.1, our initial values are a₁ = 1 and a₂ = 2 while in Fibonacci’s problem, we have F₁ = Fmove is enough an₂ = 1.

Statue of Fibonacci in Pisa,

Figure 16.4

Figure 16.5

Let us proceed to consider our second example.

Example 16.2 A tower of 8 circular discs of decreasing diameters is stacked on one of the three vertical pegs as shown in Figure 16.5.

The task is to transfer the entire tower to another peg by a number of moves subject to the following rules:

(i) each move carries exactly one disc; and

(ii) no disc can be placed on a smaller one.

What is the minimum number of moves required to accomplish the task?

Discussion and Solution Again, for convenience, let b_n denote the minimum number of moves required to transfer the entire tower with n discs from one peg to another. The problem is to find the value of b_n.

From the experience we have gained in the preceding example, let us first consider some of the simpler cases. When n = 1, it is clear that one move is enough and so b₁ = 1. When n = 2, a bit of effort will show that two moves are not enough, whereas the following sequence of moves, as shown in Figure 16.6, shows that three moves will do the job. Thus, b₂ = 3.

Figure 16.6

Figure 16.7

Consider now the case when n = 3. The sequence of moves shown in Figure 16.7 shows that seven moves are enough to accomplish the task.

Is “7” the minimum number of moves required? As shown in Figure 16.7(a)-(d), before the largest disc can be moved to another peg, we have to transfer the entire tower of two smaller discs to a peg. We know that this requires b₂ (= 3) moves. Next, we move the largest disc to the bottom of the only “empty” peg as shown in Figure 16.7(d), (e). Finally, we have to transfer the entire tower of two smaller discs and place it on the largest disc (Figure 16.7(e)–(h)), and this requires another b₂ (= 3) moves. Thus we need at least b₂ + 1 + b₂, i.e. 2b₂ +1 (= 7) moves to accomplish the task. This fact, together with the sequence of seven moves shown in Figure 16.7, shows that b₃ = 7.

In the discussion above, we have found that b₃ = 7. Indeed, we have obtained the relation b₃ = 2b₂ + 1, an instance of a recurrence relation. The reader may easily check that b₂ = 2b₁ + 1 as well. Can we generalise this relation? More precisely, given n ≥ 2, is it true that b_n = 2b_n–1 + 1?

Imagine now we have a tower of n (≥ 2) discs stacked on one of the 3 pegs (say peg (a) as shown in Figure 16.8 and we wish to evaluate b_n, the minimum number of moves needed to transfer the entire tower of n discs to another peg.

In the process of transferring the entire tower, it is clear (by rule (ii) ) that at a certain stage, we must arrive at the situation, as shown in Figure 16.9, where the entire tower of n – 1 smaller discs has been transferred to another peg (say peg (c)). This is so because only then we can finally move the largest disc from the original peg to the bottom of another peg (in this case, peg (b)). What is the minimum number of moves needed to transfer the entire tower of n – 1 smaller discs from peg (a) to peg (c)? By definition, this number is b_n–1.

Figure 16.8

Figure 16.9

Figure 16.10

After moving the largest disc from peg (a) to peg (b) as shown in Figure 16.10, our final job is to transfer the entire tower of discs at peg (c) on to the top of the largest disc at peg (b). By definition, this number is b_n–1 again.

Summing up, we see that the minimum number of moves that are needed for the whole task is b_n–1 + 1 + b_n–1. Accordingly, by the definition of b_n, we have

another example of a recurrence relation. Let us return to the problem in Example 16.2, where we were asked to evaluate b₈. Based on the result that bThe problem described i₁ = 1, by applying our recurrence relation successively, we obtain

and finally, b₈ = 255, as required.

Observe that we actually have a nice single formula for the value b_n:

and in general, b_n = 2ⁿ – 1 (see Problem 16.9).

The problem described in Example 16.2 is known as the Tower of Hanoi. Why is Hanoi, the capital of Vietnam, associated with this problem? Well, this could have something to do with these two facts: the inventor of the problem was French and the problem was introduced at a time when France began her military involvement in Vietnam.

According to Andreas M. Hinz (in his paper, The Tower of Hanoi, published in 1999), the picture shown in Figure 16.11 is of the cover of a box which was found in Paris in 1883. Looking at the picture closely, we find several items therein which are related to tropical Asia, and in particular, Vietnam. These include a Vietnamese, two sites in Vietnam, viz. Tonkin and Annam, and the title “La Tour d’Hanoi”. Two special names also appear in the picture. These are Professor N. Claus (de Siam) and his College Li-Sou-Stian. According to the French mathematician de Parville, the two names above are anagrams for Professor Lucas (d’Amiens), the inventor of this problem, and his College Saint Louis. As Lucas was Agrege de l’Universite, it is believed that he is the one carrying the ten-level tower in the picture.

Francois Edouard Anatole Lucas (1842–1891) was a French mathematician who did much work in Number Theory, Recurrent Sequences and Recreational Mathematics. In the “pre-computer age”, Lucas was the last “largest prime number record holder” (2¹²⁷ – 1). He gave a closed-form expression for the Fibonacci numbers as follows:

Figure 16.11

Edouard Lucas (1842–1891)

The associated Lucas sequence was named after him: 2, 1, 3, 4, 7, 11, 18, 29,.... Can you see the recurrence relation that generates the Lucas sequence?

So far, we have discussed two counting problems and introduced a way, called the technique of recursion or the method of recurrence relation, to solve them. The technique of recursion amounts to a derivation of a recurrence relation (such as a_n = a_{n – 1} + a_n–2 and a_n = 2a_n–1 + 1) which expresses the required number of ways, a_n (when the size of the problem is n), in terms of the numbers of ways when the sizes for the problem are smaller than n (such as a_{n – 1}, a_n–2). It is often very easy to find the number of ways a₁, a₂, a₃ when the sizes for the problem are very small. With these initial values, the recurrence relation that has been established earlier will generate successively the values of the next a_n’s. From a computational standpoint, solving a counting problem by the technique of recursion can sometimes be more useful and efficient than by a formula, especially when we need to compute all the values a₁, a₂,...,a_n up to some point.

Exercise

16.1  A man takes a bank loan of $300,000 that charges 1% interest per year in the first year, 2% interest per year in the second year and 5% interest per year from the third year. Interest is compounded yearly. The man pays $X each year to service the loan. You may assume that the interest is computed just before the man's yearly payment.

(i) Write a recurrence relation and initial conditions for b_n, the balance of the loan in dollars at the end of n years.

(ii) What should $X, to the nearest dollar, be if the man intends to complete repayment at the end of 10 years?

16.2  Suppose that you have an unlimited supply of red, blue, yellow and green counters, which are indistinguishable except for colour. Write a recurrence relation and initial conditions for the number s_n of ways to stack n counters with no two consecutive green counters.

16.3  There are n lines in a plane. Every pair of lines intersect but no three meet at a common point. How many regions is the plane divided into by these n lines?

16.4  There are n circles in a plane. Every pair of circles intersect at exactly two points but no three meet at a common point. How many regions is the plane divided into by these n circles?

16.5  Let F_n denote the number of pairs of rabbits at the end of the nth month, where n ≥ 1, as given in Fibonacci’s problem of rabbits. Show that F_n = F_n–1 + F_n–2 for n ≥ 3.

16.6  Find a recurrence relation and initial conditions for the number of binary sequences of length n with no consecutive 0’s.

16.7  Find a recurrence relation and initial conditions for the number of binary sequences of length n having no k consecutive 0’s.

16.8  Find a recurrence relation and initial conditions for the number of binary sequences of length n that do not contain the sequence 101.

16.9  Let b_n denote the minimum number of moves as defined in Example 16.2. Show that b_n = 2ⁿ– 1 for all n ≥ 1.

16.10  A permutation a₁a₂ … a_n of is called a derangement of if a_i ≠ i for each i = 1,2,...,n (see Chapter 14). For n ≥ 3, let D_n be the number of derangements of . Show that