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

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 , we have to determine .

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

How to compute S? The crucial observation is that , 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:

,

with initial values:

.

After finding the matrix equation, and can be computed easily: is the first row of , and is the first row of .

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