Sum of second order recurrence relation, non constant coëfficients

Question

Is there a general way to calculate the sum of a second order recurrence relation with non constant coëfficients? In my case, I have $$N_i = A_iN_{i-1} + B_iN_{i-2}.$$ Where I'm particularly interested in $$\sum_{i=0}^m N_i$$

For my case, the problems might simplify due to the boundary conditions $$N_0 = 1,$$ $$N_1 = 0$$ such that in principle it should be possible to write the sum als a function of all the $A$'s and $B$'s.

Any ideas?

Answer 1

Okay, so I found a general workaround that might or might not be helpful. In my case, it does speed up the calculation, so I thought I'd share it.

First, let me rewrite the recurrence relation a little: $$ N_{i-1} = A_{i-1}N_{i-2} + B_{i-1}N_{i-3} $$ Which can be substituted in the original expression for $N_i$: $$ N_i = (A_iA_{i-1} + B_i)N_{i-2} + A_{i-1}B_{i-1}N_{i-3} $$

The recurrence relation can then be written as a matrix product:

$$ \left(\begin{matrix} N_{i} \\ N_{i-1} \end{matrix} \right) = \left(\begin{matrix} A_iA_{i-1} + B_i & A_{i-1}B_{i-1} \\ A_{i-1} & B_{i-1} \end{matrix}\right) \left(\begin{matrix} N_{i-2} \\ N_{i-3} \end{matrix}\right) $$

We can now define $M_i$ to be the $2\times2$ matrix on the right-hand-side. Assuming the boundary conditions $N_0$ and $N_1$ are known, we have $$ \left(\begin{matrix} N_{i} \\ N_{i-1} \end{matrix} \right) = M_iM_{i-2}\dots M_1\left(\begin{matrix} N_1 \\ N_0 \end{matrix}\right) $$ Where $M_1 = I_2$.

Of course, this specific case only works for odd $i$, but can be reformulated for even $i$ just as easily. In my case, I could even rewrite the sum over $N_i$ as a sum of traces. This was due to one of the boundary conditions being zero, but I won't go into these details.

Answer 2

My rule of thumb is that the recurrence or summation problems are always harder than the equivalent differential equation or integral. Differential equations with non-constant coefficients are generally very hard. So recurrence relations will be that much harder. Usually the answer depends on the specifics of the problem, and it is often a clever trick that answers it.