B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

1, 1, 2, 3, 5, 8, 13,…

The recurrence relation is given by:

a_n  a_n1  a_n2 , a₀  a₁  1

Example : Towers of Hanoi is a popular puzzle. There are three pegs mounted on a board, together with disks of different sizes. Initially, these discs are placed on the first peg in order of different sizes, with the largest disc at the bottom and the smallest at the top. The task is to move the discs from the first peg to the third peg using the middle peg as auxiliary. The rules of the puzzle are:

• 
  Only one disc can be moved at a time.
  
• 
  No disc can be placed on the top of a smaller disc.
  

This is a popular puzzle and we shall discuss its solution, using the one of the techniques discussed in this chapter.

With these illustrations, we define recurrence relation now.

Definition: A recurrence relation for the sequence {a_n} is an equation, that expresses a_n in terms of one or more of the previous terms of the sequence, namely, a₀, a₁, ..., a_n–1, for all integers n with n  n₀, where n₀ is a nonnegative integer.
Example : a_n = 1.06a_n–1, with a₀ = 0.5.
Example : a_n = 2a_n–1 + 5, with a₀ =1.

The term a₀, given in the above two examples, specify initial condition to solve the recurrence relation completely.