Recursive Sequences - Mathematics

1 Chapter 1 Recursive SequencesWe have described a sequence in at least two different ways: a list of real numbers where there is a first number, a second number, and so on. Weare interested in infinite Sequences , so our lists do not end. Examples aref1; 2; 3; 4; 5; 6; : : :gorf2; 4; 8; 8; 8; 8; 8; 8; 16; : : :g. The Sequences we saw in the last section we were usu-ally able to describe by some formula. This is not always the case. afunctionaWN!Rwhere we denoted the output One example wouldbeanDn. Others areanD2n,anD1=n. Any function that is defined on the set ofwhole numbers gives us is yet another way to describe a sequence .

2 This process is known is the process of choosing a starting term and repeatedly applying the sameprocess to each term to arrive at the following term. Recursion requires that you know thevalue of the term or terms immediately before the term you are trying to Recursive formula always has two parts:1. the starting value for the first terma0;2. the recursion equation foranas a function ofan 1(the term before it.)Example the sequence given byanD2an 1C1witha0D4. The recursionfunction (orrecursion equation) tells us how to finda1,a2, and so isa10?

3 Here the problem is that we have to finda9in order to finda10, but to finda9we needa8, but to finda8we needa7, and so [Fibonacci sequence ] Consider the following recursion 1 CFn 2;F0D1; F1D1:12 CHAPTER 1. Recursive SEQUENCESF2DF1CF0D2F3DF2CF1D3In fact, it is easier to list these out in a list by just adding the previous two terms to get thenext ; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610; 987; 1597; : : :gThe Fibonacci sequence has a long history in Mathematics and you can find out moreabout it online at any number of websites.

4 The Fibonacci sequence is named after the13th-century Italian mathematician known as Fibonacci, who used it to solve a problemconcerning the breeding of rabbits. This sequence also occurs in numerous applications inplant Write Recursive equations for the sequencef5; 7; 9; 11; : : Write Recursive equations for the sequencef2; 4; 8; 16; : : Write Recursive equations for the sequencef1; 2; 6; 24; 120; 720; : : Write Recursive equations for the sequencef2; 3; 6; 18; 108; 1944; 209952; : : :gExercises1. What is the 5th term of the Recursive sequence defined as follows:a1D5,anD3an 1?

5 2. What is the 5th term of the Recursive sequence defined as follows:a1D2,anD2an 1 1?3. What is the 1st term of a Recursive sequence in whichanD4an 1, ifa4D192?4. Write Recursive equations for the sequencef5; 11; 17; 23; : : Write Recursive equations for the sequencef3; 6; 12; 24; : : Write Recursive equations for the sequencef2; 4; 16; 256; 65536; : : Write Recursive equations for the sequencef2; 6; 14; 30; 62; : : Write Recursive equations for the sequencef3; 4; 7; 11; 18; 29; : : Write Recursive equations for the sequencef6561; 81; 9; 3.

6 : : Write the first five terms of the sequence in whicha1D1andanD2an 1 Write the first five terms of the sequence in whicha1D2andanD5an 1 [Depreciation] Consider a situation in which the value of a car depreciates10% per year. If the car is originally valued at $36,000, the following year it is worth 90%of $36,000, or $32,400. After another year, the value is 90% of $32,400, or $29,160. If wewrite the decreasing values as a list: 36,000, 32,400, 29,160.. we have written a sequence - a sequence where each term depends on the value of the preceding term - a recursivesequence:anD0:9an 114 UK Mathematics LIMITS OF Recursive SEQUENCES3 Two simple examples of Recursive definitions are for arithmetic Sequences and geomet -ric Sequences .

7 An arithmetic sequence has a common difference, or a constant differencebetween each 1 Cdoran an 1Dd:The common difference,d, is analogous to the slope of a line. In this case it is possible tofind a formula for thenth term directly. This simplifies finding say the 42nd geometric sequence has a common an 1oranan 1Dr:Again, in this case it is relatively easy to find a formula for thenth , there are Sequences that can be defined recursively, analytically, and those that canbe defined in both Sequences are sometimes called adifferenceequations.

8 The Recursive se-quence in Example 1 is called a first-order difference equation becauseandepends onjust the preceding terman 1, whereas the Fibonacci sequence is a second-order differenceequation becauseFndepends on the two preceding termsFn 1andFn 2. The generalfirst-order difference equation is of the formanC1Df .an/wherefis some is it called a difference equation? The word difference comes from the fact that suchequations are often formulated in terms of the difference between one term and the next: anDanC1 an. The equation be written as follows:anC1.

9 An/wheref . Limits of Recursive SequencesIn our previous discussion, we learned how to find limn!1anwhenanis given explicitly asa function ofn. How do you find such a limit whenanis defined we define a first-order sequencefangrecursively, we expressanC1in terms ofanand specify a value fora1. We can then compute successive values ofan, which mightallow us to guess the limit if it exists. In some cases (as in the next example), we can find asolution of the recursion and then determine the limit (if it exists).Example ; 2; : : : ; 6whenanC1D14anC34witha1D2.

10 Find aMA 114 UK Mathematics Department4 CHAPTER 1. Recursive Sequences solution of the recursion, and then take a guess at the limiting behavior of the :25a3D14a2C34D1716D1:0625a4D14a3C34D6564 D1:015625a5D14a4C34D257256D1:00390625a6D 14a5C34D10251024D1:0009765625 There seems to be a pattern, namely, that the denominators are powers of 4 and thenumerators are just 1 larger than the denominators. We will tryanD4n 1C14n 1and checkwhether this is indeed a solution of the , we need to check the initial This agreeswith the given initial condition.