Recurrence Relation (Part 1)

In mathematics we come across many series which can be expressed in terms of its some or every term. These terms can be distributed in the whole of the series. For example if the n^th term is termed as T_n and it depends on its previous two terms then T_n can be expressed as many recurrence relation with these two terms. One of it is T_n = T_n-1 + T_n-2. Recurrence relations are used in computer science to find the time complexity of many algorithms. Let us consider some examples of recurrence relations. We will solve them in some other post.

• Multiple by consecutive numbers: Look at the series 2,4,6,8,10,12,14,16...The series can be represented as 0+2, 2+2, 4+2, 6+2, 8+2, 10+2, 12+2, 14+2...Here every term can be represented as sum of the previous term and 2.Hence, multiplication of 2 and consecutive natural numbers can be represented like this. T_n = T_n−1 + 2 where the first term is T₁ = 2. Similarly, multiplication of can be represented like T_n = T_n−1 + k where T₁ = k.



• Fibonacci Series: Leonardo di Pisa also known as Fibonacci posed a problem about rabbits in his book Liber Abaci in 1202. The problem stated: One pair of rabbits, one male and one female, are left on an island. These rabbits begin breeding at the end of two months and produce a pair of rabbits of opposite sex at the end of each month thereafter. Can you determine the number of pairs of rabbits after n months assuming no rabbit dies on this island?
  
  Let us try to solve this problem. In first month there is one pair. So, T₁ = 1. In the second month there is one pair. So, T₂ = 1. In the third month there are two pairs. So, T₃ = 2. Two are the rabbits in the first month and additional two are due to birth. In fourth month the pair of children produced are equal to the pairs of rabbits in the second month which can produce, this is equal to 1. The additional number of pairs are those in third month which equals 2. So, T₄ = 3. So it can be expressed in the recurrence relation as T_n = T_n-1 + T_n-2. Where T_n, T_n-1 and T_n-2 is pair of rabbits in n^th, n-1^th and n-2^th month respectively.


• The tower of Hanoi: The problem is invented by Edouard Lucas in 1883. We are given a tower of eight discs, initially stacked in decreasing size on one of three pegs. The problem is to transfer the entire tower to one of three pegs, moving only one disc at a time without ever moving a larger disc onto a smaller one.
  
  Let us solve this problem.
  
  
  
  1. With one disk we can move it in 1 move. So T₁ = 1.
  2. With two disks we can move it in 3 moves. The procedure is like this. There are three pegs A, B and C. A has both the disks in increasing order from top arranged in the order 2,1. We move 1 to B. Then move 2 to C. Then move 1 to C. So the number of moves for two disks is three. So, T₂ = 3.
  3. For three disks, we can move it in 7 moves. The procedure is like this. There are three pegs A, B and C. A has all the three disks in increasing order from top arranged in the order 3,2,1. We, move 1 to C, move 2 to B, move 1 to B, move 3 to C, move 1 to A. Then move 2 to C. Then move 1 to C. So the number of moves for three disks is seven. So, T₃ = 7.
  We can generalize the procedure like this, move n−1 disks to one peg then move the n^th disk and bring back the n−1 disks above the n^th disk. We can solve this problem in T_n = 2T_n-1 + 1 moves.

Read solutions of the above recurrences