Introduction

Recurrence is a concept that is extensively used in computer science, mathematics, and various other fields. It is a sequence of values that are defined in terms of one or more previous terms in the sequence. Recurrence relation is the formula that defines the sequence of a recurrence.

What is recurrence ?

Recurrence is a mathematical concept that involves defining a sequence of numbers or a function in terms of its previous values. It’s like a rule that tells you how to get the next number or value in a sequence based on the previous ones. For example, the Fibonacci sequence is a famous example of a recurrence relation, where each number is the sum of the two preceding numbers. Recurrence relations are used to model many real-world phenomena, and understanding how to solve them is important in mathematics and computer science.

Types of Recurrence Relations

There are mainly two types of recurrence relations: linear and non-linear.

Linear Recurrence Relations

A linear recurrence relation is one in which the current term is a linear combination of the previous terms. It can be represented as:

$a_n = c_1a_{n-1} + c_2a_{n-2} + … + c_ka_{n-k}$

where $c_1, c_2, …, c_k$ are constants.

Non-Linear Recurrence Relations

A non-linear recurrence relation is one in which the current term is a non-linear function of the previous terms. It can be represented as:

$a_n = f(a_{n-1}, a_{n-2}, …, a_{n-k})$

where $f$ is a non-linear function.

Substitution method for solving a recurrence

The substitution method is a technique used to solve recurrence relations, which are mathematical equations that recursively define a sequence or function. The method involves guessing a closed-form expression for the sequence or function and then using mathematical induction to prove that the guess is correct.

Here are the steps involved in the substitution method:

Guess a closed-form expression for the sequence or function. This guess should be based on the recurrence relation itself and any initial conditions provided. For example, if the recurrence relation is defined as f(n) = f(n-1) + 2n and the initial condition is f(0) = 1, a good guess might be f(n) = n^2+1.
Use mathematical induction to prove that the guess is correct. Mathematical induction involves proving that a statement is true for all natural numbers. In this case, we want to prove that the guess is correct for all values of n. We do this by first proving that the guess is correct for the base case, which is usually n = 0 or n = 1. For example, if the guess is f(n) = n^2 + 1 and the initial condition is f(0) = 1, we can substitute n = 0 into the guess and show that f(0) = 1, which matches the initial condition.
Next, we assume that the guess is correct for some value of n, and then use the recurrence relation to prove that it is also correct for the next value of n. For example, if the guess is f(n) = n^2 + 1 and the recurrence relation is f(n) = f(n-1) + 2n, we can substitute f(n-1) with our guess and simplify the equation to f(n) = (n-1)^2 + 2n + 1, which simplifies to f(n) = n^2 + 1, which matches our guess.
Finally, we use mathematical induction to prove that the guess is correct for all values of n. Since we have shown that the guess is correct for the base case and that it is correct for any value of n if it is correct for the previous value of n, we can conclude that the guess is correct for all values of n