Recurrence Relation
INTRODUCTION: We are familiar with some problem solving techniques for counting, such as principles for addition, multiplication, permutations, combinations etc. But there are some problems which cannot be solved or very tedious to solve, using these techniques. In some such problems, the problems can be represented in the form of some relation and can be solved accordingly. We shall discuss some such examples before proceeding further.
Example: The number of bacteria, double every hour, then what will be the population of the bacteria after 10 hours? Here we can represent number of bacteria at the nth hour be an. Then, we can say that an = 2an–1.
Example : Our usual compound interest problems are examples of such representation. That is, 
, where P is principal, r is rate of interest, n is period in years and In is interest at the end of nth year.
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, With these illustrations, we define recurrence relation now.
Definition: A recurrence relation 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 nonnegative integer.
Example: an = 1.06an–1, with a0 = 0.5.
Example: an = 2an–1 5, with a0 = 1.
The term a0, given in the above two examples, specify initial condition to solve the recurrence relation completely.