×

# Introduction to recurrence relations

This post is a guide to the art of breaking a complex problem into simpler versions of the same problem namely the art of problem solving by recurrence relations.it is a part of this set

img

In many problems related to combinatorial counting there involves an integer parameter $$n$$.This $$n$$ denotes either some set or multiset in the problem or size of combinations etc.Thus a counting problem is often not just one problem but a sequence of individual problems.There are some algebraic methods for solving counting problems involving an integer parameter $$n$$ which most of the time leads to an explicit formula.

For obtaining a recurrence relation,we must proceed along the following steps.

$$\textbf{Obtain a base case}$$

At first we must solve a simpler version of the problem at hand.We will later use this result obtained to solve the larger problem.So example in the Fibonacci sequence we have the first two terms as base cases.That is $$F_1 = 0$$ and $$F_2 = 1$$.

$$\textbf{Formulate a recursive definition:}$$

Next we must break the larger problem down into smaller version of the same problem and continue this process until we arrive at a base case.Then we have to use this base case either to obtain a generic term or an explicit formula if possible.

As an example for the Fibonacci sequence we have the recursive definition $$F_n = F_{n-1} + F_{n-2}$$.So using this definition and the base cases we can find any term of the sequence that we want.