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

You can find more detailed explanations on this technique here and here. But here I've described it briefly:

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.

Alright, so a multiplication with the Transformation Matrix shifts the elements of the vector by $$$1$$$ index each, so we can shift it by $$$X$$$ indices by multiplying the transformation matrix to it $$$X$$$ times. However we take advantage of the fact that we can first multiply the transformation with itself $$$X$$$ times and then multiply it with the column vector. Why is this advantageous? Because we can use Binary Exponentiation! If we the transformation matrix is $$$T$$$, we can find $$$T^X$$$ in $$$O(N^3 logX)$$$ time. This lets us get the K-th term in $$$O(N^3 logK)$$$ time.

Check out this Mashup for practice problems

Using Characterstic Polynomial

I learnt about this technique from TLE's blog on Berlekamp Massey Algorithm, but since it wasn't explained in detail, I had a lot of difficulty in understanding this, so I'll try to explain it in a more beginner-friendly way. Apparently the name of this trick is Kitamasa Method.

The original recurrence can be re-written as:

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

Which means, any multiple of $$$\left(R_{j} - \sum_{i=1}^{n}{C_i \cdot R_{j — i}}\right)$$$ is $$$0$$$ and if it is added or subtracted anywhere, the answer doesn't change.