newtmet3

Recursive Sequences

Fibonacci Sequence

The Fibonacci sequence is discussed in many texts. Let us calculate the first few terms of that sequence. The recursive definition: , and .

Thus the third term is 2. The fourth term is 3. The fifth term is 5, and the sixth term is 8.

This sequence describes the number of (female-male) pairs of rabbits after n months, assuming that at the start (1^st month) a pair is "born" and that two months after any pair is born it begins to give birth, each month, to a female-male pair of rabbits. So in the 1^st month there is one pair, in the second month there is still one pair, and in the third month there are two pairs, the parent pair and the offspring pair. In the fourth month, there are 3 pairs: the original pair, first offspring pair, and second offspring pair from the original pair, and on and on.

It is not difficult to see that in the month, there will be the number of pairs from the month + the offspring of the number of pairs from the month. This gives the recursion formula.

Question 1 : Write out the recursion formula that describes the number pairs of of "bold rabbits" after n months. We begin with one pair of bold rabbits in the 1^st month. Each pair of bold rabbits begins to produce on a monthly basis new female-male pairs of bold rabbits beginning in the first (not the second) month after its birth. How many pairs of bold rabbits after 10 months?

End of Question

Question 2 : Write out the recursion formula that describes the number pairs of "shy rabbits" after n months. We begin with one pair of shy rabbits in the 1^st month. Each pair of shy rabbits begins to produce on a monthly basis new female-male pairs of shy rabbits beginning in the third (not the second) month after its birth. How many pairs of shy rabbits after 10 months?

End of Question

Exploration: The Fibonacci sequence and the golden ratio

On this page, we have a new option. Since we are interested in recursive sequences (which sometimes have more than 1 starting value) we may set initial values for our sequences. You may specify a sequence of initial terms, beginning with the start term by writing the comma-separated list in the field:

This means that the first few terms will be the ones you specify, and then the recursive rule will "kick in" at the end of your list. If you do not want to initialize, then write the word none in the Initial Values field. In that case, the sequence will begin with the start index. Remember that after a Reset, the 99 terms before the 0 index will be set to 0. So you may refer to terms before the 0 term if you wish. For example you might define a sequence by a(k) := a(k-1)+k from 1 to 10 without any initial terms if you wish. You get the "triangular numbers"

1 : 1
2 : 3
3 : 6
4 : 10
5 : 15
6 : 21
7 : 28
8 : 36
9 : 45
10 : 55

If we calculate the first 1000 terms we get an interesting graph. Is it a parabola?

Suppose we iterate the sequence a(k) := 1/(1+a(k-1)), or

starting at , for the first 50 terms. That is, enter the following values and be sure to press Enter in the precision field for 15 place precision, in case you have changed it.

and press You will see the values:

This sequence actually "converges" after 38 steps (at 15 place precision) to 0.618033988749894.

What is this number? We'll see it again shortly. Greek mathematicians knew about it, long before the invention of Calculus. As an interesting aside, you might like to change the iteration function to

(1.2)

Experiment with starting values different from 0 or 1. Watch what happens when the number of steps is a multiple of 3. What's going on here?

Question 3: Describe the behavior of this example with various starting values different from 0 or 1 in your own words. Why must we choose starting values different from 0 or 1?

End of Question

Hint: It is a good idea frequently to clear the MathEdit list and to clear the Graph2D. The information they store accumulates and eventually it will slow things down if you do not clear them. You clear these windows by pressing Reset, or by pressing one of the Clear Buttons.

Question 4 : Consider the recursive sequence

Calculate the first few terms of this sequence by hand. Guess what a function formula for the sequence might be (A function formula would express a(k) in terms of k alone.) Check your guess using the Iterate! button.

End of Question

Fibonacci Sequence: recursive definition

Back to Fibonacci. To calculate the terms of the Fibonacci sequence, we start by writing down the recursion relation in the definition fields. The sequence starts at 1 and continues to 20, since we want to report the numbers for 20 months.

First, you should press the Reset Button to start a new sequence. Then enter the sequence definition:

a(k) = a(k-1)+a(k-2)

From 1 to 20

Start values: 1,1

Since we want the first two terms to be equal to 1, initialize with start values 1,1 in the right field. The initial values are simply listed, separated by commas. If there are to be no initial values, you must type the word none.

Since these numbers will be very large, we will make all calculations Exact. This means that only fractions and integers will be calculated. No decimals. To do that, press the Exact button below the MathEdit:

(You may also do this elsewhere if you right click on any MathEdit and when you see the menu, select Actions, Read numbers as... Click Exact and dismiss the menu. The Command Fields and TextBoxes -- not TextLines -- have similar options). Later, when you want to do decimal calculations again, press the Double button:

The precision will be set to the value in the precision field..

We are ready to go. Press Iterate! and you see

The graph took off. It grows really fast. In fact, the 20th term is 6765. You see here the first few terms of the sequence. If you want to see how fast it's growing, calculate , the 49th term. It is 7,778,742,049 which is close to eight billion. Imagine if your savings account accumulated interest at that rate!

Now we want to make a decimal calculation. press the Double button:

Question 5: Suppose you found a savings bank that offered 61% interest on your account each year. Suppose further that you deposited $1.00 in the year 2001 into that account. Then in the year 2002, you would have $1.61.

Not rocket science. We'll get to that later in the book. How much would you have in 2003? Well it would be $1.61 + 61% of 1.61 = 1.61*1.61 or 1.61^2 dollars. Roughly $2.59 Hmm... Well, let's see how much we'd have in 2051, after the 50^th year.

End of Question

Construct the recursive sequence:

a(k) = 1.61*a(k-1)

From 1 to 50

Start values: 1

Set the precision to 15 and iterate!

What is in your account in 2050, rounded to the nearest cent? The number reported should be: 1.3629123457907438e10 where the "e10" means multiply by 10 billion. Do you remember the 49th term of the Fibonacci sequence: ?

It was 7, 778, 742, 049. Close to 8 Billion.

What is more surprising, there is a number n such that or which the Fibonacci sequence is greater than the amount of principal in our fictitious account after n years. Thereafter, the Fibonacci sequence stays larger than the principal in our account.

Question 6: Find the smallest n for which this is true.

End of Question

Now, press Reset and generate the first 60 terms of the Fibonacci sequence. Be sure to press the exact button before you do. You will see the first 60 terms of the Fibonacci sequence.

1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8
7 : 13
8 : 21
9 : 34
10 : 55
11 : 89
12 : 144
13 : 233
14 : 377
15 : 610
16 : 987
17 : 1597
18 : 2584
19 : 4181
20 : 6765
21 : 10946
22 : 17711
23 : 28657
24 : 46368
25 : 75025
26 : 121393
27 : 196418
28 : 317811
29 : 514229
30 : 832040
31 : 1346269
32 : 2178309
33 : 3524578
34 : 5702887
35 : 9227465
36 : 14930352
37 : 24157817
38 : 39088169
39 : 63245986
40 : 102334155
41 : 165580141
42 : 267914296
43 : 433494437
44 : 701408733
45 : 1134903170
46 : 1836311903
47 : 2971215073
48 : 4807526976
49 : 7778742049
50 : 12586269025
51 : 20365011074
52 : 32951280099
53 : 53316291173
54 : 86267571272
55 : 139583862445
56 : 225851433717
57 : 365435296162
58 : 591286729879
59 : 956722026041
60 : 1548008755920

Next, press Reset, then press the Double button . We will now generate the sequence as decimals (doubles). Thus, press Iterate and you will see the decimal version of the Fibonacci sequence.

What we will do now is generate the sequence of ratios a(n)/a(n+1) as n varies from 1 to 59. We do this principally to show you how to generate a new sequence from an old one, and secondarily to show you one of the many surprises that the Fibonacci sequence holds. We will generate the sequence of ratios as a b-sequence

So enter the following values in the field defining the sequence:

We are allowed to define this sequence in terms of "future" values of the Fibonacci sequence because the values of the Fibonacci sequence are stored in the sequence until we Reset. Now press the b-sequence button, and you see:

Golden Rectangle

The graph tells us that this sequence of ratios rapidly "stabilized." In mathematical terms, it goes quickly to a limit. This is what it means for the graph to flatten out this way. But look at the numbers in the Math Edit field. The almost constant value these numbers approach is the Golden Ratio," a ratio that defines a shape that frequently found itself in Greek architecture. It is the shape of the rectangle below.

The Greeks thought of ratios as the "shapes" of rectangles (and not as numbers). This rectangle has the remarkable property that the shape of the original rectangle is the same as the shape of the rectangle obtained by removing the large yellow square on the right:

This leads to an infinite process that intrigued the Greeks - and prevented them from formulating the modern notion of irrational number.

Why does the sequence of Fibonacci ratios approach the Golden ratio? Use the length of the tiny rectangle in the upper left hand corner of the picture above as a unit length, and measure the lengths of the short side each of the rectangles that appears in the picture, starting with the square of length 1 and proceeding to the 2 x 1 rectangle in the upper left corner, then the 3 x 2 rectangle, and so on, and you will see that these lengths, in increasing order, form the terms of the Fibonacci sequence. Now as this process is continued the "shapes" of these rectangles approach (as a limit in a sense) the "shape" of the Golden rectangle. There is an intuitive reason to think that this is so. Can you think of it?

Question 7: Answer the following question. Define "Quasi-Fibonacci Sequences" in the same way we defined Fibonacci sequences, except that the first two terms are allowed to be:

1) 1, 2

2) 1, 5

3) 1, 10

For each of these, look at the sequence of ratios a(n)/a(n+1) as we did for the Fibonacci sequence. In each case, show what this sequence of ratios seems to approach. What is the pattern?

End of Question

We are now ready to study Newton's Method for solving equations in terms of recursive sequences. So go to the next page for that discussion.