Recurrence Relation

Recurrence Relation Definition

Recursive techniques are very helpful in deriving sequences and it can also be used for solving counting problems. The procedure that helps to find the terms of a sequence in a recursive manner is known as recurrence relation. We have studied about the theory of linear recurrence relations and their solutions. Finally, we are introduced to generating functions for solving recurrence relations. But the question is what is a recurrence relation? If you google the term “Recurrence Relation” you might get something back like: “ In Mathematics, a recurrence relation can be defined as an equation that recursively clarifies a sequence or multidimensional array of values, once  or more initial terms are provided with: each further term of the sequence or an array is explained as a function of the preceding terms.” 

Meaning of Recurrence Relation

What do you mean by recurrence relation? By the term “standard pattern”, we mean that all the terms in the relation of an equation have the same characteristics. In other words it means that if there is a value of ‘n’, then it can be used to find other values by just entering the value of ‘n’.

The value of n must be organized and accurate. This is known as the Simplest form. In case of the simplest form of any such relation, the following term is dependent only upon the previous term. The sequence or series formed by recurrence relation is called a Recurrence Sequence.

Methods of Solving Recurrence Relations

There are three methods of solving recurrence relations:

1. Substitution Method: This method is a guesswork game. We guess the solution and then with the help of mathematical induction we try to prove if the guess we made is true or false. 

2. Recurrence Tree Method: In this method, we draw a recurrence tree just like a family tree. But in the recurrence tree we do not figure out the relation but time. We calculate the time taken by every level of the tree. The final job is to sum the work done at all levels. For drawing a recurrence tree, we begin with the given recurrence and continue drawing till we catch hold of a pattern among levels. The pattern will be basically arithmetic or a geometric series. 

3. Master Method: This is a straightforward method to get your solution. It is basically derived from the recurrence tree method. If we draw the tree, we will see that the work is done at the roots, the leaves, and the height of the recurrence tree. If the work done at leaves will polynomially be more then the leaves then it will be the dominant part. Thus, the result would be the work done at the leaves. But if the work done at the leaves and the root will be asymptomatically be more, then the result would be height multiplied by work done at any level. If work done at root is asymptomatically more, then the result would be work done at root. 

Examples of Recurrence Relation

How do you calculate recurrence relations? See the following examples to find your answer.

Example 1) Find a recurrence relation and the initial condition for 1,5,17,53,161,485….

Solution 1) It would be easier to find a recurrence relation if we would have some context for the problem as it tells us how to proceed from previous term to future terms. Unfortunately, we are provided with only the sequence. Nevertheless, if we look at the difference between the terms like 4,12,36, 108 and so on… we can see that the numbers are growing by a factor of 3. Is it the same with the original sequence? 1*3 = 3; 5*3 = 15; 17*3 = 51 and so on... notice that we always end up with 2 less than the next term. Therefore, our recurrence relation will be aₙ = 3aₙ₋₁ + 2 and the initial condition will be a₀ = 1.

Example 2) Solve the recurrence aₙ = aₙ₋₁ + n with a₀ = 4 using iteration. 

Solution 2) We will first write down the recurrence relation when n=1. We won't be subtracting aₙ₋₁ to the other side.

                                  a₁ = a₀ + 1       

Now a₂ = a₁ + 2, but we already know what a₁ is, so if we subtract, we will get

                                  a₂ = (a₀ + 1) + 2

Now we’ll go to  a₃ = a₂ + 3 by using the known value of a₂ :

                                  a₃ = ((a₀ + 1) + 2) + 3

We can clearly see a pattern each time we take the previous term to add to the current index. Therefore: aₙ = ((((a₀ + 1) + 2) + 3) + ….. + n-1) + n.

If we regroup the terms, we will notice that aₙis just a₀.

Also the sum of the integers from 1 to n. Therefore, since a₀ = 4,

                       aₙ = 4 + \[\frac{n(n+1)}{2}\].