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

RECURRENCE RELATION:

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.

The expression of higher terms in terms of combination of lower terms is known as recurrence relation

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 n^th hour be a_n. Then, we can say that a_n = 2a_n–1.

Example: Consider the Fibonacci sequence