I supposed that you have learnt the chapter **Sequences & Series** in Maths T before you arrive at this chapter.

A

recursive definitionof a sequence specifies one or more initial terms and a rule for determining subsequent terms from those that precede them. Arecurrence relationsfor the sequence{ais an equation that expresses_{n}}ain terms of one or more of the previous terms of the sequence, namely,_{n}a,_{0}a,_{1}…,a, for all integers_{n-1}nwithn ≥ n, where_{0}nis a non-negative integer._{0}

That was the formal definition of recurrence relations. When you say that something is **recursive**, it means that there is a repetition. So a **recurrence relation** is basically just an **equation** which relates a term, with the term before it. Let’s take the arithmetic sequence 1, 2, 3, 4, 5, … till infinity. So the term ‘2’ is derived from the term ‘1’, by adding 1 to it. Similarly, there is the same relationship for all the terms, which is to add 1 to it. We shall denote ‘1’ as **a _{0}, **which is the

**initial term**. Then, we find that the term

**a**

_{1}_{ }which is related to the initial term by the equation

**a _{1} = a_{0} + 1**

So after generalizing the sequence, we can conclude that the arithmetic sequence can be represented by the recurrence relations**a _{n} = a_{n-1} + 1**

where **n ≥ 0** (non-negative integer). Using this equation, and given the initial condition **a**_{0}, you can write down the rest of the terms by slowly adding all the way up (just imagine if I asked you to find the term **a _{109}**!). So now you know that a recurrence relation is just an equation which has

**a**and at least another term

_{n}**a**. Examples of recurrence relations are

_{n-x}**a**

_{n }= 6a

_{n-2}a_{n}= 5a_{n+4}- 2a_{n+3}+ n

We say that a recurrence relation is **homogeneous** when it only contains the terms **a _{n-x}**. For example,

**a**is homogeneous, while

_{n }= 6a_{n-2}**a**is not, as 3 is not an

_{n}= 5a_{n-1}– 2a_{n-2}+ 3**a**. term.

_{n-x}We say that a recurrence relation is **linear** when the maximum power of the **a _{n-x}** terms is 1. For example,

**a**

_{n }= 6a_{n-2 }is linear, but

**a**

_{n }= 6(a_{n-2})^{2 }is not, as its maximum power is 2.

The **order / degree **of a recurrence relation tells us the maximum amount of terms away is the term **a _{n}** related from itself. For example,

**a**is a first order recurrence relation, while

_{n }= 6a_{n-1}**a**is a third order recurrence relation. Any recurrence relation with the

_{n }= 6a_{n-1}+ a_{n-3}**k-**th order requires

**k**amount of initial conditions to be solved. For example, we see that the equation

**a**

_{n }= 8a_{n-1}+ 9a_{n-2 }needs 2 initial conditions,

**a**and

_{0}**a**to be defined.

_{1}In STPM, you will only be dealing with

**linear**and

**2nd order**recurrence relations, for both

**homogeneous**and

**non-homogeneous**.

Now that you know what a recurrence relation is, I will guide you with some basic modelling. You need to learn how to use recurrence relations in a given situation, or question. Let me start with 2 very famous examples, the **Fibonacci Numbers **and the **Tower of Hanoi**.

** RABBITS, AND THE FIBONACCI NUMBERS**, also known as

Leonardo Pisano

**Fibonacci**, came up with this problem in the 13th century. Suppose a young pair of rabbits (one male and one female) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. He wanted to find a recurrence relation for the number of pairs of rabbits on the island after n months, assuming that no rabbits ever die.

Let’s try counting. In the beginning, there were only 2 rabbits. Then in the first and month, there are still 2 rabbits on the island, because they are still not old enough to breed. But in the second month, the pair of rabbits started to breed, and they produce another 2 rabbits on the island, making it 4 rabbits. In the third month, there will be 6, because the old rabbits reproduce, but not the young rabbits. Counting by pairs, we found out that the rabbits grow according to a sequence of 1, 1, 2, 3, 5, 8, 13, … and so on. Take a look at the bunny diagram below.

Now, here is the hard part. To solve this problem, you know that there are 2 initial conditions, **a _{0}** and

**a**, which are both 1 (

_{1}**a**is the starting, which I will call it as month 0, and

_{0}**a**is for the first month). As we step into month 2, the amount of pair of rabbits will be the number of pairs of rabbits in the previous month (month 1) plus a new line of rabbit which it reproduced (which has the condition of the rabbits in month 0). The progress goes on and every time we reach a new month, we will add up the number of pairs of rabbits in the previous month with the number of pairs of rabbits in the month before the previous month. So in the end, we come up with the famous

_{1}**Fibonacci Sequence**, which is represented by the recurrence relation

**f**

_{n}= f_{n-1}+ f_{n-2}I bet you got lost somewhere, but this is the best explanation I could come up with. You can try reading the textbooks, and you might not even understand it at all. We see that the Fibonacci sequence is a 2nd order homogeneous linear recurrence relation. This chapter really needs you to think a lot.

Do you know that Fibonacci numbers also exist in sunflower patterns, pinecones, and spiral seashells? Get to know more about Fibonacci Numbers in Nature.

__THE TOWER OF HANOI__

Have you played this game before?

You are given a chunk of disks of different sizes on the left. Your objective is to transfer all the disks from the left pole to the right pole, only moving one disk at one time, and not stacking a bigger disk onto a smaller disk. At every move, only one disk can be in your hand, and the disk could only be placed in any of the 3 poles. Watch this video to see how others do it:

Interesting? A myth created to accompany the puzzle tells of a tower in Hanoi where monks are transferring 64 gold disks from one peg to another, according to the rules of the puzzle. The myth says that the world will end when they finish the puzzle. Detail calculations show that if they move one disk per second, it will take them more than **500 billion years** to complete!

Anyway, enough of fun stuff. Our goal here is to find a recurrence relation for the minimum amount of moves required to move n pegs from the left to the right.

Let’s start from scratch. If there was one disk, you only need one move to solve the problem. If there were 2 disks, you need to take the top disk to the middle peg, transfer the bottom disk to the 3rd peg, and transfer the top disk back on top of the bottom disk on peg 3. So if we have **n** disks, we can see that we need to move **n-1** disks to the middle peg, move the bottom disk to the right, and then move the **n-1** disks to the last peg, on top of the bottom disk. The bottom disk only requires one move, but you need 2 moves to transfer the **n-1** disks, which is once to the middle peg, then twice to the 3rd peg. So here, we can deduce that the recurrence relation can be represented by**H _{n} = 2H_{n-1} + 1**

where

**H**represents the minimum number of moves required to transfer n pegs from the left to the right pole. The initial condition,

_{n }**H**is 1 move.

_{0}I suppose you are terribly confused by now. These are only 2 examples! The hard part of this chapter is to model recurrence relations. The solving part (will be dealt in section 4.2 & 4.3) are actually much easier. Spend more time thinking and try to figure out some of my examples below.

1. A pond with **a _{0}** amount of fish will double every month. So for

**n**months, the number of fish can be represented by the relation

**a**.

_{n}= 2a_{n-1}2. In the first month, you date 1 girl, the second month 2 girls, and the nth month you dated **n** girls. So the recurrence relation **a _{n }= n + a_{n-1}** will be the total amount of girls you have dated in the first n months. How nasty of you…

3. You have a loan of RM **a _{0}** from Along Bukit Beruntung. You now pay RM100 every month to the him, who charges you a rate of 10% increment every month. So the balance you owe the loan shark on the

**n**th month can be represented by the relation

**a**.

_{n}= (1 + 0.1)a_{n-1}– 1004. The cash deposit machine in CIMB bank only accepts RM1 coins (if they exist), RM1 notes and RM5 notes. If the order of the deposition matters, the number of ways you deposit RM n into the machine can be represented by the relation **a _{n} = 2a_{n-1} + a_{n-5}**. [5th order recurrence relation!]

5. If you can climb up a flight of stairs by taking either one step or two steps at one time, the recurrence relation for the number of ways to climb

**n**stairs can be represented by the equation

**a**.

_{n}= a_{n-1}+ a_{n-2}6. You are laying tiles on a walkway in a single line. You can only lay either red, green or blue tiles, in which no 2 red tiles are adjacent to each other, and the tiles of the same color are considered indistinguishable. The recurrence relation for the number of ways to lay out a walkway with **n** tiles is **a _{n} = 2a_{n-1} + 2a_{n-2}**. [Go think about it. This is hard…]

This is not an easy chapter. A lot of understanding is required. ☺

Hai John , I am learning this chapter but its quite hard for me to find exercises to practice since I lack of sources. May I know where I can get more questions to do? Thx^^

ReplyDeletethe second one is it gt problem??

ReplyDeletei think shud be a(term:n-1)+n-1

Hi Lumpy, sorry for a really late reply. You can buy the textbook, Discrete Structures by Rosen for extra exercises. As for 就是我, there's no mistake in the 2nd example.

ReplyDelete