Linear Recurrence : Introduction

Fibonacci Sequence is one of the simplest examples of a linear recurrence: $$$F_x = F_{x-1} + F_{x-2}$$$, with $$$F_0 = 0, F_1 = 1$$$

Here is a more general example of a linear recurrence:

\begin{align} R_{x} = \sum_{i=1}^{n}{C_i \cdot R_{x — i}} \end{align}

where $$$C_i$$$ is constant and $$$R_x$$$ is the x-th term of the recurrence. Since $$$R_x$$$ depends on the previous $$$n$$$ terms of the recurrence, it is called a linear recurrence of order $$$n$$$. It is called a "Linear" Recurrence, since we do not have any terms of the type $$$R_x \cdot R_y$$$

Note: We need $$$n$$$ initial conitions for a linear recurrence of order $$$n$$$, for example, we have 2 initial conditions for the Fibonacci Sequence.

Iternary

In this blog we will learn about various methods of solving the following problem: Given a Linear Recurrence of order $$$N$$$, find the $$$K$$$-th term of the recurrence. There are various methods to do this:

• $$$O(N \cdot K)$$$ using DP
• $$$O(N^3 \cdot logK)$$$ using Matrix Exponentiation
• $$$O(P(n) \cdot logK)$$$ using Characterstic Polynomials where P(n) is the time required for polynomial multiplication — which can be $$$O(N^2)$$$ naively or $$$O(N^{1.58})$$$ using Karatsuba Multiplication or $$$O(N logN)$$$ using Fast Fourier Transform.

DP Solution

The $$$O(N \cdot K)$$$ solution is pretty trivial. (Assume dp[0] .. dp[n-1] are stored correctly as initial conditions)

for(int i = n; i < k; i++){
    dp[i] = 0;
    for(int j = 0; j < n; j++){
        dp[i] += c[j] * dp[i - j];
    }
}

Matrix Exponentiation

Let's look at the problem from another angle. From the DP solution, it is clear that we need to keep track of the previous $$$n$$$ elements at all times, and it won't matter even if we "forget" other elements. So let's keep a column vector of the "current" $$$n$$$ consecutive elements. Since the recurrence relation is a Linear Relation, it is possible to have a linear transformation to get the next elements.

Finding this linear transformation is quite intuitive and it can be expressed as multiplication with a square matrix, so let's directly write the general result.

Reader is advised to take a moment to manually mutliply the matrices and verify the above result for a better understanding.