This blog is part of a series dedicated to linear recurrence sequences. In the Series page you can find all the posts of the series.

This post is the continuation of the previous post with the end goal of computing a closed form for any linear recurrence sequence. Details about what are these sequences and how to compute their generating function are in the first blog:

• Linear recurrence sequences

In that blog, I showed that for these sequences, their generating functions are rational functions or

\[F(z) = \frac{P(z)}{Q(z)}\]

for $P(z)$ and $Q(z)$ two polynomials of order $M-1$ and $M$, respectively. Moreover, the coefficients for these polynomials are given by initial sequence condition and the coefficients of the linear recurrence.

Now let’s assume that the poles of $F(z)$ are distinct and therefore, it is possible to write the polynomial $Q(z)$ as follow¹

\[Q(z) = q_M \prod^{M}_{i=1} (z-\eta_i).\]

This means that there is a partial fraction decomposition or expansion of generating function $F(z)$ that can be expressed as bellow²:

\[\begin{aligned} F(z) &= \sum^{M}_{i=1} \frac{r_i}{z-\eta_i} \newline &= \sum^{M}_{i=1} \frac{-\eta_i^{-1}r_i}{(1-z\eta_i^{-1})} \newline &= \sum^{M}_{i=1} \frac{-\rho_i r_i}{(1-z\rho_i)} \newline &= \sum^{M}_{i=1} -\rho_i r_i \sum_{n \geq 0} \rho_i^n z^n \newline &= \sum_{n \geq 0} \sum^{M}_{i=1} c_i \rho_i^n z^n \end{aligned}\]

where $\rho_i = \eta_i^{-1}$ are the reciprocal roots of polynomial $Q(z)$, $r_i$ are the residuals of the partial fraction decomposition, and $c_i = -\rho_i r_i$. For the last two steps, I used geometric series result:

\[\sum_{n \geq 0} x^n = \frac{1}{1-x}\]

and therefore, $F(z)$ domain needs to be defined such as

\[|z| < \frac{1}{\max_{i}|\rho_i|}\]

By definition then, recursive sequence $f_n$ generated by $F(z)$ is then given by the following equation:

\[f_n = \sum^{M}_{i=1} c_i \rho_i^n\]

that for the case of distinct poles, there is a closed-form expression for the residues of the decomposition $r_i$¹ allowing to write $c_i$ coefficients directly

\[c_i = \frac{-\rho_i P(\rho_i^{-1})}{Q'(\rho_i^{-1})}\]

It is important to realize, that the coefficient $r_i$ and reciprocal roots $\rho_i$ are not necessary real numbers. We will see that for most of the example sequences (see program examples), they are complex numbers! The use of complex number will not be an issue if you write the algorithm in a language that supports complex numbers as primitive types.

Now, we have all the necessary ingredients to write the algorithm to compute the closed form. The algorithm is rather simple, and it is easy to write in pseudocode³.

\begin{algorithm}
\caption{CloseFormV1}
\begin{algorithmic}
\FUNCTION{CloseFormV1}{$a,b$}
    \STATE $q$ = \CALL{CreateQ}{$a$}
    \STATE $\hat{q}$ = reverse of $q$
    \STATE $\rho$ = roots of the polynomial $\hat{Q}$
    \STATE $p$ = \CALL{CreateP}{$a,b$}
    \STATE $Q'$ = get the derivative of $Q$
    \FOR{$i = 0$ \TO len($\rho$)}
        \STATE $c_i = -\rho_i P(\rho^{-1}_i)/Q'(\rho^{-1}_i)$
    \ENDFOR
    \RETURN $c$, $\rho$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

This code depends of two other functions CreateP and CreateQ defined in the previous post. Moreover, the program needs some functions to manipulate polynomials that are easy to find in high-level languages. For example, find full working examples in MATLAB and python of this code.

When I started working on this project, I dreamed that I could create some generalization to the Fibonacci sequence and put my name to it! I was already naming them the Bazterra’s sequences.

Yes, I am that naive sometimes.

Anyway, I realized that most of the sequence I could think of (the trivial ones) could be found in a beautiful resource know as The On-Line Encyclopedia of Integer Sequences⁴. They provide information about the sequence themselves, and also other data as their generating function and more. I used this database to test the code on several sequences. Within the code comments, I provide the identification code for each sequence within the database so that you can verify the results by yourselves.

References