## Solving Linear Recurrence for Programming Contest – Examples

After grasping the basic method of solving linear recurrence, let’s apply it in real problems.

SPOJ Recursive Sequence

This is a classical problem that is directly solvable using the basic method I explained in the previous post. It is expected that you solve this problem and master the basic method before solving the next problems.

SPOJ Recursive Sequence (Version II)

A slightly harder version of the previous problem. This time, instead of determining $a_{n}$, we have to determine $a_{m} + a_{m+1} + \cdots + a_{n}$.

Let’s simplify the problem first, using a well-known technique called partial sum. Define a series $S$, where $S_{i} = a_{1} + a_{2} + \cdots + a_{i}$, with $S_{0} = 0$. Then, the result we are looking for is exactly $S_{n} - S_{m-1}$ (prove that). So, instead of determining (n – m + 1) terms of sequence $a$, it is sufficient to determine only two terms of series $S$.

How to compute S? The crucial observation is that $S_{i} = S_{i-1} + a_{i}$, i.e., S itself is a linear recurrence! So, we can adopt the matrix equation of a to incorporate S. The final matrix equation of would look like this:

$\begin{bmatrix}1&1&0&0&\cdots&0\\0&0&1&0&\cdots&0\\0&0&0&1&\cdots&0\\0&0&0&0&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&c_{k}&c_{k-1}&c_{k-2}&\cdots&c_{1}\end{bmatrix} \begin{bmatrix}S_{i-1}\\a_{i}\\a_{i+1}\\a_{i+2}\\\vdots\\a_{i+k-1}\end{bmatrix} = \begin{bmatrix}S_{i}\\a_{i+1}\\a_{i+2}\\a_{i+3}\\\vdots\\a_{i+k}\end{bmatrix}$,

with initial values:

$\begin{bmatrix}S_{0} = 0\\b_{1}\\b_{2}\\b_{3}\\\vdots\\b_{k}\end{bmatrix}$.

After finding the matrix equation, $S_{n}$ and $S_{m-1}$ can be computed easily: $S_{n}$ is the first row of $T^{n}F_{1}$, and $S_{m-1}$ is the first row of $T^{m-1}F_{1}$.

You may also want to solve SPOJ Fibonacci Sum. It uses exactly the same idea. [Read more…]

## 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.

## Definition

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.

## Problem

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. [Read more…]