Linear Algebra/Topic: Linear Recurrences

Linear Algebra Topic: Linear Recurrences Topic: Stable Populations Appendix In 1202 Leonardo of Pisa, also known as Fibonacci, posed this problem. A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the second month on becomes productive? This moves past an elementary exponential growth model for population increase to include the fact that there is an initial period where newborns are not fertile. However, it retains other simplyfing assumptions, such as that there is no gestation period and no mortality. The number of newborn pairs that will appear in the upcoming month is simply the number of pairs that were alive last month, since those will all be fertile, having been alive for two months. The number of pairs alive next month is the sum of the number alive current month and the number of newborns. The is an example of a recurrence relation (it is called that because the values of are calculated by looking at other, prior, values of ). From it, we can easily answer Fibonacci's twelve-month question. FibonacciThe sequence of numbers defined by the above equation (of which the first few are listed) is the Fibonacci sequence. The material of this chapter can be used to give a formula with which we can can calculate without having to first find , , etc. For that, observe that the recurrence is a linear relationship and so we can give a suitable matrix formulation of it. Then, where we write for the matrix and for the vector with components and , we have that . The advantage of this matrix formulation is that by diagonalizing we get a fast way to compute its powers: where we have , and the -th power of the diagonal matrix is the diagonal matrix whose entries that are the -th powers of the entries of . The characteristic equation of is . The quadratic formula gives its roots as and . Diagonalizing gives this. Introducing the vectors and taking the -th power, we have We can compute from the second component of that equation. Notice that is dominated by its first term because is less than one, so its powers go to zero. recurrenceIn general, a linear recurrence relation has the form (it is also called a difference equation). homogeneousThis recurrence relation is homogeneous because there is no constant term; i.e, it can be put into the form . orderThis is said to be a relation of order . initial conditionsThe relation, along with the initial conditions , ..., completely determine a sequence. For instance, the Fibonacci relation is of order and it, along with the two initial conditions and , determines the Fibonacci sequence simply because we can compute any by first computing , , etc. In this Topic, we shall see how linear algebra can be used to solve linear recurrence relations. First, we define the vector space in which we are working. Let be the set of functions from the natural numbers to the real numbers. (Below we shall have functions with domain , that is, without , but it is not an important distinction.) Putting the initial conditions aside for a moment, for any recurrence, we can consider the subset of of solutions. For example, without initial conditions, in addition to the function given above, the Fibonacci relation is also solved by the function whose first few values are , , , and . The subset is a subspace of . It is nonempty because the zero function is a solution. It is closed under addition since if and are solutions, then And, it is closed under scalar multiplication since We can give the dimension of . Consider this map from the set of functions to the set of vectors . Problem 3 shows that this map is linear. Because, as noted above, any solution of the recurrence is uniquely determined by the initial conditions, this map is one-to-one and onto. Thus it is an isomorphism, and thus has dimension , the order of the recurrence. So (again, without any initial conditions), we can describe the set of solutions of any linear homogeneous recurrence relation of degree by taking linear combinations of only linearly independent functions. It remains to produce those functions. For that, we express the recurrence with a matrix equation. In trying to find the characteristic function of the matrix, we can see the pattern in the case and case. Problem 4 shows that the characteristic equation is this. We call that the polynomial "associated" with the recurrence relation. (We will be finding the roots of this polynomial and so we can drop the as irrelevant.) If has no repeated roots then the matrix is diagonalizable and we can, in theory, get a formula for as in the Fibonacci case. But, because we know that the subspace of solutions has dimension , we do not need to do the diagonalization calculation, provided that we can exhibit linearly independent functions satisfying the relation. Where , , ..., are the distinct roots, consider the functions through of powers of those roots. Problem 2 shows that each is a solution of the recurrence and that the of them form a linearly independent set. So, given the homogeneous linear recurrence (that is, ) we consider the associated equation . We find its roots , ..., , and if those roots are distinct then any solution of the relation has the form for . (The case of repeated roots is also easily done, but we won't cover it here— see any text on Discrete Mathematics.) Now, given some initial conditions, so that we are interested in a particular solution, we can solve for , ..., . For instance, the polynomial associated with the Fibonacci relation is , whose roots are and so any solution of the Fibonacci equation has the form . Including the initial conditions for the cases and gives which yields and , as was calculated above. We close by considering the nonhomogeneous case, where the relation has the form for some nonzero . As in the first chapter of this book, only a small adjustment is needed to make the transition from the homogeneous case. This classic example illustrates. In 1883, Edouard Lucas posed the following problem. In the great temple at Benares, beneath the dome which marks the center of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty four disks of pure gold, the largest disk resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the disks from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disk at a time and that he must place this disk on a needle so that there is no smaller disk below it. When the sixty-four disks shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dusk, and with a thunderclap the world will vanish.(Translation of De Parvill 1884 from Ball 1962.) How many disk moves will it take? Instead of tackling the sixty four disk problem right away, we will consider the problem for smaller numbers of disks, starting with three. To begin, all three disks are on the same needle. x300px|center After moving the small disk to the far needle, the mid-sized disk to the middle needle, and then moving the small disk to the middle needle we have this. x300px|center Now we can move the big disk over. Then, to finish, we repeat the process of moving the smaller disks, this time so that they end up on the third needle, on top of the big disk. So the thing to see is that to move the very largest disk, the bottom disk, at a minimum we must: first move the smaller disks to the middle needle, then move the big one, and then move all the smaller ones from the middle needle to the ending needle. Those three steps give us this recurrence. We can easily get the first few values of . We recognize those as being simply one less than a power of two. To derive this equation instead of just guessing at it, we write the original relation as , consider the homogeneous relation , get its associated polynomial , which obviously has the single, unique, root of , and conclude that functions satisfying the homogeneous relation take the form . That's the homogeneous solution. Now we need a particular solution. Because the nonhomogeneous relation is so simple, in a few minutes (or by remembering the table) we can spot the particular solution (there are other particular solutions, but this one is easily spotted). So we have that— without yet considering the initial condition— any solution of is the sum of the homogeneous solution and this particular solution: . The initial condition now gives that , and we've gotten the formula that generates the table: the -disk Tower of Hanoi problem requires a minimum of moves. Finding a particular solution in more complicated cases is, naturally, more complicated. A delightful and rewarding, but challenging, source on recurrence relations is Graham Knuth Patashnik 1988., For more on the Tower of Hanoi, Ball 1962 or Gardner 1957 are good starting points. So is Hofstadter 1985. Some computer code for trying some recurrence relations follows the exercises. Exercises Problem 1 Solve each homogeneous linear recurrence relations. <li> <li> <li> Problem 2exer:SolvePartRecurSoltn Give a formula for the relations of the prior exercise, with these initial conditions. <li> , <li> , <li> , , . Problem 3exer:SeqToRnLinMap Check that the isomorphism given between and is a linear map. It is argued above that this map is one-to-one. What is its inverse? Problem 4exer:CharEqnIsDeter Show that the characteristic equation of the matrix is as stated, that is, is the polynomial associated with the relation. (Hint: expanding down the final column, and using induction will work.) Problem 5exer:SoltnsLinRecur Given a homogeneous linear recurrence relation , let , ..., be the roots of the associated polynomial. <li> Prove that each function satisfies the recurrence (without initial conditions). <li> Prove that no is . <li> Prove that the set is linearly independent. Problem 6 (This refers to the value given in the computer code below.) Transferring one disk per second, how many years would it take the priests at the Tower of Hanoi to finish the job? Computer Code This code allows the generation of the first few values of a function defined by a recurrence and initial conditions. It is in the Scheme dialect of LISP (specifically, it was written for A. Jaffer's free scheme interpreter SCM, although it should run in any Scheme implementation). First, the Tower of Hanoi code is a straightforward implementation of the recurrence. (define (tower-of-hanoi-moves n) (if (= n 1) 1 (+ (* (tower-of-hanoi-moves (- n 1)) 2) 1) ) ) (Note for readers unused to recursive code: to compute , the computer is told to compute , which requires, of course, computing . The computer puts the "times " and the "plus " aside for a moment to do that. It computes by using this same piece of code (that's what "recursive" means), and to do that is told to compute . This keeps up (the next step is to try to do while the other arithmetic is held in waiting), until, after steps, the computer tries to compute . It then returns , which now means that the computation of can proceed, etc., up until the original computation of finishes.) The next routine calculates a table of the first few values. (Some language notes: '() is the empty list, that is, the empty sequence, and cons pushes something onto the start of a list. Note that, in the last line, the procedure proc is called on argument n.) (define (first-few-outputs proc n) (first-few-outputs-helper proc n '()) ) ; (define (first-few-outputs-aux proc n lst) (if (< n 1) lst (first-few-outputs-aux proc (- n 1) (cons (proc n) lst)) ) ) The session at the SCM prompt went like this. >(first-few-outputs tower-of-hanoi-moves 64) Evaluation took 120 mSec (1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 1073741823 2147483647 4294967295 8589934591 17179869183 34359738367 68719476735 137438953471 274877906943 549755813887 1099511627775 2199023255551 4398046511103 8796093022207 17592186044415 35184372088831 70368744177663 140737488355327 281474976710655 562949953421311 1125899906842623 2251799813685247 4503599627370495 9007199254740991 18014398509481983 36028797018963967 72057594037927935 144115188075855871 288230376151711743 576460752303423487 1152921504606846975 2305843009213693951 4611686018427387903 9223372036854775807 18446744073709551615) This is a list of through . (The mSec came on a 50 mHz '486 running in an XTerm of XWindow under Linux. The session was edited to put line breaks between numbers.) /Solutions/ References W.W. Ball Mathematical Recreations and Essays MacMillan 1962 (revised by H.S.M. Coxeter). De Parville La Nature I 1884 285-286 Paris. Martin Gardner Mathematical Games: About the remarkable similarity between the Icosian Game and the Tower of Hanoi Scientific American 150-154 May. 1957. Ronald L. Graham Donald E. Knuth Oren Patashnik Concrete Mathematics Addison-Wesley 1988. Douglas R. Hofstadter Metamagical Themas:~Questing for the Essence of Mind and Pattern Basic Books 1985. Linear Algebra Topic: Linear Recurrences Topic: Stable Populations Appendix