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