I supposed that you have learnt the chapter Sequences & Series in Maths T before you arrive at this chapter.
A recursive definition of a sequence specifies one or more initial terms and a rule for determining subsequent terms from those that precede them. A recurrence relations for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, …, an-1, for all integers n with n ≥ n0, where n0 is a non-negative integer.
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 a0, which is the initial term. Then, we find that the term a1 which is related to the initial term by the equation
a1 = a0 + 1
So after generalizing the sequence, we can conclude that the arithmetic sequence can be represented by the recurrence relations
an = an-1 + 1
where n ≥ 0 (non-negative integer). Using this equation, and given the initial condition a0, 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 a109!). So now you know that a recurrence relation is just an equation which has an and at least another term an-x. Examples of recurrence relations are
an = 6an-2
an = 5an+4 - 2an+3 + n
We say that a recurrence relation is homogeneous when it only contains the terms an-x. For example, an = 6an-2 is homogeneous, while an = 5an-1 – 2an-2 + 3 is not, as 3 is not an an-x. term.
We say that a recurrence relation is linear when the maximum power of the an-x terms is 1. For example, an = 6an-2 is linear, but an = 6(an-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 an related from itself. For example, an = 6an-1 is a first order recurrence relation, while an = 6an-1 + an-3 is a third order recurrence relation. Any recurrence relation with the k-th order requires k amount of initial conditions to be solved. For example, we see that the equation an = 8an-1 + 9an-2 needs 2 initial conditions, a0 and a1 to be defined.
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
Leonardo Pisano, also known as 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, a0 and a1, which are both 1 (a0 is the starting, which I will call it as month 0, and a1 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 Fibonacci Sequence, which is represented by the recurrence relation
fn = fn-1 + fn-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
Hn = 2Hn-1 + 1
where Hn represents the minimum number of moves required to transfer n pegs from the left to the right pole. The initial condition, H0 is 1 move.
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 a0 amount of fish will double every month. So for n months, the number of fish can be represented by the relation an = 2an-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 an = n + an-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 a0 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 nth month can be represented by the relation an = (1 + 0.1)an-1 – 100.
4. 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 an = 2an-1 + an-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 an = an-1 + an-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 an = 2an-1 + 2an-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