# Constant term evaluation for summation of C-finite sequences

Qing-Hu Hou<fnref n="1" /> and Guoce Xin<fnref n="2" />

**Abstract.** Based on constant term evaluation, we present a new method to compute a closed form of the summation $\sum_{k=0}^{n-1} \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j)$, where $\{F_j(k)\}$ are C-finite sequences and $a_j$ and $b_j + c_j$ are nonnegative integers. Our algorithm is much faster than that of Greene and Wilf.

**Résumé.** En s'appuyant sur l'évaluation de termes constants, nous présentons une nouvelle méthode pour calculer une forme close de la somme $\sum_{k=0}^{n-1} \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j)$, où les $\{F_j(k)\}$ sont des suites C-finies, et où les $a_j$ et les $b_j + c_j$ sont des entiers positifs ou nuls. Notre algorithme est beaucoup plus rapide que celui de Greene et Wilf.

**Keywords:** C-finite sequences, constant term, summation, closed form

## 1 Introduction

A sequence $\{F(k)\}_{k \ge 0}$ is C-finite (see [Ze190]) if there exist constants $c_1, \dots, c_d$ such that

$$F(k) = c_1 F(k-1) + c_2 F(k-2) + \dots + c_d F(k-d), \quad \forall k \ge d.$$

Correspondingly, the integer $d$ is called the order of the recurrence. Greene and Wilf [GW07] provided a method to compute a closed form of the summation

$$\sum_{k=0}^{n-1} \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j),$$

where $\{F_j(k)\}$ are C-finite sequences and $a_j, b_j$ are integers satisfying $a_j \ge 0$ and $a_j + b_j \ge 0$. They proved that the sum must be a linear combination of the terms

$$\prod_{j=1}^{r} F_j((a_j + b_j)n + i_j) \quad \text{and} \quad \phi_{i_1, \dots, i_r}(n) \prod_{j=1}^{r} F_j(a_j n + i_j), \quad (0 \le i_j < d_j)$$

where $d_j$ is the order of the recurrence of $\{F_j(k)\}$ and $\phi_{i_1, \dots, i_r}(n)$ is a polynomial in $n$ with given degree bound. Then the explicit formula of the sum can be computed by the method of undetermined coefficients.

<footnote n="1">¹Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, PR China</footnote>

<footnote n="2">²Department of Mathematics, Capital Normal University, Beijing 100084, PR China</footnote>

<footnote n="1">¹hou@nankai.edu.cn, ²guoce.xin@gmail.com</footnote>
In this paper, we provide another approach which is based on MacMahon's partition analysis [Mac16] and the Omega calculations [APR01, Xin04]. We first introduce an extra variable $z$ and consider the summation

$$S(z) = \sum_{k=0}^{n-1} z^k \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j).$$

Then we rewrite $S(z)$ as the constant term (with respect to $x_1, \dots, x_r$) of the Laurent series

$$f_1(x_1)f_2(x_2)\cdots f_r(x_r) \sum_{k=0}^{n-1} z^k \prod_{j=1}^{r} x_j^{-a_j n - b_j k - c_j},$$

where

$$f_j(x_j) = \sum_{k=0}^{\infty} F_j(k) x_j^k$$

is the generating function. Using partial fraction decomposition, we can derive an explicit formula for $S(z)$ in terms of $\prod_{j=1}^{r} F_j((a_j + b_j)n + i_j)$ and $\prod_{j=1}^{r} F_j(a_j n + i_j)$, where $0 \le i_j < d_j$. Finally, the substitution of $z = 1$ leads to a closed form of the original summation.

## 2 Basic tools by partial fraction decomposition

Let $K$ be a field. Fix a polynomial $D(x) \in K[x]$. For any polynomial $P(x) \in K[x]$, we use $\text{rem}(P(x), D(x), x)$ (or $\text{rem}(P(x), D(x))$ for short) to denote the remainder of $P(x)$ when divided by $D(x)$. This notation is extended for rational function $R(x) = P(x)/Q(x)$ when $Q(x)$ is coprime to $D(x)$:

$$\text{rem}(R(x), D(x)) := \text{rem}(P(x)\beta(x), D(x)), \text{ if } \alpha(x)D(x) + \beta(x)Q(x) = 1. \quad (1)$$

In algebraic language, the remainder is the standard representative in the quotient ring $K[x]/\langle D(x) \rangle$.

It is convenient for us to use the following notation:

$$\left\{ \frac{P(x)}{D(x)} \right\} = \frac{\text{rem}(P(x)/Q(x), D(x))}{D(x)}. \qquad (2)$$

Equivalently, if we have the following partial fraction decomposition:

$$\frac{P(x)}{Q(x)D(x)} = p(x) + \frac{r_1(x)}{D(x)} + \frac{r_2(x)}{Q(x)},$$

where $p(x), r_1(x), r_2(x)$ are polynomials with $\deg r_1(x) < \deg D(x)$, then we claim that $r_1(x) = \text{rem}(P(x)/Q(x), D(x))$ and hence

$$\left\{ \frac{P(x)}{D(x)} \right\} = \frac{r_1(x)}{D(x)}.$$

Note that we do not need $\deg r_2(x) < \deg Q(x)$.
The following properties are transparent:

$$P_1(x) \equiv P_2(x) \pmod{D(x)} \Rightarrow \left\{ \frac{R(x)P_1(x)}{D(x)} \right\} = \left\{ \frac{R(x)P_2(x)}{D(x)} \right\}; \quad (3)$$

$$\alpha(x)D(x) + \beta(x)Q(x) = 1 \Rightarrow \left\{ \frac{P(x)/Q(x)}{D(x)} \right\} = \left\{ \frac{P(x)\beta(x)}{D(x)} \right\}; \quad (4)$$

$$\left\{ \frac{aR_1(x) + bR_2(x)}{D(x)} \right\} = a \left\{ \frac{R_1(x)}{D(x)} \right\} + b \left\{ \frac{R_2(x)}{D(x)} \right\}, \quad \forall a, b \in K. \quad (5)$$

The crucial lemma in our calculation is as follows.

**Lemma 1** Let $R(x), D(x)$ be as above and assume $D(0) \neq 0$. Then for any Laurent polynomial $L(x)$ with $\deg L(x) \le 0$, we have

$$\mathrm{CT}_x L(x) \left\{ \frac{R(x)}{D(x)} \right\} = \mathrm{CT}_x \left\{ \frac{L(x)R(x)}{D(x)} \right\}, \quad (6)$$

where $\mathrm{CT}_x g(x)$ means to take constant term of the Laurent series $g(x)$ in $x$.

**Proof:** By linearity, we may assume $L(x) = x^{-k}$ for some $k \ge 0$.

Assume $r(x) = \mathrm{rem}(R(x), D(x))$. Since $D(0) \neq 0$, we have the following partial fraction decomposition:

$$\frac{r(x)}{x^k D(x)} = \frac{p(x)}{x^k} + \frac{r_1(x)}{D(x)},$$

where $\deg p(x) < k$ and $\deg r_1(x) < \deg D(x)$. Then taking constant term in $x$ gives

$$\mathrm{CT}_x \frac{r(x)}{x^k D(x)} = \mathrm{CT}_x \frac{r_1(x)}{D(x)} = \mathrm{CT}_x \left\{ \frac{x^{-k}r(x)}{D(x)} \right\} = \mathrm{CT}_x \left\{ \frac{x^{-k}R(x)}{D(x)} \right\}.$$

This is just (6) when $L(x) = x^{-k}$.

<figure><img src="image_1.png" /></figure>

Let $\mathbb{Z}$ and $\mathbb{N}$ denote the set of integers and nonnegative integers respectively. Suppose that $\{F(k)\}_{k \in \mathbb{N}}$ is a C-finite sequence such that

$$F(k) = c_1 F(k-1) + c_2 F(k-2) + \dots + c_d F(k-d) \quad (7)$$

holds for any integer $k \ge d$. Then its generating function is of the form

$$f(x) = \sum_{k=0}^{\infty} F(k)x^k = \frac{p(x)}{1 - c_1x - c_2x^2 - \dots - c_d x^d},$$

where $p(x)$ is a polynomial in $x$ of degree less than $d$. We will say that $\{F(k)\}_{k \ge \mathbb{N}}$ is a C-finite sequence with generating function $p(x)/q(x)$, where $q(x) = 1 - c_1x - c_2x^2 - \dots - c_d x^d$.

It is well-known [Sta86, Section 4.2] that we can uniquely extend the domain of $F(k)$ to $k \in \mathbb{Z}$ by requiring that (7) holds for any $k \in \mathbb{Z}$. The $k$-th term of the extended sequence can be given by the following lemma.
**Lemma 2** Let {$F(k)$}$_{k \in \mathbb{N}}$ be a C-finite sequence with generating function $p(x)/q(x)$ and {$F(k)$}$_{k \in \mathbb{Z}}$ be its extension. Then

$$F(k) = \mathrm{CT}_x \left\{ \frac{x^{-k}p(x)}{q(x)} \right\} = \left\{ \frac{x^{-k}p(x)}{q(x)} \right\} \bigg|_{x=0} \quad \forall k \in \mathbb{Z}. \qquad (8)$$

**Proof:** Since $q(0) = 1$, the second equality holds trivially. Let

$$G(k) = \mathrm{CT}_x \left\{ \frac{x^{-k}p(x)}{q(x)} \right\}.$$

Then for $k \ge 0$, applying Lemma 1 gives

$$G(k) = \mathrm{CT}_x x^{-k} \left\{ \frac{p(x)}{q(x)} \right\} = \mathrm{CT}_x x^{-k} \frac{p(x)}{q(x)} = [x^k]f(x) = F(k),$$

where $[x^k]f(x)$ means to take the coefficient of $x^k$ in $f(x)$.

Therefore, by the uniqueness of the extension, it suffices to show that $G(k)$ also satisfy the recursion (7) for all $k \in \mathbb{Z}$. We compute as follows:

$$\begin{aligned} G(k) - c_1 G(k-1) - \dots - c_d G(k-d) \\ &= \mathrm{CT}_x \left\{ \frac{x^{-k}p(x)}{q(x)} \right\} - c_1 \left\{ \frac{x^{-k+1}p(x)}{q(x)} \right\} - \dots - c_d \left\{ \frac{x^{-k+d}p(x)}{q(x)} \right\} \\ &= \mathrm{CT}_x \left\{ \frac{x^{-k}p(x)q(x)}{q(x)} \right\} = 0. \end{aligned}$$

This completes the proof. □

### 3 Constant term evaluation

Let {$F_j(k)$}$_{k \in \mathbb{Z}}$ be C-finite sequences with generating functions $f_j(x) = p_j(x)/q_j(x)$ for $j = 1, 2, \dots, r$. We denote the degree of the denominators by $d_j = \deg q_j(x)$. To evaluate the sum

$$S = \sum_{k=0}^{n-1} \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j),$$

we evaluate the more general sum $S_r(z)$ instead, where $S_m(z)$ is defined by

$$S_m(z) = \sum_{k=0}^{n-1} z^k \prod_{j=1}^{m} F_j(a_j n + b_j k + c_j), \quad 0 \le m \le r. \qquad (9)$$
The advantage is that $S_m(z)$ can be evaluated recursively. Since $a_j \ge 0$ and $a_j + b_j \ge 0$, we have $a_j n + b_j k \ge 0$ for any $n \ge 0$ and $0 \le k < n$. By Lemmas 1 and 2, we have

$$
\begin{align*}
S_m(z) &= \sum_{k=0}^{n-1} z^k \prod_{j=1}^{m-1} F_j(a_j n + b_j k + c_j) \text{CT}_x \left\{ \frac{x^{-a_m n - b_m k - c_m} p_m(x)}{q_m(x)} \right\} \\
&= \sum_{k=0}^{n-1} z^k \prod_{j=1}^{m-1} F_j(a_j n + b_j k + c_j) \text{CT}_x x^{-a_m n} x^{-b_m k} \left\{ \frac{x^{-c_m} p_m(x)}{q_m(x)} \right\} \\
&= \text{CT}_x x^{-a_m n} \left\{ \frac{x^{-c_m} p_m(x)}{q_m(x)} \right\} \sum_{k=0}^{n-1} (zx^{-b_m})^k \prod_{j=1}^{m-1} F_j(a_j n + b_j k + c_j).
\end{align*}
$$

Therefore, we obtain the recursion

$$
S_m(z) = \text{CT}_x x^{-a_m n} \left\{ \frac{p_m(x) x^{-c_m}}{q_m(x)} \right\} S_{m-1}(zx^{-b_m}). \quad (10)
$$

The initial condition is $S_0(z) = 1 + z + \cdots + z^{n-1} = \frac{1-z^n}{1-z}$.

Let $L_m$ and $L'_m$ be the linear operators acting on Laurent polynomials in $x_1, \dots, x_m$ by

$$
L_m \left( \prod_{j=1}^{m} x_j^{\alpha_j} \right) = \prod_{j=1}^{m} F_j (a_j n - \alpha_j), \quad (11)
$$

$$
L'_{m} \left( \prod_{j=1}^{m} x_{j}^{\alpha_{j}} \right) = \prod_{j=1}^{m} F_{j}((a_{j} + b_{j})n - \alpha_{j}).
$$

Then $S_m(z)$ have simple rational function representations.

**Theorem 3** For any $0 \le m \le r$, there exist a polynomial $P_m(z)$ with coefficients being Laurent polynomials in $x_1, \dots, x_m$ and a non-zero polynomial $Q_m(z) \in K[z]$ such that

$$
S_m(z) = \frac{L_m(P_m(z)) - z^n L'_m(P_m(z))}{Q_m(z)}, \quad (12)
$$

where $L_m, L'_m$ are defined by (11).

**Proof:** We prove the theorem by induction on $m$.

Setting $P_0(z) = 1$ and $Q_0(z) = 1-z$, we see that the assertion holds for $m=0$. Suppose that the assertion holds for $m-1$. We can compute $P_m(z)$ and $Q_m(z)$ as follows. For brevity, we write $R(z) = P_{m-1}(z)/Q_{m-1}(z)$.

By definition $S_{m-1}(z)$ is a polynomial in $z$ of degree less than $n$. If $b_m \ge 0$, then $-a_m n \le 0$; If $b_m \le 0$, then $-a_m n - b_m(n-1) \le 0$. Thus $x^{-a_m n} S_{m-1}(zx^{-b_m})$ is always a Laurant polynomial of
degree no more than 0. Therefore, by Lemma 1 and the recursion (10), we have

$$
\begin{align*}
S_m(z) &= \text{CT}_x \left\{ \frac{p_m(x)x^{-c_m}}{q_m(x)} \right\} x^{-a_m n} S_{m-1}(zx^{-b_m}) \\
&= \text{CT}_x \left\{ \frac{p_m(x)x^{-c_m} x^{-a_m n} S_{m-1}(zx^{-b_m})}{q_m(x)} \right\} \\
&= \text{CT}_x \left\{ \frac{p_m(x)x^{-c_m} x^{-a_m n} (L_{m-1}(R(zx^{-b_m})) - z^n x^{-b_m n} L'_{m-1}(R(zx^{-b_m})))}{q_m(x)} \right\} \\
&= L_{m-1} \text{CT}_x x^{-a_m n} G(x, z) - z^n L'_{m-1} \text{CT}_x x^{-(a_m+b_m)n} G(x, z),
\end{align*}
$$

where $G(x, z)$ is given by

$$
G(x, z) = \left\{ \frac{p_m(x) x^{-c_m} R(zx^{-b_m})}{q_m(x)} \right\} .
$$

Now set

$$
\frac{u(x, z)}{w(z)} = \operatorname{rem}\left(x^{d_m-1-c_m} R(zx^{-b_m}), q_m(x), x\right), \quad (13)
$$

where $u(x, z)$ is a polynomial in $x$, $z$ and $w(z)$ is a polynomial in $z$. Then

$$
\begin{align*}
G(x, z) &= \left\{ \frac{p_m(x) x^{-d_m+1} \cdot x^{d_m-1-c_m} R(zx^{-b_m})}{q_m(x)} \right\} \\
&= \left\{ \frac{p_m(x) x^{-d_m+1} u(x, z) / w(z)}{q_m(x)} \right\} \\
&= \frac{1}{w(z)} \left\{ \frac{p_m(x) \cdot x^{-d_m+1} u(x, z)}{q_m(x)} \right\}.
\end{align*}
$$

Since $x^{-d_m+1}u(x,z)$ is a Laurent polynomial of degree in $x$ less than or equal to 0, we obtain

$$
\begin{align*}
S_m(z) &= L_{m-1} \text{CT}_x \frac{x^{-d_m+1} u(x,z)}{x^{a_m n}} \left\{ \frac{p_m(x)}{q_m(x)} \right\} - z^n L'_{m-1} \text{CT}_x \frac{x^{-d_m+1} u(x,z)}{x^{(a_m+b_m)n}} \left\{ \frac{p_m(x)}{q_m(x)} \right\} \\
&= L_{m-1} \text{CT}_x \frac{x^{-d_m+1} u(x,z)}{x^{a_m n}} f_m(x) - z^n L'_{m-1} \text{CT}_x \frac{x^{-d_m+1} u(x,z)}{x^{(a_m+b_m)n}} f_m(x).
\end{align*}
$$

Now set

$$
P_m(z) = x_m^{-d_m+1} u(x_m, z), \quad Q_m(z) = w(z). \tag{14}
$$

It is then easy to check that $S_m(z)$ has the desired form. This completes the induction. $\square$

<figure><img src="image_2.png" /></figure>

**Remark 1.** Form the above proof we see that the degree of $x_m$ in $P_m(z)$ is between $-d_m + 1$ and 0.
Therefore the coefficients of the numerator of $S(z)$ are linear combinations of the form

$$
\prod_{j=1}^{r} F_j(a_j n + i_j), \quad \prod_{j=1}^{r} F_j((a_j + b_j)n + i_j),
$$
where $0 \le i_j \le d_j - 1$.

**Remark 2.** Let $\{F(k)\}$ be a sequence with generating function $p(x)/q(x)$. We call the sequence $\{\overline{F}(k)\}$ with generating function $1/q(x)$ its *primitive sequence*. It is more convenient to represent $S(z)$ in terms of the *primitive sequences* $\{\overline{F}_j(k)\}$ instead of the sequences $\{F_j(k)\}$ themselves. The existence of such a representation is obvious since $F_j(k)$ is a linear combination of $\overline{F}_j(k)$. In this way, the coefficients of the numerator of $S(z)$ will be linear combinations of the form

$$ \prod_{j=1}^{r} \overline{F}_j(a_j n - i_j), \quad \prod_{j=1}^{r} \overline{F}_j((a_j + b_j)n - i_j), $$

where $0 \le i_j \le d_j - 1$. Then we can take advantage of the fact $\overline{F}_j(-i_j) = 0$, $1 \le i_j \le d_j - 1$ if $a_j = 0$ or $a_j + b_j = 0$. The computation is similar and in a natural way. In fact, if we define

$$ \frac{P_m(z)}{Q_m(z)} = \operatorname{rem} \left( p_m(x) x^{-c_m} \frac{P_{m-1}(zx^{-b_m})}{Q_{m-1}(zx^{-b_m})}, q_m(x), x \right), $$

then we have

$$ S_m(z) = \frac{\overline{L}_m(P_m(z)) - z^n \overline{L}'_m(P_m(z))}{Q_m(z)}, $$

where

$$ \overline{L}_m \left( \prod_{j=1}^{m} x_j^{\alpha_j} \right) = \prod_{j=1}^{m} \overline{F}_j (a_j n - \alpha_j), $$

$$ \overline{L}'_m \left( \prod_{j=1}^{m} x_j^{\alpha_j} \right) = \prod_{j=1}^{m} \overline{F}_j ((a_j + b_j)n - \alpha_j). $$

# 4 Evaluation of $S_r(z)$ at $z = 1$

In this section, we consider the evaluation of $S_r(z)$ at $z = 1$, which is equal to the sum

$$ S = \sum_{k=0}^{n-1} \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j). \qquad (15) $$

The evaluation of $S_r(z)$ at $z = 1$ can be obtained by the following lemma.

**Lemma 4** Let $f(z) = \sum_i f_i z^i$, $g(z) = \sum_i g_i z^i$ and $h(z) = \sum_i h_i z^i$ be polynomials in $z$. Suppose that

$$ S(z) = \frac{f(z) - z^n g(z)}{h(z)} $$

is a polynomial in $z$ and

$$ h(z) = \sum_{i \geq e} \tilde{h}_i (z - 1)^i, \quad \tilde{h}_e \neq 0. \qquad (16) $$

Then

$$ S(1) = \frac{1}{\tilde{h}_e} \sum_i \left( f_i \binom{i}{e} - g_i \binom{n+i}{e} \right). $$
**Proof:** By expanding $f(z) - z^n g(z)$ at the point $z = 1$, we obtain

$$f(z) - z^n g(z) = \sum_{i} f_i(z - 1 + 1)^i - g_i(z - 1 + 1)^{n+i} = \sum_{j} (z - 1)^j A_j,$$

where

$$A_j = \sum_i \left( f_i \binom{i}{j} - g_i \binom{n+i}{j} \right).$$

Since $S(z)$ is a polynomial in $z$ and $\tilde{h}_e \neq 0$, we have $A_j = 0$ for any $j < e$ and $S(1) = A_e/\tilde{h}_e$, as desired. □

*Remark.* Alternatively, we can write

$$S(z) = z^n \frac{z^{-n} f(z) - g(z)}{h(z)}.$$

A similar argument yields

$$S(1) = \frac{1}{\tilde{h}_e} \sum_i \left( f_i \binom{i-n}{e} - g_i \binom{i}{e} \right),$$

The algorithm CFsum for finding a closed form of the sum (15).

*Input:* The generating functions $p_j(x)/q_j(x)$ of $F_j(k)$ and the parameters $(a_j, b_j, c_j)$

*Output:* A closed formula for $S = \sum_{k=0}^{n-1} \prod_{j=1}^{r} F_j(a_j n + b_j k + c_j)$.

1. Initially set $P(z) = 1$ and $Q(z) = 1 - z$.

2. For $j = 1, 2, \dots, r$ do

Set $R(z) = P(z)/Q(z)$.

Let

$$\frac{u(x, z)}{w(z)} = \text{rem}(p_j(x)x^{-c_j} R(zx^{-b_j}), q_j(x), x).$$

Set $P(z) = u(x_j, z)$ and $Q(z) = w(z)$.

3. Set $A = B = P$.

4. For $j = 1, 2, \dots, r$ do

$$A = \sum_{i=0}^{d_j-1} \bar{F}_j(a_j n + d_j - i) [x_j^i] A, \quad B = \sum_{i=0}^{d_j-1} \bar{F}_j((a_j + b_j)n + d_j - i) [x_j^i] B,$$

where $[x^i]f(x)$ denotes the coefficient of $x^i$ in $f(x)$ and $\{\bar{F}_j(k)\}$ is the primitive sequence corresponding to $\{F_j(k)\}$.

5. Let $e$ be the lowest degree of $z$ in $Q(z+1)$ and $h = [z^e]Q(z+1)$.
6. Finally, return

$$S = \frac{1}{h} \sum_{i} \left( \binom{i}{e} [z^i] A - \binom{n+i}{e} [z^i] B \right).$$

Our algorithm suggested a new way to look at the degree bound for the coefficients $\phi_{i_1, \dots, i_r}(n)$. One bound is just the multiplicity of 1 as a root of $Q_r(z)$. To study the $e$ described in (16), it is better to use the alternative representation of $S(z) = S_r(z)$:

$$S(z) = \mathrm{CT}_{x_1, \dots, x_r} \left( \frac{1}{x_1^{a_1} \cdots x_r^{a_r}} \right)^n \frac{1 - \left( \frac{z}{x_1^{b_1} \cdots x_r^{b_r}} \right)^n}{1 - \frac{z}{x_1^{b_1} \cdots x_r^{b_r}}} \prod_{j=1}^r \left\{ \frac{p_j(x_j) x_j^{-c_j}}{q_j(x_j)} \right\}.$$

Suppose that $\alpha_j$ is a root of $q_j(x)$ with multiplicity $\nu_j(\alpha_j)$. By partial fraction decomposition, $S(z)$ can be written as a linear combination of the terms

$$S(z; \alpha, s) = \mathrm{CT}_{x_1, \dots, x_r} \left( \frac{1}{x_1^{a_1} \cdots x_r^{a_r}} \right)^n \frac{1 - \left( \frac{z}{x_1^{b_1} \cdots x_r^{b_r}} \right)^n}{1 - \frac{z}{x_1^{b_1} \cdots x_r^{b_r}}} \prod_{j=1}^r \frac{1}{1 - x_j / \alpha_j} s_j,$$

where $s_j \le \nu_j(\alpha_j)$. From the discussion on Omega operator [Xin04], we see that the denominator of $S(z; \alpha, s)$ is given by

$$\left(1 - \frac{z}{\alpha_1^{b_1} \cdots \alpha_r^{b_r}}\right)^{s_1 + s_2 + \cdots + s_r - r + 1}$$

Therefore, by summing over all $\alpha, s$ and take common denominator, we see that

$$e \le \max\{\nu_1 + \cdots + \nu_r - r + 1 : \alpha_1^{b_1} \cdots \alpha_r^{b_r} = 1 \text{ and } q_j(\alpha_j) = 0\}.$$

# 5 Examples

We have implement the algorithm CFSum in Maple, which can be download from http://www.combinatorics.net.cn/homepage/xin/maple/CFsum.txt.

**Example 1.** Let

$$f(n) = \sum_{k=0}^{n-1} F(k)^2 F(2n-k),$$

where $\{F(k)\}$ is the Fibonacci sequence defined by

$$F(0) = 0, F(1) = 1, F(k) = F(k-1) + F(k-2), \forall k \ge 2.$$

We see that the generating function for $\{F(k)\}$ is $x/(1-x-x^2)$. Using the package, we immediately derive that

$$f(n) = \frac{1}{2}(-\bar{F}(2n) + \bar{F}(2n-1) + \bar{F}(n)^3 + \bar{F}(n)\bar{F}(n-1)^2 - \bar{F}(n-1)\bar{F}(n)^2),$$
where {$\overline{F}(k)$} is the primitive sequence of {$F(k)$}. In fact, $\overline{F}(k) = F(k + 1)$ and hence

$$f(n) = \frac{1}{2}(-F(2n + 1) + F(2n) + F(n + 1)^3 + F(n + 1)F(n)^2 - F(n)F(n + 1)^2).$$

**Example 2.** Let

$$S(z) = \sum_{k=0}^{n-1} F(k)^4 z^k,$$

where {$F(k)$} is the Fibonacci sequence defined as in Example 1. Using the package, we find that

$$S(z) = \frac{\sum_{i=0}^{4} f_i(z) z^n \overline{F}(n-1)^i \overline{F}(n)^{4-i} - z(z+1)(z^2-5z+1)}{(z-1)(z^2+3z+1)(z^2-7z+1)} \\ = \frac{\sum_{i=0}^{4} f_i(z) z^n F(n)^i F(n+1)^{4-i} - z(z+1)(z^2-5z+1)}{(z-1)(z^2+3z+1)(z^2-7z+1)},$$

where

$$f_0(z) = z(z+1)(z^2-5z+1), \quad f_1(z) = -4z^2(z^2-3z-1), \quad f_2(z) = 6z^2(z^2-z+1),$$

and

$$f_3(z) = -4z^2(z^2+3z-1), \quad f_4(z) = z^4+11z^3-14z^2-5z+1.$$

# 6 D-finite sequence involved

The readers are referred to [Sta99, Chapter 6.4] for definitions of D-finite generating functions and P-recursive sequence. Let {$G(k)$}$_{k \in \mathbb{N}}$ be a P-recursive sequence with D-finite generating function $g(x)$. We wish to find a similar representation of the sum

$$S = \sum_{k=0}^{n-1} \prod_{j=1}^{r+1} F_j(k)$$

with $F_j$ as before except for $F_{r+1}(k) = G(k)$ being P-recursive. We shall only consider the case $c_r = 0$ for brevity.

Define $S_m(z)$ as in (9). The recursion (10) still holds for $m \le r$, and a similar calculation yields

$$S_{r+1}(z) = \text{CT}_x x^{-a_{r+1}n} g(x) S_r(zx^{-b_{r+1}}).$$

By Theorem 3, we can write

$$S_r(z) = \frac{L_r(P_r(z)) - z^n \tilde{L}_r(P_r(z))}{Q_r(z)}. \qquad (17)$$
Since $S_r(z)$ is a polynomial in $z$ of degree less than $n$, $\deg P_r(z) < \deg Q_r(z)$ and $Q_r(0) \neq 0$.
Now put (17) into the recursion and set $z = 1$, we obtain

$$S_{r+1}(1) = \text{CT}_x x^{-a_{r+1}n} g(x) \frac{L_r(P_r(x^{-b_{r+1}})) - x^{-nb_{r+1}} \tilde{L}_r(P_r(x^{-b_{r+1}}))}{Q_r(x^{-b_{r+1}})}$$

This expression can be written as

$$S_{r+1}(1) = \text{CT}_x x^{-a_{r+1}n} \bar{g}(x) L_r(\bar{P}(x)) - x^{-n(a_{r+1}+b_{r+1})} \tilde{L}_r(\bar{P}(x)) \bar{g}(x),$$

where $\bar{g}(x) = g(x)\bar{Q}(x)^{-1}$, with

$$\frac{P_r(x^{-b_{r+1}})}{Q_r(x^{-b_{r+1}})} = \frac{\bar{P}(x)}{\bar{Q}(x)}$$

being in its standard representation.

Now if we let $\bar{G}(k) = [x^k]\bar{g}(x)$. Then we have a representation of $S_{r+1}(1)$ by a linear combination of terms of the form

$$\prod_{j=1}^{r+1} \bar{F}_j(u_j n + v_j),$$

where $\bar{F}_j(k)$ is the primitive sequence of $F_j(k)$ as before, except that $\bar{F}_{r+1}(k) = \bar{G}(k)$.

It is clear that $\bar{g}(x)$ is also D-finite and hence $\bar{G}(k)$ is P-recursive. It can be shown that if $G(k)$ satisfy a P-recursion of order $e$ then we can find for $\bar{G}(k)$ a P-recursion of order $e + \deg \bar{Q}(x)$.

# Acknowledgements

## References

[APR01] G.E. Andrews, P. Paule, and A. Riese. Macmahon's partition analysis iii: the Omega package. *Europ. J. Combin.*, 22:887–904, 2001.

[GW07] C. Greene and H.S. Wilf. Closed form summation of C-finite sequences. *Trans. AMS*, 359(3):1161–1190, 2007.

[Mac16] P.A. MacMahon. *Combinatory Analysis*, 2 volumes. Cambridge University, 1915–1916. (Reprinted: Chelsea, New York, 1960).

[Sta86] R.P. Stanley. *Enumerative Combinatorics, I*. Wadsworth & Brooks/Cole, 1986. (Reprinted: Cambridge University Press, 1997).

[Sta99] R.P. Stanley. *Enumerative Combinatorics, II*. Cambridge University Press, 1999.

[Xin04] G. Xin. A fast algorithm for MacMahon's partition analysis. *Electron. J. Combin.*, 11:R58, 2004.

[Zei90] D. Zeilberger. A holonomic systems approach to special functions identities. *J. Comput. Appl. Math.*, 32:321–368, 1990.