In this unit we take a deeper look into Fibonacci sequences. We see situations other than rabbits that produce these numbers; a related set of numbers – the Lucas numbers; and the use of quadratic equations to find a general term of a sequence of numbers that is generated by a recurrence relation similar to Fibonacci’s.

- find the smaller Fibonacci numbers by using the recurrence relation
- find te initial members of other sequences that can be found using a recurrence relation like the Fibonacci one
- find the general term of these recurrence relations using quadratic equations
- understand the concept of a limit of a sequence
- find various limits relating to sequences

This unit extends the work of Fibonacci I, Level 5 and What Happens on Average? Algebra, Level 5. As such it takes a deeper look at the Fibonacci sequence and the recurrence relation from which it comes.

Recurrence relations are an important tool especially in discrete areas of mathematics and computer science. They provide ways to count things that are not open to counting by other routes. We provide a little of the theory that can be used to solve some simpler kinds of recurrence relations.

You will find that all of the theory you will need is in the Teachers’ Notes that come at the start of each session. However, you will find a great deal of background reading both in the books below and in the web sites that we have listed. They might provide some additional work for your more able students.

Useful web sites are

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/

http://turnbull.mcs.st-and.ac.uk/~history/HistTopics/

www.mcs.surrey.ac.uk/Personal/R.Knott/;

www.mathforum.com/dr.math/.

You will find some extra material to that we have provided here in Chapter 3 in each of:

P. Hilton, D. Holton and J. Pedersen, Mathematical Reflections, Springer-Verlag, New York, 1997.

P. Hilton, D. Holton and J. Pedersen, Mathematical Vistas, Springer-Verlag, New York, 2002.

### Prerequisites

You won’t be able to do this unit in full unless your class has a good understanding of how to solve quadratic equations and how to solve simultaneous linear equations.

It is essential that the students have already done the units Fibonacci I, Level 5 and What Happens on Average?, Level 5.

Fibonacci's Rabbits sheet

Calculators or access to spreadsheets

Fibonacci numbers, recurrence relation, quadratic equations, conjecture, divisibility properties, infinity, Golden Ratio, factorisation, surd expression

*In this session we recall the Fibonacci numbers by looking at dominoes and coloured cubes.*

#### Teachers’ Notes

You’ll recall that Fibonacci introduced his numbers using the rabbit problem (see Fibonacci I, Level 5). We have shown the first few generations of rabbits in the diagram below. You might like to print the following section as a poster.

If you look carefully at the diagram, you will see that there are three types of pairs of rabbits. These are ones represented by the:

red dots – new born – say a_{n} in generation n;

green squares – month old – say b_{n} in generation n;

blue rhombuses – older than one month old – say c_{n} in generation n;

Let F(n) be the total number of pairs in generation n. We’ll show that

F(n + 2) = F(n + 1) + F(n).

The first thing to notice is that

F(n) = a_{n} + b_{n} + c_{n}.

The second thing is that

a_{n} = b_{n-1} + c_{n-1}.

The third thing is that

c_{n} = b_{n-1} + c_{n-1}.

And the fourth thing is that

b_{n} = a_{n-1}.

So

F(n + 2) = a_{n+2} + b_{n+2} + c_{n+2}

= (b_{n+1} + c_{n+1}) + (a_{n+1}) + (b_{n+1} + c_{n+1})

= (a_{n+1} + b_{n+1} + c_{n+1}) + (b_{n+1} + c_{n+1})

= F(n + 1) + (b_{n+1} + c_{n+1})

= F(n + 1) + (a_{n}) + (b_{n} + c_{n})

= F(n + 1) + F(n).

Now we have put this in here, not that you would necessarily want to show it to your students but rather that you might like to know how the Fibonacci recurrence relation comes about.

On the other hand, there are a couple of other situations that generate the Fibonacci numbers and that are fairly easy to understand. We list them here as Dominoes and Cubes and we expect to use them with the students in the first session of this unit.

**Dominoes**: In how many ways can dominoes cover a 2 x n board?

In this problem you can think of a domino as being a 2 x 1 rectangle. Let’s see how the numbers build up for n = 1, 2, 3, and 4.

If D(n) is the number of ways a domino can cover a 2 x n board, then from above we can see that D(1) = 1, D(2) = 2, D(3) = 3, and D(4) = 5. It can easily be shown that D(5) = 8 and so it begins to look as if

**Conjecture 5**: D(n) = F(n + 1) for n > 0.

To show that this is true, we only have to look at how the right hand side of a

2 x (n + 2) board can be covered. Either there is one vertical domino or there are two horizontal ones. If it is one vertical domino, the 2 x (n + 1) board remaining can be filled in D(n + 1) ways; if it is two horizontal dominoes, the 2 x n board remaining can be filled in D(n) ways. This means that

D(n + 2) = D(n + 1) + D(n).

But we know from above that D(1) = 1 and D(2) = 2. So D(n) = F(n + 1).

**Cubes**: Suppose that we have red cubes and blue cubes. How many ways can we make a tower of cubes so that no two adjacent cubes are blue?

The way to start is to try to see what happens in small cases. So let the number of towers that can be made with n cubes be C(n). What can we say about C(1), C(2), C(3), etc.?

From the diagram we can see that C(1) = 2, C(2) = 3, and C(3) = 5. With a little more work it can be shown that C(4) = 8.

It looks as if we might have

**Conjecture 5**: C(n) = F(n + 2) for n > 0.

We can show this in the same way that we did for the Domino numbers. Suppose that we have a tower with n + 2 cubes in it. The top cube is either red or blue. If it is red, then we can have any of the towers with n + 1 cubes underneath. So a red on top comes from C(n + 1) towers.

If the blue is on top, then the cube underneath the blue cube has to be red. Below that we can have any of the C(n) possible towers that can be made with n cubes. So

C(n + 2) = C(n + 1) + C(n).

And because C(1) = F(3) and C(2) = F(4), C(n) = F(n + 2).

**Washing:** We get exactly the same situation if we put washing on the line. Suppose that we hang up football jerseys and football shorts but we don’t want to put two shorts together. Then working from the left we can think of n pieces of washing as being equivalent to n blue or red cubes.

### Teaching Sequence

Reintroduce the Fibonacci numbers. This might be done using the story of the rabbits, by spreadsheets, or by asking leading questions.

*What do you remember about Fibonacci numbers?*

What do you remember about Fibonacci?Give the groups the Cubes problem and let them go away in their groups to try to find C(n) for n < 7. Make sure that they record their results. This is preferably done by using a table.

Discuss what they have found and try to make a conjecture(s) based on their work. (There may be competing conjectures. Test out each one and think about the ones that satisfy the numbers that the groups have found.)

*Is there a way of getting C(3) from C(2) and C(1)?*

Is there a way of getting C(4) from C(3) and C(2)?

Is there a way of getting C(5) from C(4) and C(3)?*Can you generalise these ideas?*Take them through a proof of their conjecture as in the Teachers’ Notes. Give them time to write the proof down in their books.

Give the groups the Dominoes problem and ask them to find D(n) for n < 7. This time also ask them to come up with some conjectures. They should also be trying to find proofs of their conjectures.

Discuss what the groups have found.

*Is there a way of getting D(3) from D(2) and D(1)?*

Is there a way of getting D(4) from D(3) and D(2)?

Is there a way of getting D(5) from D(4) and D(3)?*Can you generalise these ideas?*

Can you use them to make up a proof?Let them take you through a proof. Have someone write out the steps on the board. The rest of the class should be ‘critical friends’ during this process.

Allow time for the class to write up a proof of the Dominoes problem in their books.

Give them the Washing problem to tackle in their groups. Have a reporting back session.

#### Session 2

In this session we introduce a new sequence of numbers, called the Lucas numbers, which is based on the same recurrence relation as the Fibonacci numbers. We investigate divisibility properties of these numbers.

#### Teachers’ Notes

In the first session we looked at some other sequences that were built with the same relation as the Fibonacci numbers but that had different initial values (different values when n = 1 and n = 2). Here we look at a famous sequence that was invented by Lucas (he is also famous for inventing the Tower of Hanoi problem).

Instead of starting off with F(1) = 1 = F(2), Lucas decided that he wanted to start with 1 and 3, in that order. Since this gives quite a different set of numbers we’ll call the n-th Lucas number, L(n). So here we have

L(1) = 1, L(2) = 3 and L(n + 2) = L(n + 1) + L(n).

The first thirty Lucas numbers are:

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364,

2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079,

103682, 167761, 271443, 439204, 710647, 1149851, 1860498

Both the Fibonacci and Lucas numbers can be generated using a spreadsheet.

Simply put the first number in cell A1, the second in cell A2, then enter the formula <

> “=A1+A2” in cell A3. Select cell A3 and as many as you like below it and choose the ‘fill down’ function.

This will produce a sequence of numbers such that each equals the two before it.

Notice that we have highlighted below in bold the Lucas numbers that are divisible by 3, 4, 7 and 11.

Divisible by 3:

1, **3**, 4, 7, 11, **18**b>, 29, 47, 76, 123, 199, 322, 521, **843**, 1364,

2207, 3571, **5778**, 9349, 15127, 24476, **39603**, 64079,

103682, 167761, **271443**, 439204, 710647, 1149851, **1860498**

Divisible by 4:

1, 3, **4**, 7, 11, 18, 29, 47, **76**, 123, 199, 322, 521, 843, **1364**,

2207, 3571, 5778, 9349, 15127, **24476**, 39603, 64079,

103682, 167761, 271443, **439204**, 710647, 1149851, 1860498

Divisible by 7:

1, 3, 4, **7**, 11, 18, 29, 47, 76, 123, 199, **322**, 521, 843, 1364,

2207, 3571, 5778, 9349, **15127**, 24476, 39603, 64079,

103682, 167761, 271443, 439204, **710647**, 1149851, 1860498

Divisible by 11:

1, 3, 4, 7, **11**, 18, 29, 47, 76, 123, 199, 322, 521, 843, **1364**,

2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079,

103682, **167761**, 271443, 439204, 710647, 1149851, 1860498

By the same methods that we used in Fibonacci I, Level 5 it can be shown that 3, 4, 7, and 11 divide an infinite number of Lucas numbers.

Now in Fibonacci I, we were beginning to see that any number we could think of was the factor of an infinite number of Fibonacci numbers. But that isn’t true for Lucas numbers. For instance, there are no Lucas numbers in our list above that are divisible by 5.

To see this is actually true no matter how far into the sequence you go, reduce the numbers in the Lucas sequence modulo 5. (In other words just list the remainders when you divide by 5.) If we can show that we never get a 0, then we know that we can never find a Lucas number that has 5 as a factor.

The first twenty Lucas numbers modulo 5:

1, 3, 4, 2, 1, 3, 4, 2, 1, 3, 4, 2, 1, 3, 4,

2, 1, 3, 4, 2, 1, 3, 4,2, 1, 3, 4, 2, 1, 3.

See how the numbers 1, 3, 4, 2 cycle around? They do this for ever and so there is no Lucas number which is 0 modulo 5. In other words, no Lucas number is divisible by 5.

What numbers can you find that divide an infinite number of Lucas numbers? What numbers divide no Lucas numbers?

### Teaching Sequence

Note that we can use the Fibonacci recurrence relation in a number of ways, depending on what initial conditions we use. Get them to see how Cubes, Dominoes and Washing all give sequences with the Fibonacci recurrence relation but that the initial conditions differ from those that Fibonacci employed.

Remind them of the work in Fibonacci I to do with factors.

Tell them about Lucas’ choice of initial conditions and get them to work out the first 10 values of the Lucas sequence.

*What factors can you see here?*

Is any number a factor of some Fibonacci number?

Is any number a factor of some Lucas number?

Can you prove any of this?After the initial discussion get them to go into their groups to investigate Lucas numbers. Go round the groups as they work. Help them out if they are having difficulty by asking leading questions.

Bring the class together and see what they have discovered. Let each group write what they have found on the board. Some of this may be related to the material in the Teachers’ Notes and some may not. Try to prove as much as you can.

Let the students go into their groups to experiment with initial values for the Fibonacci recurrence relation.

*What initial values work like Fibonacci’s numbers in that every number seems to divide some number of the sequence?**What initial values work like Lucas numbers in that not every number seems to divide some number of the sequence?*Get the students to discuss the results that they found.

Let them write down the class’s conclusions in their note books.

#### Session 3 & 4

*Here we look at how quadratic equations can be used to find the general terms for the Fibonacci numbers, the Lucas numbers, and any other sequence of Fibonacci-like numbers that have similar recurrence relationships.*

#### Teacher’s Notes

In the last session we looked at what happens when we change the initial conditions of the Fibonacci recurrence relation. In these next two sessions we look at recurrence relations that are similar to Fibonacci’s and show how to find a general term for them.

In earlier sessions we’ve looked at

F(1) = 1, F(2) = 1 and F(n + 2) = F(n + 1) + F(n), and

L(1) = 1, L(2) = 3 and L(n + 2) = L(n + 1) + L(n).

And in What Happens on Average, we’ve looked at

R(n + 2) = ½ R(n + 1) + ½ R(n), with varying R(1) and R(2).

Here we will call a recurrence relation Fibonacci-like, if it is of the form

T(n + 2) = A T(n + 1) + B T(n),

where A and B are constants.

It turns out that quadratic equations can be used to find the general term of all of these Fibonacci-like recurrence relations. We’ll move off from an example and show you what we mean as we go along.

Here is our first example. Let A = 2 and B = 3, so we’re looking at

T(n + 2) = 2 T(n + 1) + 3 T(n).

If we choose to start off with T(1) = 2 and T(2) = 10, here are the next 8 terms of the sequence:

26, 82, 242, 730, 2186, 6562, 19682, 59050.

You might like to use a spreadsheet to find the next 12 terms.

The fascinating thing about this sequence is that it is very nearly consecutive powers of 3 – but not quite.

The next thing to do is to pull a rabbit out of a hat. The recurrence relation here is

T(n + 2) = 2 T(n + 1) + 3 T(n).

So consider the quadratic equation

x^{2} = 2x + 3.

Solving that gives

x = 3 or -1.

It turns out that

T(n) = 3^{n} + (-1)^{n}

What’s going on here?

Well for some reason, if we have any Fibonacci-like recurrence relation of the form

T(n + 2) = A T(n + 1) + B T(n),

we can find T(n) by solving the quadratic

x^{2} = Ax + B.

If r and s are roots of the quadratic, r ≠ s, then

T(n) = Cr^{n} + Ds^{n},

where we can find the constants C and D by solving two equations using the values of T(1) and T(2).

To see how we do this let’s go back to our last recurrence relation. Here we found that r = 3 and s = -1. So

T(n) = C3^{n} + D(-1)^{n}.

Since T(1) = 2 and T(2) = 10 we get the two equations

2 = 3C – D

10 = 9C + D.

Solving gives C = D = 1 and so we know that

T(n) = 3^{n} + (-1)^{n}.

But we can do that for all of the Fibonacci-like sequences – even Fibonacci itself. To see how that goes, start with

F(1) = 1, F(2) = 1 and F(n + 2) = F(n + 1) + F(n).

So we have to deal with the quadratic equation

x^{2} = x + 1.

This can be solved using the quadratic formula to give

Take r = (1 + √5)/2 and s = (1 – √5)/2, and do some very careful algebra (don’t simplify the surd expression at all unless you need to make a calculation) and you’ll get

You might find it surprising that we can find the general term of the Fibonacci sequence. Perhaps it is even more surprising that this expression involves √5! It’s certainly not the first thing that you would think of.

Anyway, if you repeat this process again for the Lucas sequence you should get

Check it out for some small values of n.

And, by the way, that sequence in What Happens on Average, its general term is

R(n) = 1^{n} + 4(-1/2)^{n},

well, it is if you start off with -1 and 2.

In fact if you start off with a and b instead you get

You should now find it easy to prove some of the things in that unit.

**Comments**:There are six things that need to be said here.

First thing: If your students have only worked with quadratic equations that they can solve by factorisation, then there is still plenty for them to be able to do. It is certainly easy enough to find interesting sequences for them to tackle that have simple whole number roots. We have done this in Copymaster 1.

Second thing: Even if they can solve quadratic equations by using the formula, most of your students will have trouble working with surd expressions. They will want to change it into 2.23… If they use approximations to √5 in order to find their values of F(n), then they will only get approximate answers. However, they should probably see how to round these approximations to get the correct whole number answer.

Third thing: For best results in finding the general term of the Fibonacci sequence (and others too), encourage the class to leave the √5 in until the end. As it happens, they just fall out then. The major problem is in expanding (1 + √5)^{n}.

Fourth thing: Armed with this method and some computing power, your students can find F(n) for quite large numbers n without having to find all of the intermediate terms of the Fibonacci sequence.

Fifth thing: But why does this quadratic method work? In some ways the answer is “because it does”. You might remember other times when a substitution like this has worked.

Sixth thing: And there is always the question of what to do if r = s! In that case you have

T(n) = (C + nD)r^{n}.

### Teaching Sequence

Recall the method of factorising a quadratic and how this is used to solve quadratic equations. Recall the subject of the last session.

*How can you factorise x*^{2}– 3x + 2?

How can you solve x^{2}– 3x + 2 = 0?

Why would you ever want to solve a quadratic equation anyway?

Do you know any uses for that skill?

How can we use it to find the general term of the Fibonacci sequence?There are some things that you can motivate but it’s difficult to motivate the use of quadratics in solving recurrence relations. Some things just work. Be up front about it. Take them into a simple example such as the first worked example in the Teachers’ Notes.

Let them work in groups to find the general term of the sequences that come from the recurrence relations in Copymaster 1. Let them use the general term to find the first 10 terms of the sequence. Check these by using the recurrence relation (possibly with a spreadsheet).

Of course the sequences that interest us most are much more complicated than the ones we’ve just worked with. The problem is that we can’t solve these easily using the factorisation method. There is a formula approach but this is not on the agenda until next year. However, we do have a way to solve any quadratic using a spreadsheet.

Set up a spreadsheet so that it has three cells for the coefficients of the terms of the quadratic (you could put headings in the cells above to make it easier to use). Lets say that the cells for the coefficients are x

^{2 }in A2, x, in B2, and the number in C2.In the cell you want the first answer to appear in enter the quadratic formula (=(-B2+(B2*B2-4*A2*C2)^0.5)/(2*A2)), and in a separate cell enter the negative version (=(-B2-(B2*B2-4*A2*C2)^0.5)/(2*A2)).

Now, so long as you enter the coefficients in the right cells your spreadsheet will solve any quadratic equation for you.

Armed with this spreadsheet method we can solve any quadratic. Send them away to solve any quadratic that has real roots. Let them use this approach to find the general terms of the Fibonacci and Lucas numbers.

Let them then work on their own recurrence relations and find their general terms.

The quicker students could be asked to make up their own recurrence relations that fit a practical situation. (They might use Fibonacci’s rabbits, Cubes, Dominoes, etc.as starting points and vary them a little. For example, what happens if each pair of rabbits produces

**two**pairs instead of one?). They should then try to find the general terms of these sequences.

#### Session 5

In this session we consider what the limits of some sequences are and what the limit of the ratio of consecutive numbers in the some sequences are.

#### Teacher’s Notes

In What Happens on Average, we found by experimentation that if

R(n + 2) = ½ R(n + 1) + ½ R(n), with R(1) = a and R(2) = b, then

R(n) → (a + 2b)/3 as n → ∞.

Now that we know the quadratic method for finding the general term of a sequence we can show that limit directly.

As we said in the Teachers’ Notes to the last session, the algebra gives us

Now as n → ∞, (½)^{n }→ 0 and 1^{n} → 1. So R(n) approaches the multiple of 1^{n} in the expression above. So R(n) → (a + 2b)/3 as we had already found by experiment.

We can take this same approach with any other general term.

Let’s go back to the Fibonacci sequence for a minute. Remember that

F(1) = 1, F(2) = 1 and F(n + 2) = F(n + 1) + F(n).

Using a spreadsheet you can investigate the ratio F(n + 1)/F(n) as n gets very large.

Suppose that F(n + 1)/F(n) approaches L as n approaches infinity, then so does F(n + 2)/F(n + 1), F(n)/F(n – 1) etc. Now

F(n + 2) = F(n + 1) + F(n), so

F(n + 2)/F(n + 1) = F(n + 1)/F(n + 1) + F(n)/F(n + 1).

Hence L = 1 + 1/L.

Multiplying both sides of the equation by L we get

L^{2} – L – 1 = 0.

From the last session when we found a way to express the Fibonacci numbers in terms of them, we know that the roots of this equation are (1 + √5)/2 and (1 – √5)/2. So L must be one of these two, but which?

That’s not too hard. After all, it is clear from the values of F(n) that L must be positive. So

This number is the intriguing Golden Ratio. That ought to be good for a unit all by itself at some point.

### Teaching Sequence

Remind the students of sequence of numbers that we found in What Happens on Average. Let them play with it to recall the way it went. Recall the limit of R(n) as n → ∞. Ask them if they can see how to prove this now that they have done the work of the last session. Work through the ideas on the board.

In their groups, let them try the sequences that come from the recurrence relations of Copymaster 1. What numbers do the general terms approach as n → ∞? These can be checked using a spreadsheet.

Ask the groups to report back and share their results.

Now consider the Fibonacci sequence again. This clearly gets larger and larger as n gets larger and larger. However, say that the ratio of F(n + 1) to F(n) approaches an interesting limit.

Let them work in their groups using a spreadsheet to see what this limit is. Is it something that they recognise?

What does the ratio L(n + 1)/L(n) approach as n → ∞? Let them use a spreadsheet again.

Show them how to find this limit using quadratics.

Point out that the limit is called the Golden Ratio. If there is time (or for homework) let them find out what they can about the Golden Ratio from the internet.