CS 473 Notes on Solving Recurrence Relations1 Fun with Fibonacci numbersConsider the reproductive cycle of bees. Each male bee has a mother but no father; each femalebee has both a mother and a father. If we examine the generations we see the following family tree:♂♀♀♀♀♀♀♀♂♂♀♂♀♀♂♂♀♀♀♂♂♀♂♀♀♀♀♂♂♀♂♀♀♂♂♀♀♀♀♀♂♂♀♂♀♀♂♂♀♀♀♂♂♀We easily see that the number of ancestors in each generation is the sum of th e two numbersbefore it. For example, our m ale bee has three great-grandparents, two grandparents, and oneparent, and 3 = 2 + 1. The number of ancestors a bee has in generation n is defined by theFibonacci sequence; we can also see this by applying the rule of sum.As a second example, consider light entering two adjacent planes of glass:At any meeting surface (between the two panes of glass, or between the glass and air), the lightmay either reflect or continue straight through (refract). For example, here is the light bouncingseven times before it leaves the glass.In general, how many different paths can the light take if we are told that it bounces n times beforeleaving the glass?The answer to the question (in case you haven’t guessed) rests with the Fibonacci sequence.We can apply the rule of sum to the event E constituting all paths through the glass in n bounces.We generate two separate sub-events, E1and E2, illustrated in the following picture.1CS 473 Notes on Solving Recurrence RelationsSub-event E1: Let E1be the event that the first bounce is not at the boundary betweenthe two panes. In this case, the light must firs t bounce off the bottom pane, or else we aredealing with the case of having zero bounces (there is only one way to have zero bounces).However, the number of remaining paths after bouncing off the bottom pane is the same asthe number of paths entering through th e bottom pane and bouncing n − 1 bounces more.Entering through th e bottom pane is the same as entering through the top p ane (but flippedover), so E1is the number of paths of light bouncing n −1 times.Sub-event E2: Let E2be the event that the first bounce is on the boundary between thetwo panes. In this case, we consider the two options for the light after the first bounce: itcan either leave the glass (in which case we are dealing with the case of having one bounce,and there is only one way for the light to bounce once) or it can bounce yet again on the topof the upper pane, in which case it is equivalent to the light entering from the top with n −2bounces to take along its path.By the r ule of sum, we thus get the following recurr en ce relation for Fn, the number of pathsin which the light can travel with exactly n bounces. There is exactly one way for the light totravel with no bounces—straight through—and exactly two ways for the light to travel with onlyone bounce—off the bottom and off the m iddle. For any n > 1, there are Fn−1paths where thelight bounces off the bottom of the glass, and Fn−2paths where the light bounces off the middleand then off the top.F0= 1F1= 2Fn= Fn−1+ Fn−2Stump a professorWhat is the recurrence relation for three panes of glass? This question once stumped an anonymousprofessor1in a science discipline, but now you should be able to solve it with a bit of effort. Aren’tyou proud of your knowledge?1Not me! —Jeff2CS 473 Notes on Solving Recurrence Relations2 Sequences, sequence operators, and annihilatorsWe have sh own that several different p roblems can be expressed in terms of Fibonacci sequences,but we don’t yet know how to explicitly compute the nth Fibonacci number, or even (and moreimportantly) roughly how big it is. We can easily write a program to compute the n th Fibonaccinumber, but that doesn’t help us much here. What we really want is a closed form solution for theFibonacci recurrence—an explicit algebraic formula without conditionals, loops, or recursion.In order to solve recurrences like the Fibonacci recurr en ce, we first need to understand operationson infinite sequences of numbers. Although these sequences are formally defined as functions ofthe form A : IN → IR, we w ill write them either as A = ha0, a1, a2, a3, a4, . . .i when we want toemphasize the entire sequence2, or as A = haii when we want to emphasize a generic element. Forexample, the Fibonacci sequence is h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i.We can naturally define several sequence operators:We can add or subtract any two sequences:haii + hbii = ha0, a1, a2, . . .i + hb0, b1, b2, . . .i = ha0+ b0, a1+ b1, a2+ b2, . . .i = hai+ biihaii − hbii = ha0, a1, a2, . . .i − hb0, b1, b2, . . .i = ha0−b0, a1− b1, a2− b2, . . .i = hai− biiWe can multiply any sequence by a constant:c · haii = c · ha0, a1, a2, . . .i = hc · a0, c · a1, c · a2, . . .i = hc · aiiWe can shift any sequence to the left by removing its initial element:Ehaii = Eha0, a1, a2, a3, . . .i = ha1, a2, a3, a4, . . .i = hai+1iExample: We can u nderstand these operators better by looking at some specific examples, usingthe sequence T of powers of two.T = h20, 21, 22, 23, . . .i = h2iiET = h21, 22, 23, 24, . . .i = h2i+1i2T = h2 · 20, 2 · 21, 2 · 22, 2 · 23, . . .i = h21, 22, 23, 24, . . .i = h2i+1i2T − ET = h21− 21, 22− 22, 23− 23, 24− 24, . . .i = h0, 0, 0, 0, . . .i = h0i2.1 Properties of operatorsIt turns out that the distributive property holds for these operators, so we can rewrite ET −2T as(E −2)T . Since (E −2)T = h0, 0, 0, 0, . . .i, we say that the operator (E − 2) annihilates T , and wecall (E −2) an annihilator of T . Obviously, we can trivially annihilate any sequence by multiplyingit by zero, so as a technical matter, we do not consider multiplication by 0 to be an annihilator.What happen s wh en we apply the operator (E − 3) to our sequence T ?(E − 3)T = ET − 3T = h2i+1i − 3h2ii = h2i+1− 3 · 2ii = h−2ii = − TThe operator (E − 3) did very little to our sequ en ce T ; it just flipped the sign of each number inthe sequence. In fact, we will soon see that only (E − 2) will annihilate T , and all other simple2It really doesn’t matter whether we start a sequence with a0or a1or a5or even a−17. Zero is often a convenientstarting point for many recursively defined sequences, so we’ll usually start there.3CS 473 Notes on Solving Recurrence Relationsoperators will affect T in very minor ways. Thus, if we know how to annihilate