Solving Linear Recurrence for Programming Contest

One of the topics that often arises in programming contests nowadays is about solving linear recurrence. It may come as a classic “find the n-th term of Fibonacci sequence” to more complex and creative forms of problems. Usually, after being simplified, the problem is merely asking you the n-th term of a linear recurrence. It should be able to solve with dynamic programming, however, the problem is that usually n can very large.

Because this topic starts to emerge in contests, I would like to share how I usually solve problems of this topic.


First, let’s start with a definition. A linear recurrence relation is a function or a sequence such that each term is a linear combination of previous terms. Each term can be described as a function of the previous terms. A famous example is the Fibonacci sequence: f(i) = f(i-1) + f(i-2). Linear means that the previous terms in the definition are only multiplied by a constant (possibly zero) and nothing else. So, this sequence: f(i) = f(i-1) * f(i-2) is not a linear recurrence.


Now, let’s state the problem formally.

Given f, a function defined as a linear recurrence relation. Compute f(N). N may be very large.

How to Solve

Here is the method I usually use in programming contests. I break down the method into four steps. Fibonacci sequence will be used as an example.

It is assumed that you have learned matrix and matrix operations, especially multiplication of two matrices.

Step 1. Determine K, the number of terms on which f(i) depends.

More precisely, K is the minimum integer such that f(i) doesn’t depend on f(i-M), for all M > K. For Fibonacci sequence, because the relation is:

f(i) = f(i-1) + f(i-2),

therefore, K = 2. In this way, be careful for missing terms though, for example, this sequence:

f(i) = 2f(i-2) + f(i-4)

has K = 4, because it can be rewritten explicitly as:

f(i) = 0f(i-1) + 2f(i-2) + 0f(i-3) + 1f(i-4).

Step 2. Determine vector F1, the initial values.

If each term of a recurrence relation depends on K previous terms, then it must have the first K terms defined, otherwise the whole sequence is undefined. For Fibonacci sequence (K = 2), the well-known initial values are:

  • f(1) = 1
  • f(2) = 1

Although some people may define other initial values, like f(1) = 0 and f(2) = 1, we will use the above definition in this post.

From now on, we will work extensively in matrices. We define a column vector Fi as a K x 1 matrix whose first row is f(i), second row is f(i+1), and so on, until K-th row is f(i+K-1). The initial values of f are given in column vector F1 that has values f(1) through f(K):

F_{1} = \begin{bmatrix}f(1)\\f(2)\\\vdots\\f(K)\end{bmatrix}

Step 3. Determine T, the transformation matrix.

This is the most important step in solving recurrence relation. The heart of this method is to construct a K x K matrix T, called transformation matrix, such that

TF_{i} = F_{i+1}.

Here is how to construct it. Suppose that f(i) = \sum_{j=1}^{K} c_{j} f(i-j) . You can solve this equation with any method, and obtain the result:

T = \begin{bmatrix}0&1&0&0&\cdots&0\\0&0&1&0&\cdots&0\\0&0&0&1&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\c_{K}&c_{K-1}&c_{K-2}&c_{K-3}&\cdots&c_{1}\end{bmatrix}.

More precisely, T is a K x K matrix whose last row is a vector� \begin{bmatrix}c_{K}&c_{K-1}&\cdots&c_{1}\end{bmatrix}, and for the other rows, the i-th row is a zero vector except that its (i+1)th element is 1.

Let’s apply it to our example. In Fibonacci sequence,

T = \begin{bmatrix}0&1\\1&1\end{bmatrix}.

Exercise: find out how matrix T can transforms Fi into Fi+1, and memorize the pattern.

Step 4. Determine FN.

After we construct the transformation matrix, the rest is very simple. We can obtain Fi for any i, by repeatedly multiplying T with F1. For example, to obtain F2,

F_{2} = T F_{1}.

To obtain F3,

F_{3} = T F_{2} = T^{2} F_{1}.

And so on. In general,

F_{N} = T^{N-1} F_{1}.

Therefore, the original problem is now (almost) solved: compute FN as above, and then we can obtain f(N): it is exactly the first row of FN. In case of our Fibonacci sequence, the N-th term in Fibonacci sequence is the first row of:

\begin{bmatrix}0&1\\1&1\end{bmatrix}^{N-1} \begin{bmatrix}1\\1\end{bmatrix}.

What remains is how to compute TN-1 efficiently. The most popular method is to use exponentiation by squaring method that works in O(log N) time, with this recurrence:

  • A^{p} = A \text{, if } p = 1,
  • A^{p} = A .A^{p-1} \text{, if } p \text{ is odd,}
  • A^{p} = X^{2} \text{, where } X = A^{p/2}\text{, otherwise.}

Multiplying two matrices takes O(K3) time using standard method, so the overall time complexity to solve a linear recurrence is O(K3 log N).

Sample code

Here is a sample C++ code to compute the N-th term of Fibonacci sequence, modulo 1,000,000,007.

#include <vector>
#define REP(i,n) for (int i = 1; i <= n; i++)
using namespace std;

typedef long long ll;
typedef vector<vector<ll> > matrix;
const ll MOD = 1000000007;
const int K = 2;

// computes A * B
matrix mul(matrix A, matrix B)
    matrix C(K+1, vector<ll>(K+1));
    REP(i, K) REP(j, K) REP(k, K)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;

// computes A ^ p
matrix pow(matrix A, int p)
    if (p == 1)
        return A;
    if (p % 2)
        return mul(A, pow(A, p-1));
    matrix X = pow(A, p/2);
    return mul(X, X);

// returns the N-th term of Fibonacci sequence
int fib(int N)
    // create vector F1
    vector<ll> F1(K+1);
    F1[1] = 1;
    F1[2] = 1;

    // create matrix T
    matrix T(K+1, vector<ll>(K+1));
    T[1][1] = 0, T[1][2] = 1;
    T[2][1] = 1, T[2][2] = 1;

    // raise T to the (N-1)th power
    if (N == 1)
        return 1;
    T = pow(T, N-1);

    // the answer is the first row of T . F1
    ll res = 0;
    REP(i, K)
        res = (res + T[1][i] * F1[i]) % MOD;
    return res;


Those are the basics of solving linear recurrence. Here we will discuss the variants that often occur.

* Constants in the relation

The recurrence relation may include a constant, i.e., the function is of the form f(i) = \sum_{j=1}^{K} c_{j} f(i-j) + d. In this variant, the vector F is enhanced to “remember” the value of d. It is of size (K+1) x 1 now:

F_{i} = \begin{bmatrix}f(i)\\f(i+1)\\\vdots\\f(i+K-1)\\d\end{bmatrix}.

We now want to construct a matrix T, of size (K+1) x (K+1), such that:

[ T ] \begin{bmatrix}f(i)\\f(i+1)\\\vdots\\f(i+K-1)\\d\end{bmatrix} = \begin{bmatrix}f(i+1)\\f(i+2)\\\vdots\\f(i+K)\\d\end{bmatrix}.

After learning the basic method, can you figure out the matrix T for this variant? Here it is:

T = \begin{bmatrix}0&1&0&0&\cdots&0&0\\0&0&1&0&\cdots&0&0\\0&0&0&1&\cdots&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\c_{K}&c_{K-1}&c_{K-2}&c_{K-3}&\cdots&c_{1}&1\\0&0&0&0&\cdots&0&1\end{bmatrix}.

For example, let f(i) = 2f(i-1) + 3f(i-2) + 5. Then, the matrix equation for this function is:

\begin{bmatrix}0&1&0\\3&2&1\\0&0&1\end{bmatrix} \begin{bmatrix}f(i)\\f(i+1)\\5\end{bmatrix} = \begin{bmatrix}f(i+1)\\f(i+2)\\5\end{bmatrix}.

* Odd/even conditional function

The function f may behave differently according to the parity of the argument. For example, if i is even, then f(i) = f(i-1)/2, otherwise (if i is odd) f(i) = 3f(i-1) + 1.

How to solve this variant? It is possible to split the equation into even and odd parts. We construct two matrices Teven and Todd such that:

  • T_{\text{even}} F_{i} = F_{i+1} \text{, }i \text{ is even}
  • T_{\text{odd}} F_{i} = F_{i+1} \text{, }i \text{ is odd}

We also construct matrix T = T_{\text{even}} . T_{\text{odd}}. Now, we can compute FN with a single formula:

  • F_{N} = T^{N/2} . F_{1} \text{, if } N \text { is odd,}
  • F_{N} = T_{\text{odd}} . T^{(N-1)/2} . F_{1} \text{, otherwise.}

Note that Teven and Todd must be of the same size, so in this example, convert f(i) = f(i-1)/2 into f(i) = \frac{1}{2}f(i-1) + 0 to make it look like the odd part, and then apply the standard method.

* Your variants

Have you ever encountered another variant of linear recurrence problem? Please share it in the comment section 🙂

About Ashar Fuadi

Ashar Fuadi is a competitive programmer from University of Indonesia. He loves to code, especially for TopCoder SRM, Codeforces, and ICPC.
Follow Ashar on Google+ and Twitter.


  1. One variation you can easily handle with this strategy is recurrence containing more than one functions.
    f(n) = f(n-1) + g(n-1)
    g(n) = f(n-1) + g(n-1)
    I think it is possible to convert these kind of recurrences to a single function recurrence, but when you are using the matrix exponentiation, it is easier to use it straight away.

    • “but when you are using the matrix exponentiation, it is easier to use it straight away”

      What is the “straight away” method?

    • You’re Fi will now look as follows
      Fi =
      [ f(i) f(i+1) g(i) g(i+1)]

      Now isn’t it easy to come up with the transformation matrix?

  2. Could you please post the transformation matrix in the Odd and Even Variants case. I need to verify once .

  3. some example of recurrences codes that have to count on its own like for example on this equation

    5!= 120

    could u give me some tips to solve this program ?

    thanks alot

  4. ” We also construct matrix T = T_{\text{even}} . T_{\text{odd}}. Now, we can compute FN with a single formula:

    F_{N} = T^{N/2} . F_{1} \text{, if } N \text { is odd,}
    F_{N} = T_{\text{odd}} . T^{(N-1)/2} . F_{1} \text{, otherwise.} ”

    In the above quote , I guess there is some discrepancy. Are you sure that it is true ? I guess the conditions are exchanged.

  5. coder says:

    I think it is:

    F_{N} = T^{(N-1)/2} . F_{1} \text{, if } N \text { is odd,}
    F_{N} = T_{\text{even}} . T^{(N-2)/2} . F_{1} \text{, otherwise.}

    Correct me if it is wrong.


  6. What in case of f(n)=f(n-1)+f(n-2) +/- n??

  7. Thank you for this nice post .
    How to handle recurence involving two separate functions:
    For eg->
    f[n]=f[n-1]+f[n-2]+g[n] where g[n]=g[n-1]+g[n-2] ??

    • Solution :
      g(n) = f(n) – f(n-1) – f(n-2) => g(n-1) = f(n-1) – f(n-2) – f(n-3) …..(I)
      and g(n-2) = f(n-2) – f(n-3) – f(n-4)……(II)
      of (I)+(II) g(n-1) + g(n-2) = f(n-1) – f(n-2) – f(n-3) + f(n-2) – f(n-3) – f(n-4)…(III)
      as g(n) = g(n-1)+g(n-2) => g(n) = f(n-1) – f(n-2) – f(n-3) + f(n-2) – f(n-3) – f(n-4)….(IV)
      then g(n) = f(n-1) – f(n-4)
      finally f(n) = f(n-1) + f(n-2) + f(n-1)-f(n-4) = 2f(n-1)+f(n-2)-f(n-4)

  8. The article is great!
    There is a small bug in the code:
    either MOD = 1000000007 instead of MOD = 10000000007
    or res = (res + (T[1][i] * F1[i]) % MOD) % MOD instead of res = (res + T[1][i] * F1[i]) % MOD;
    Best regards

  9. Ashar Fuadi says:

    @ Igor: Thanks, this is fixed. 🙂

  10. Abhishek Panigrahy says:

    How can i solve a recurrence relation of the form :
    F(n) = F(n-3) + n/2 + 1

  11. Nikhil Sharma says:

    How to solve the recurrence of the following specific type

    T(n+1)=T(n)+ 26^(n+1)/2

  12. Florin says:

    Thank you for this great post!

  13. unknown says:

    Can anyone tell me how the matrix turns out to be {2,2,1,0} for f(n) = f(n-1)+4f(n-2)+2f(n-3) in the below link?

  14. Can you please tell me the linear recurrence equation for ?

  15. That was really helpful

  16. This has been the clearest explanation I have found on the topic among the blogs I have looked at. Thanks a lot :D. Also, can you recommend any books that go more in-depth on the topic?

  17. if Ck is 1 (such as in the case of fibonacci series) then you can lose F1 in the math and the
    actual result is for all n>2 T^(n-1)[1,1] is the nth series element. saves a matrix multiplication.

  18. How can we solve recurrence relations involving square roots like F(N)=F(N-1)+F(N-2)+sqrt(3*F(N-2)+F(N-1)) using matrix exponentiation ?

  19. Great article..!! Was looking for such a simple yet educative article for some time now..!!

  20. Excellent post, very well written and explained! Thanks a lot for the effort. Appreciate it.

  21. There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps.
    which given in SICP exercise 1.19

  22. Thanks a lot.Great tutorial 🙂

  23. thnx learning new concept for linear recurence relation
    now i have confidence to solve it

  24. Harsh Shah says:

    What if the value of K is large, say more than 1000 ??

  25. Taj Uddin says:

    Thanks a lot. great post ,very informative and simple as well.

  26. Anonymous says:

    F_{N} = T^{N/2} . F_{1} ,- if N is odd.

    Why is it not –
    F_{N} = T^{N/2} .T^{N/2}. F(1) , if N is odd.

  27. what are the values in the last row of T, what is that c?

  28. great article

  29. Shubham Bharti says:

    @Ashar Fuadi Great post buddy. Thanks.
    Can you tell where did you encounter the Odd/Even conditional variation? I mean, can you share the question to solve?

  30. Mithun Mohan K says:

    That is really an EPIC explanation and a brilliant piece of Code Bro 🙂


  1. […] which is a very classic problem. The Nth Fibonacci number can be found in logarithmic time through fast matrix exponentiation, which is a divide and conquer algorithm. We would expect that the solution to the general problem […]

  2. […] trick: Meet in the middle Introduction to Dynamic Programming Dynamic Programming Practice Problems Solving Linear Recurrence for Programming Contest Tutorial on Trie and example problems by Lalit Kundu on Threads @ IIIT Hyderabad Binary Indexed […]

  3. Quora says:

    What is the dumbest code ever made that has become famous?

    The recursive function for Fibonacci Numbers. Fibonacci numbers are a series of numbers, in which the nth number is sum of its previous two numbers. 1, 1, 2, 3, 5, 8, 13, … The most common function to find a particular Fibonacci number is, > int fibona…

  4. […] which is a very classic problem. The Nth Fibonacci number can be found in logarithmic time through fast matrix exponentiation, which is a divide and conquer algorithm. We would expect that the solution to the general problem […]

Speak Your Mind