Recurrence Relations for Sums of Binomial Coefficients and Some Generalizations

Eduardo H. M. Brietzke Instituto de Matemática e Estatística Universidade Federal do Rio Grande do Sul Porto Alegre, CEP 91509-900 Brazil

                 brietzke@mat.ufrgs.br

Abstract

We develop a new method for the discovery and proof of recurrences for sums of binomial coefficients which is easy to apply and consists of justifying that it is enough to verify the recurrence for finitely many values of n, provided an extra condition is satisfied. This method can easily be implemented by using software. We also consider the case of a Riordan array instead of Pascal’s triangle.

1 Introduction

In 1969, Andrews [1] discovered two new identities relating the sequence of Fibonacci numbers to Pascal’s triangle,

F_{n} = ∑_{k=−∞}^{∞}(−1)^{k}\binom{n − 1}{⌊\frac{1}{2}(n − 1 − 5k)⌋}  (1)

and

F_{n} = ∑_{k=−∞}^{∞}(−1)^{k}\binom{n}{⌊\frac{1}{2}(n − 1 − 5k)⌋}.  (2)

Different proofs of (1) and (2) have been given by Gupta [8] and Hirschhorn [9, 10]. As indicated by Gupta [8], identities (1) and (2) are equivalent to

F_{2n+1} = ∑_{j=−∞}^{∞}(\binom{2n + 1}{n − 5j} − \binom{2n + 1}{n − 5j − 1}),  (3)

F_{2n+2} = ∑_{j=−∞}^{∞}(\binom{2n + 2}{n − 5j} − \binom{2n + 2}{n − 5j − 1})  (4)

and

F_{2n+2} = ∑_{j=−∞}^{∞}(\binom{2n + 1}{n − 5j} − \binom{2n + 1}{n − 5j − 2}),  (5)

F_{2n+1} = ∑_{j=−∞}^{∞}(\binom{2n}{n − 5j} − \binom{2n}{n − 5j − 2}),  (6)

respectively. These identities have been reobtained by Andrews [2] in the context of identities of the Rogers-Ramanujan type. The author proved identities (3)–(6) and some generalizations by a completely elementary method in [3] and a Riordan array method in [4]. Cigler proved these identities by several different methods [5], [6], [7]. Cigler obtained many identities of the same type about sums of binomial coefficients, in terms not of Fibonacci numbers, but of solutions to more general recursions.

The aim of this article is to study some further identities of the same type. The idea is to justify that some recurrences that can easily be conjectured using software like Maple indeed hold true. Our method applies equally well when, instead of 2n in identities (3)–(6), we have an arbitrary multiple of n.

2 Preliminaries

Throughout this paper by recurrence we mean a homogeneous linear recurrence with integer coefficients

x_{n} = a_{1}x_{n−1} + a_{2}x_{n−2} + ⋯ + a_{k}x_{n−k}  (7)

and we say that

1 − a_{1}x − a_{2}x^{2} − ⋯ − a_{k}x^{k}  (8)

is the polynomial associated with recurrence (7). Note that (8) is the reciprocal of the characteristic polynomial of (7).

In our first result we show that if a sequence (x_{n}) satisfies recurrence R_{1} and if, for a sufficiently large N, (x_{n}) satisfies another recurrence R_{2} for all n ≤ N, then (x_{n}) satisfies R_{2} for every n. The idea is very simple but it is the basis of our method. To prove that a sequence (x_{n}) satisfies a recurrence it is enough to verify it for sufficiently many terms, provided we know that (x_{n}) satisfies another recurrence.

Proposition 1. Suppose the sequence (x_{n})_{n≥0} satisfies

x_{n} = A_{1}x_{n−1} + A_{2}x_{n−2} + ⋯ + A_{r}x_{n−r},  ∀ n ≥ r,  (9)

and that for some N ≥ r + s − 1 we have

x_{n} = a_{1}x_{n−1} + a_{2}x_{n−2} + ⋯ + a_{s}x_{n−s},  ∀ n with s ≤ n ≤ N.  (10)

Then (10) holds for every n ≥ s.

Proof. By induction, it suffices to show that (10) also holds for n = N + 1. We have

x_{N+1} = A_{1}x_{N} + ⋯ + A_{r}x_{N−r+1}
= A_{1}(a_{1}x_{N−1} + ⋯ + a_{s}x_{N−s}) + ⋯ + A_{r}(a_{1}x_{N−r} + ⋯ + a_{s}x_{N−s−r+1})
= a_{1}(A_{1}x_{N−1} + ⋯ + A_{r}x_{N−r}) + ⋯ + a_{s}(A_{1}x_{N−s} + ⋯ + A_{r}x_{N−r−s+1})
= a_{1}x_{N} + ⋯ + a_{s}x_{N−s+1}.

Therefore (10) also holds for n = N + 1.

The following result holds for any domain A, but we only need the case A = ℤ.

Proposition 2. Let f(x) ∈ ℤ[x] be a polynomial of degree r and integer coefficients and let ω = exp(2πi/k). Define

F (x) = f(ωx)f(ω^{2}x) ⋯ f(ω^{k−1}x).  (11)

Then F (x) ∈ ℤ[x] has integer coefficients and there is a polynomial T (x) ∈ ℤ[x] of degree r such that

f(x)F (x) = T (x^{k}).

Proof. Given f(x) ∈ ℤ[x] and k > 1, define F (x) by (11). It is trivial that the product f(x)F (x) involves only powers of x with exponents that are multiples of k, since

φ(x) := f(x)f(ωx) ⋯ f(ω^{k−1}x)

satisfies φ(ωx) = φ(x). We now prove that F (x) has integer coefficients.

Define a polynomial g in k − 1 variables by

g(x_{1}, x_{2}, …, x_{k−1}) = f(x_{1})f(x_{2}) ⋯ f(x_{k−1}).

Then g is a symmetric polynomial with integer coefficients. By the fundamental theorem of symmetric polynomials, there is a polynomial h in k − 1 variables and integer coefficients such that

g(x_{1}, …, x_{k−1}) = h(s_{1}, s_{2}, …, s_{k−1}),

where

s_{1} = s_{1}(x_{1}, …, x_{k−1}) = x_{1} + ⋯ + x_{k−1}
s_{2} = s_{2}(x_{1}, …, x_{k−1}) = x_{1}x_{2} + ⋯ + x_{k−2}x_{k−1}
⋮
s_{k−1} = s_{k−1}(x_{1}, …, x_{k−1}) = x_{1} ⋯ x_{k−1}

are the elementary symmetric polynomials. It follows that F (x) satisfies

\begin{aligned}F (x) & = g(ωx, ω^{2}x, …, ω^{k−1}x) \\ & = h(s_{1}(ωx, …, ω^{k−1}x), …, s_{k−1}(ωx, …, ω^{k−1}x)). \end{aligned}

We need to investigate the polynomials s_{j}(ωx, …, ω^{k−1}x). Since

(1 + x_{1})(1 + x_{2}) ⋯ (1 + x_{k−1}) = 1 + s_{1} + s_{2} + ⋯ + s_{k−1},

making the substitution x_{j} = −ω^{j}x we have

(1 − ωx)(1 − ω^{2}x) ⋯ (1 − ω^{k−1}x) = 1 − s̃_{1} + s̃_{2} − ⋯ + (−1)^{k−1}s̃_{k−1},  (12)

where

s̃_{j} = s_{j}(ωx, ω^{2}x, …, ω^{k−1}x) = c_{j}x^{j}  (13)

for some complex number c_{j}. The left hand side of (12) is a monic polynomial of degree k − 1, whose zeros are ω, ω^{2}, …, ω^{k−1}, since, for each j ∈ {1, …, k − 1}, x = ω^{k−j} is a zero of 1 − ω^{j}x. Therefore,

(1 − ωx)(1 − ω^{2}x) ⋯ (1 − ω^{k−1}x) = \frac{x^{k} − 1}{x − 1} = 1 + x + x^{2} + ⋯ + x^{k−1}.  (14)

Comparing (12), (13), and (14) we have that, for all j, the coefficient c_{j} in (13) is c_{j} = (−1)^{j}, i.e.,

s̃_{j} = (−1)^{j}x^{j}.

Hence,

F (x) = g(−x, x^{2}, −x^{3}, …, (−1)^{k−1}).

But g is a polynomial with integer coefficients. Therefore, F (x) ∈ ℤ[x].

Corollary 3. Let k > 1 be an integer. Every polynomial f(x) of degree r and integer coefficients has a multiple f(x)F (x) with integer coefficients and involving only powers of x with an exponent multiple of k, and f(x)F (x) has degree kr.

3 Case of Pascal’s triangle

Definition 4. A Riordan array is a pair (g(x), h(x)) of formal power series, where

g(x) = ∑_{n=0}^{∞} g_{n}x^{n}, with g_{0} ≠ 0,

and

h(x) = ∑_{n=1}^{∞} h_{n}x^{n}.

This Riordan array is associated with an infinite matrix (d(n, k))_{n,k≥0} given by

d(n, k) = [x^{n}]g(x)(h(x))^{k},

where [x^{n}] denotes the operator [x^{n}] ∑ c_{j}x^{j} = c_{n}.

The main example of a Riordan array is Pascal’s triangle, for g(x) = \frac{1}{1−x}, and h(x) = \frac{x}{1−x}. In this case

d(n, k) = \binom{n}{k}.

If all the coefficients g_{n} and h_{n} are integers and g_{0} = 1, then d(n, k) ∈ ℤ, ∀ (n, k).

Proposition 5. Let (g(x), h(x)) be a Riordan array. Fix k > 1 and for p ∈ {0, 1, 2, …, k−1} define the sequence

a_{p}(n) := ∑_{j=0}^{∞} d(n, kj + p).

Then

a_{p}(n) = ∑_{j=0}^{∞} d(n, kj + p) = [x^{n}]\frac{g(x)(h(x))^{p}}{1 − (h(x))^{k}} .

Proof.

a_{p}(n) = ∑_{j=0}^{∞} d(n, kj + p) = [x^{n}] ∑_{j=0}^{∞} g(x)(h(x))^{kj+p} = [x^{n}]\frac{g(x)(h(x))^{p}}{1 − (h(x))^{k}} .

Our main interest is the case in which the Riordan array is defined by two rational functions g and h, since we are interested in linear recurrences with constant coefficients. We examine some examples to explain our method.

Example 6. To explain our method, we consider the particular case of Pascal’s triangle and k = 6. For 0 ≤ p ≤ 5, using Proposition 5 we have

a_{p}(n) = ∑_{j=0}^{∞} \binom{n}{6j + p} = [x^{n}]\frac{x^{p}(1 − x)^{6−p−1}}{(1 − x)^{6} − x^{6}} .

This sequence satisfies the recurrence a_{p}(n) = 6a_{p}(n − 1) − 15a_{p}(n − 2) + 20a_{p}(n − 3) − 15a_{p}(n − 4) + 6a_{p}(n − 5), ∀ n ≥ 6, associated with the polynomial

R(x) = (1 − x)^{6} − x^{6} = 1 − 6x + 15x^{2} − 20x^{3} + 15x^{4} − 6x^{5}.

Using Proposition 2 and multiplying

R(x)R(−x) = 1 − 6x^{2} + 15x^{4} − 22x^{6} − 15x^{8} − 36x^{10},

we obtain a multiple of R(x) containing only even exponents. It follows that for every p with 0 ≤ p ≤ 5, the sequence

b(n, p) := a_{p}(2n) = ∑_{j∈ℤ}^{∞} \binom{2n}{6j + p}

satisfies the recurrence b(n, p) = 6b(n − 1, p) − 15b(n − 2, p) + 22b(n − 3, p) + 15b(n − 4, p) + 36b(n − 5, p), ∀ n ≥ 6, associated with the polynomial

S(x) := 1 − 6x + 15x^{2} − 22x^{3} − 15x^{4} − 36x^{5} = (1 − 4x)(1 + x + x^{2})(1 − 3x + 9x^{2}). Consider the primitive 6^{th} root of unity

ω = exp (\frac{iπ}{3} ) = \frac{1}{2} + i\frac{\sqrt{3}}{2}.

To obtain a polynomial multiple of S(x) containing only exponents that are multiples of 6, we use Proposition 2 and, with the help of software, we multiply and obtain

S(x)S(ωx)S(ω^{2}x) ⋯ S(ω^{5}x) = T (x^{6}),

where

T (x) = 1 − 5556x + 6514518x^{2} − 2189794708x^{3} + 4360068081x^{4} − 2176782336x^{5}.

Therefore, ∀ p ∈ {0, 1, 2, 3, 4, 5},

\begin{aligned}b(n, p) & = 5556 b(n − 6, p) − 6514518 b(n − 12, p) + 2189794708 b(n − 18, p) \\ & − 4360068081 b(n − 24, p) + 2176782336 b(n − 30, p),  ∀ n ≥ 31. \end{aligned}  (15)

Note that in practice we do not need to calculate the polynomial T (x), we only use the existence of a recurrence like (15) associated with a polynomial involving only exponents that are multiples of 6.

Let ℕ_{0} denote the set of nonnegative integers, and let p : ℕ_{0} → {0, 1, 2, 3, 4, 5} be any function satisfying p(n + 6) = p(n), ∀ n ∈ ℕ_{0}. Define a sequence x(n) by

x(n) := b(n, p(n)).

Then, by (15),

\begin{aligned}x(n) & = 5556x(n − 6) − 6514518x(n − 12) + 2189794708x(n − 18) \\ & − 4360068081x(n − 24) + 2176782336x(n − 30),  ∀ n ≥ 31, \end{aligned}  (16)

since

x(n) = b(n, p(n))
x(n − 6) = b(n − 6, p(n − 6)) = b(n − 6, p(n))
x(n − 12) = b(n − 12, p(n))
⋮
x(n − 30) = b(n − 30, p(n)).

As an example of the situation considered above, let P (n) be a polynomial with integer coefficients. Define

c(n) := ∑_{j∈ℤ} \binom{2n}{P (n) + 6j}.

Define p : ℕ_{0} → {0, 1, 2, 3, 4, 5} by p(n) = P (n) mod 6, where m mod 6 is the unique element in {0, 1, 2, 3, 4, 5} congruent to m modulo 6. Then p(n + 6) = p(n) for every n and

c(n) = b(n, p(n)) = ∑_{j∈ℤ} \binom{2n}{P (n) + 6j} = ∑_{j=0}^{∞} \binom{2n}{p(n) + 6j}.

In particular, for P (n) = n + q, q ∈ {0, 1, 2, 3, 4, 5}, we have that

c_{q}(n) = ∑_{j∈ℤ} \binom{2n}{n + q + 6j}

satisfies

\begin{aligned}c_{q}(n) & = 5556c_{q}(n − 6) − 6514518c_{q}(n − 12) + 2189794708c_{q}(n − 18) − 4360068081c_{q}(n − 24) \\ & + 2176782336c_{q}(n − 30), ∀ n ≥ 31. \end{aligned}

Using software it is easy to find that

c_{q}(n) = 8c_{q}(n − 1) − 19c_{q}(n − 2) + 12c_{q}(n − 3), ∀ n with 4 ≤ n ≤ 33.

Note that

1 − 8x + 19x^{2} − 12x^{3} = (1 − x)(1 − 3x)(1 − 4x).

By Proposition 1,

c_{p}(n) = 8c_{p}(n − 1) − 19c_{p}(n − 2) + 12c_{p}(n − 3),  ∀ n ≥ 4.  (17)

Condition (17) implies that

∑_{n=0}^{∞} ∑_{j∈ℤ}^{∞} \binom{2n}{n + 6j + p} = \frac{u_{p}(x)}{(1 − x)(1 − 3x)(1 − 4x)},

with u_{p}(x) polynomials with integer coefficients and degree at most 3. Using software, it is easy to calculate

\begin{aligned}u_{0}(x) & = 1 − 6x + 9x^{2} − 2x^{3} \\ u_{1}(x) & = x − 4x^{2} + 2x^{3} \\ u_{2}(x) & = x^{2} − 2x^{3} \\ u_{3}(x) & = 2x^{3}. \end{aligned}

Looking for A, B, C, D such that Au_{0}(x) + Bu_{1}(x) + Cu_{2}(x) + Du_{3}(x) = (1 − 3x)(1 − 4x), we find A = D = 1 and B = C = −1. Hence,

∑_{j∈ℤ}(\binom{2n}{n + 6j} − \binom{2n}{n + 6j + 1} − \binom{2n}{n + 6j + 2} + \binom{2n}{n + 6j + 3}) = 1, ∀ n.

Looking for A, B, C, D such that Au_{0}(x) + Bu_{1}(x) + Cu_{2}(x) + Du_{3}(x) = (1 − x)(1 − 4x), we find A = B = 1 and C = D = −1. Hence,

∑_{j∈ℤ}(\binom{2n}{n + 6j} + \binom{2n}{n + 6j + 1} − \binom{2n}{n + 6j + 2} − \binom{2n}{n + 6j + 3}) = 3^{n}, ∀ n.

Example 7. Using the same method, we find that

∑_{n=0}^{∞} ∑_{j∈ℤ}^{∞} \binom{3n}{n + 6j + p} = \frac{u_{p}(x)}{(1 − 8x)(1 − x + x^{2})(1 − 9x + 27x^{2})},

with

\begin{aligned}u_{0}(x) & = 1 − 15x + 78x^{2} − 166x^{3} + 105x^{4} − 36x^{5} \\ u_{1}(x) & = 3x − 34x^{2} + 117x^{3} − 120x^{4} + 36x^{5} \\ u_{2}(x) & = x − 3x^{2} − 27x^{3} + 81x^{4} − 36x^{5} \\ u_{3}(x) & = 6x^{2} − 23x^{3} − 24x^{4} + 36x^{5} \\ u_{4}(x) & = 2x^{2} + 9x^{3} − 15x^{4} − 36x^{5} \\ u_{5}(x) & = x − 12x^{2} + 54x^{3} + 36x^{5}. \end{aligned}

Looking for A_{0}, A_{1}, …, A_{5} such that A_{0}u_{0}(x) + A_{1}u_{1}(x) + A_{2}u_{2}(x) + A_{3}u_{3}(x) + A_{4}u_{4}(x) + A_{5}u_{5}(x) = (1 − 8x)(1 − 9x + 27x^{2}), we find A_{0} = A_{3} = 1, A_{1} = A_{4} = 0, and A_{2} = A_{5} = −1. It follows that

∑_{n=0}^{∞} ∑_{j∈ℤ}(\binom{3n}{n + 6j} − \binom{3n}{n + 6j + 2} + \binom{3n}{n + 6j + 3} − \binom{3n}{n + 6j + 5}) = \frac{1}{1 − x + x^{2}} .

Hence,

∑_{j∈ℤ}(\binom{3n}{n + 6j} − \binom{3n}{n + 6j + 2} + \binom{3n}{n + 6j + 3} − \binom{3n}{n + 6j + 5}) = cos \frac{nπ}{3} + \frac{1}{\sqrt{3}} sin \frac{nπ}{3} ,

i.e.,

∑_{j∈ℤ}(\binom{3n}{n + 3j} − \binom{3n}{n + 3j + 2}) = cos \frac{nπ}{3} + \frac{1}{\sqrt{3}} sin \frac{nπ}{3} , ∀ n.

Looking for A, B, C, D such that Au_{0}(x) + Bu_{1}(x) + Cu_{2}(x) + Du_{3}(x) = (1 − x)(1 − 4x), we find A = B = 1 and C = D = −1. Hence,

∑_{j∈ℤ}(\binom{3n}{n + 6j} + \binom{3n}{n + 6j + 1} − \binom{3n}{n + 6j + 2} − \binom{3n}{n + 6j + 3}) = 3^{n}, ∀ n.

Likewise, looking for constants A, B, …, F such that Au_{0}(x) + Bu_{1}(x) + Cu_{2}(x) + Du_{3}(x) + Eu_{4}(x) + F u_{5}(x) = (1 − 8x)(1 − x + x^{2}), we find

∑_{n=0}^{∞} x^{n} ∑_{j∈ℤ}(\binom{3n}{n + 6j} + 2\binom{3n}{n + 6j + 1} + \binom{3n}{n + 6j + 2} − \binom{3n}{n + 6j + 3}

− 2\binom{3n}{n + 6j + 4} − \binom{3n}{n + 6j + 5}) = \frac{1}{1 − 9x + 27x^{2}} ,

i.e.,

∑_{j∈ℤ}(\binom{3n}{n + 6j} + 2\binom{3n}{n + 6j + 1} + \binom{3n}{n + 6j + 2} − \binom{3n}{n + 6j + 3}

− 2\binom{3n}{n + 6j + 4} − \binom{3n}{n + 6j + 5}) = (3\sqrt{3})^{n} (cos \frac{nπ}{6} + \sqrt{3} sin \frac{nπ}{6} ) .

We now summarize the method explained in the examples above. Proposition 8. Given α, k > 1, γ ≥ 1, and 0 ≤ p < k integers, suppose the sequence

c(n) := ∑_{j∈ℤ} \binom{αn}{γn + p + kj}

satisfies

c(n) = δ_{1}c(n − 1) + δ_{2}c(n − 2) + ⋯ + δ_{s}c(n − s)  (18)

for every n, with s ≤ n ≤ k^{2} + s − 1, where δ_{i} ∈ ℤ are independent of p. Then c(n) satisfies (18) for every n ≥ s. Proof. We have that

a_{p}(n) := ∑_{j∈ℤ} \binom{n}{p + kn}

satisfies, for every n ≥ k the recurrence of order at most k associated with the polynomial R(x) = (1 − x)^{k} − x^{k}. Let

τ = exp (\frac{2πi}{α}) .

Since

V (x) = R(x)R(τx) ⋯ R(τ^{α−1}x)

is a multiple of R(x), a_{p}(n) satisfies the recurrence associated with V (x). By Proposition 2, V (x) = S(x^{α}), with S(x) a polynomial of degree at most k. Hence

b(n, p) := a_{p}(αn) = ∑_{j∈ℤ} \binom{αn}{p + kj}

satisfies the recurrence associated with S(x), for every n ≥ k. Let

ω = exp (\frac{2πi}{k}) .

Since

S(x)S(ωx) ⋯ S(ω^{k−1}x)

has degree at most k^{2} and involves only powers of x with exponents that are multiples of k, we have that

c(n) = ∑_{j∈ℤ} \binom{αn}{γn + p + kj}

satisfies a recurrence of order at most k^{2}. Therefore, by Proposition 1, c(n) satisfies recurrence (18) for every n ≥ k^{2} + s − 1.

Theorem 9. Given α, k, γ > 1, β ≥ 0, and 0 ≤ p < k integers, suppose the sequence

c(n) := ∑_{j∈ℤ} \binom{αn + β}{γn + p + kj}

satisfies

c(n) = δ_{1}c(n − 1) + δ_{2}c(n − 2) + ⋯ + δ_{s}c(n − s)  (19)

for every n, with s ≤ n ≤ k^{2} + s − 1, where δ_{i} ∈ ℤ are independent of p. Then c(n) satisfies (18) for every n ≥ s.

Proof. Consider

c(n, p, β) = ∑_{j∈ℤ} \binom{αn + β}{γn + p + kj}.

The proof is by induction and Proposition 8 is the base case. Suppose that, for some β ≥ 0, c(n, p, β) satisfies (19) for every n and p with s ≤ n ⩽ k^{2} + s − 1 and 0 ≤ p < k. Since

c(n, p, β + 1) = \begin{cases}c(n, p, β) + c(n, p − 1, β), & if p > 0; \\ c(n, 0, β) + c(n, k − 1, β), & if p = 0. \end{cases}

(19) also holds for β + 1.

Example 10. As a further example, by the same method and using Theorem 9 we can show that, for all p ∈ {0, 1, …, 7},

b(n) := ∑_{j∈ℤ} \binom{7n + 2}{3n + 8j + p}

satisfies the recurrence

\begin{aligned}b(n) & = 280b(n − 1) − 27184b(n − 2) + 1094016b(n − 3) − 14123136b(n − 4) \\ & + 90277888b(n − 5) − 10764288b(n − 6) + 2097152b(n − 7), \end{aligned}

which is associated with the polynomial

\begin{aligned}1 − 280x & + 27184x^{2} − 1094016x^{3} + 14123136x^{4} − 90277888x^{5} + 10764288x^{6} − 2097152x^{7} \\ & = (1 − 128x)(1 − 16x + 128x^{2})(1 − 136x + 5424x^{2} − 640x^{3} + 128x^{4}). \end{aligned}

We have

\begin{matrix}∑_{n=0}^{∞} x^{n} ∑_{j∈ℤ} & \binom{7n + 2}{3n + 8j + p} \\ = \frac{v_{p}(x)}{(1 − 128x)(1 − 16x + 128x^{2})(1 − 136x + 5424x^{2} − 640x^{3} + 128x^{4})}, \end{matrix}

where

\begin{aligned}v_{0}(x) & = 1 − 196x + 11792x^{2} − 168240x^{3} + 2658624x^{4} + 8569344x^{5} + 860160x^{6} \\ v_{1}(x) & = 2 − 434x + 30544x^{2} − 792560x^{3} + 6198656x^{4} − 13590016x^{5} + 860160x^{6} \\ v_{2}(x) & = 1 − 154x + 4776x^{2} + 89712x^{3} − 3498176x^{4} + 9704960x^{5} − 1892352x^{6} \\ v_{3}(x) & = 84x − 12064x^{2} + 438480x^{3} − 2845440x^{4} + 50688x^{5} + 1777664x^{6} \\ v_{4}(x) & = 36x − 1952x^{2} − 119248x^{3} + 3605312x^{4} − 9309696x^{5} − 712704x^{6} \\ v_{5}(x) & = 10x + 2128x^{2} − 189840x^{3} + 147328x^{4} + 12833280x^{5} − 712704x^{6} \\ v_{6}(x) & = 10x + 840x^{2} − 11888x^{3} − 1356480x^{4} − 9132544x^{5} + 1777664x^{6} \\ v_{7}(x) & = 36x − 5152x^{2} + 334256x^{3} − 2091264x^{4} + 538112x^{5} − 1892352x^{6}. \end{aligned}

We also have

\begin{aligned}(1 − 128x)(1 − 136x + 5424x^{2} − 640x^{3} + 128x^{4}) & = 1 − 264x + 22832x^{2} − 694912x^{3} \\ & + 82048x^{4} − 16384x^{5}. \end{aligned}

Looking for constants A_{0}, A_{1}, …, A_{7} such that

A_{0}v_{0}(x) + A_{1}v_{1}(x) + ⋯ + A_{7}v_{7}(x) = (1 − 128x)(1 − 136x + 5424x^{2} − 640x^{3} + 128x^{4}), we find

A_{0} = A_{4} = −A_{1} = −A_{5} = −1 − A_{3}, A_{7} = −A_{2} = A_{3}.

Choosing A_{3} = 0, we obtain that

u(n) := ∑_{j∈ℤ}(−\binom{7n + 2}{3n + 8j} + \binom{7n + 2}{3n + 8j + 1} − \binom{7n + 2}{3n + 8j + 4} + \binom{7n + 2}{3n + 8j + 5})

satisfies

∑_{n=0}^{∞} u(n)x^{n} = \frac{1}{1 − 16 + 128x^{2}} .

Choosing A_{3} = −1, we obtain another expression for u(n),

u(n) = ∑_{j∈ℤ}(\binom{7n + 2}{3n + 8j + 2} − \binom{7n + 2}{3n + 8j + 3} + \binom{7n + 2}{3n + 8j + 6} − \binom{7n + 2}{3n + 8j + 7}).

It follows that u(n) satisfies the recurrence

u(n) = 16u(n − 1) − 128u(n − 2), n ≥ 2.

Also

u(n) = (8\sqrt{2})^{n} (cos \frac{nπ}{4} + sin \frac{nπ}{4} ) .

4 Riordan arrays defined by rational functions

It is well known that the coefficients of a generating function

f(x) = ∑_{n=0}^{∞} b(n)x^{n} ∈ ℤ[[x]]

satisfy a recurrence of the form

b(n) = α_{1}b(n − 1) + ⋯ + α_{k}b(n − k),

with α_{i} ∈ ℤ, if and only if f is a rational function expressed as

f(x) = \frac{P (x)}{Q(x)}

with P (x), Q(x) ∈ ℤ[x] and Q(0) = 1. For this reason, we study Riordan arrays defined by rational functions.

Proposition 11. Let (g, h) = (d(n, k)) be a Riordan array with g and h rational functions,

g(x) = \frac{g_{1}(x)}{g_{2}(x)}  and  h(x) = \frac{x^{ν}h_{1}(x)}{h_{2}(x)},

with g_{1}, g_{2}, h_{1}, h_{2} ∈ ℤ[x], g_{2}(0) = h_{1}(0) = h_{2}(0) = 1, and ν ≥ 1. Then, for all integers k > p ≥ 0,

a_{p}(n) := ∑_{j} d(n, kj + p)

satisfies a recurrence

a_{p}(n) = α_{1}a_{p}(n − 1) + ⋯ + α_{r}a_{p}(n − r),

with α_{i} integers not depending on p.

Proof. By Proposition 5,

\begin{aligned}∑_{n=0}^{∞} a_{p}(n)x^{n} & = \frac{g(x)(h(x))^{p}}{1 − (h(x))^{k}} \\ & = \frac{g_{1}(x)x^{pν}(h_{1}(x))^{p}(h_{2}(x))^{k−p}}{g_{2}(x)((h_{2}(x))^{k} − x^{kν}(h_{1}(x))^{k})}. \end{aligned}

Hence, for all p ∈ {0, 1, …, k − 1}, (a_{p}(n))_{n} satisfies

a_{p}(n) = α_{1}a_{p}(n − 1) + ⋯ + α_{r}a_{p}(n − r),

where

g_{2}(x) ((h_{2}(x))^{k} − x^{kν}(h_{1}(x))^{k}) = 1 − α_{1}x − ⋯ − α_{r}x^{r}.

Example 12. The Riordan array of coefficients of Morgan-Voyce polynomials, which is sequence \underline{A085478} in the On-Line Encyclopedia of Integer Sequences (OEIS) [11], is

(\frac{1}{1 − x}, \frac{x}{(1 − x)^{2}} ) ,

with

d(n, k) = \binom{n + k}{n − k}.

For p ∈ {0, 1, 2}, let

a_{p}(n) := ∑_{j=0}^{∞} d(n, 3j + p).

Then

∑_{n=0}^{∞} a_{p}(n)x^{n} = \frac{g(x)(h(x))^{p}}{1 − (h(x))^{3}}

= \frac{1}{1 − x} \frac{(\frac{x}{(1−x)^{2}} )p}{1 − (\frac{x}{(1−x)^{2}} )^{3}}

= \frac{x^{p}(1 − x)^{5−2p}}{(1 − x)^{6} − x^{3}} .

Therefore, for every p ∈ {0, 1, 2}, a_{p}(n) satisfies a_{p}(n) = 6a_{p}(n−1)−15a_{p}(n−2)+21a_{p}(n−3)−15a_{p}(n−4)+6a_{p}(n−5)−a_{p}(n−6), ∀ n ≥ 0. Multiplying

((1 − x)^{6} − x^{3})((1 + x)^{6} + x^{3}) = 1 − 6x^{2} + 3x^{4} − 61x^{6} + 3x^{8} − 6x^{10} + x^{12}, we find that

b_{p}(n) := ∑_{j} d(2n, 3j + p)

satisfies

b_{p}(n) = 6b_{p}(n − 1) − 3b_{p}(n − 2) + 61b_{p}(n − 3) − 3b_{p}(n − 4) + 6b_{p}(n − 5) − b_{p}(n − 6). By the same method used in Example 6,

c(n) := ∑_{j} d(2n, n + 3j + p)

satisfies a recurrence of the form

c(n) = δ_{1}c(n − 3) + δ_{2}c(n − 6) + ⋯ + δ_{t}c(n − 3t),

for all n, with δ_{i} ∈ ℤ. Using software it is easy to find out that for every n less than or equal to a sufficiently large number the following recurrence holds,

c(n) = 12c(n − 1) − 42c(n − 2) + 43c(n − 3) + 21c(n − 4) + 3c(n − 5) − c(n − 6). (20)

Then, by the same method used in Example 6, recurrence (20) holds for every n and

∑_{n} x^{n} ∑_{j} d(2n, n + p + 3j) = \frac{u_{p}(x)}{R(x)},

with

\begin{aligned}R(x) & = 1 − 12x + 42x^{2} − 43x^{3} − 21x^{4} − 3x^{5} + x^{6} \\ & = (1 − 7x + x^{2})(1 − 5x + 6x^{2} + 4x^{3} + x^{4}) \end{aligned}

and

\begin{aligned}u_{0}(x) & = 1 − 9x + 21x^{2} − 11x^{3} − 6x^{4} \\ u_{1}(x) & = x − 4x^{2} + 12x^{3} − 2x^{4} − x^{5} \\ u_{2}(x) & = x − x^{2} − 9x^{3} + x^{4} − x^{5}. \end{aligned}

Unfortunately, since the degrees of of the polynomials u_{i}(x) are greater than the degrees of the nontrivial factors of R(x), there is little hope that a linear combination of u_{0}, u_{1}, u_{2} might be equal to one of these factors and there will be no recurrences simpler than the ones we have already found.

5 Concluding remarks

As we pointed out in the previous section, it is not to be expected that a Riordan array (g(x), h(x)) may exhibit recurrences like the ones studied in this article if g and h are not rational functions. However, we now present an example of a Riordan array in which g and h are not rational functions and still some recursions do occur. Consider the Riordan array (d(n, k)) = (g(x), h(x)), where

g(x) = \frac{1 − 2x − \sqrt{1 − 4x}}{2x^{2}}, h(x) = xg(x).

This Riordan array, known as Catalan’s triangle, is sequence \underline{A039598} in the On-Line Encyclopedia of Integer Sequences (OEIS) [11] and the first few rows are

1

2 1
5 4 1
14 14 6 1
42 48 27 8 1
132 165 110 44 10 1

We have

d(n, k) = \frac{k + 1}{n + 1}\binom{2(n + 1)}{n − k}.

Since g and h are not rational functions, for fixed p,

∑_{j} d(n, 5j + p)

does not satisfy any homogeneous linear recurrence with constant coefficients, but this does not prevent the fact that a sequence of the type

∑_{j}(d(n, 5j + p) − d(n, 5j + q))

might satisfy one. Indeed this is the case, as the following holds.

Proposition 13. With the above notation, we have

∑_{j=0}^{∞}(d(n, 5j + 1) − d(n, 5j + 2)) = F_{2n}  (21)

and

∑_{j=0}^{∞}(d(n, 5j) − d(n, 5j + 3)) = F_{2n+1}.  (22)

Proof. We have

\begin{aligned}∑_{n=0}^{∞} x^{n} ∑_{j=0}^{∞}(d(n, 5j + 1) − d(n, 5j + 2)) & = ∑_{j=0}^{∞} g(x) ((h(x))^{5j+1} − (h(x))^{5j+2}) \\ & = \frac{g(x)h(x)(1 − h(x))}{1 − (h(x))^{5}} \\ & = \frac{1}{x} \frac{1}{(h(x))^{−2} + (h(x))^{−1} + 1 + h(x) + (h(x))^{2}} . \end{aligned} ; (23)

But

h(x) + (h(x))^{−1} = \frac{1 − 2x}{x}.  (24)

Squaring both sides we obtain

(h(x))^{2} + 2 + (h(x))^{−2} = \frac{1 − 4x + 4x^{2}}{x^{2}} ,

hence,

(h(x))^{2} + (h(x))^{−2} = \frac{1 − 4x + 2x^{2}}{x^{2}} .  (25)

Replacing (24) and (25) in (23) yields

∑_{n=0}^{∞} x^{n} ∑_{j=0}^{∞}(d(n, 5j + 1) − d(n, 5j + 2)) = \frac{x}{1 − 3x + x^{2}} ,

proving (21). Identity (22) follows by a similar argument.

Conjecture 14. Let

a(n) := ∑_{j∈ℤ}(d(2n, n + 5j + 4) − d(2n, n + 5j + 3)).

We have a(0) = 0, but all the other terms satisfy

\begin{aligned}a(5n) & = F_{20n+1} \\ a(5n + 1) & = F_{20n+5} \\ a(5n + 2) & = −F_{20n+7} \\ a(5n + 3) & = − (F_{20n+13} + F_{20n+10}) \\ a(5n + 4) & = −F_{20n+15}. \end{aligned}

Furthermore

∑_{n=0}^{∞} a(n)x^{n} = −1 + \frac{1 + x + 13x^{2} + 5x^{3}}{1 − 4x + 46x^{2} + 11x^{3} + x^{4}} .

Conjecture 15.

b(n) = ∑_{j=0}^{∞}(d(n, 4j) − d(n, 4j + 2)) = 2^{n}.

References

[1] G. E. Andrews, Some formulae for the Fibonacci sequence with generalizations, Fibonacci Quart. 7 (1969), 113–130.

[2] G. E. Andrews, A polynomial identity which implies the Rogers-Ramanujan identities, Scripta Math. 28 (1970), 297–305.

[3] E. H. M. Brietzke, Generalization of an identity of Andrews, Fibonacci Quart. 44 (2006), 166–171.

[4] E. H. M. Brietzke, An identity of Andrews and a new combinatorial method for the Riordan array proof of combinatorial identities, Discrete Math. 308 (2008), 4246–4262.

[5] J. Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, preprint, 2022. Available at https://arxiv.org/

abs/2212.02118.

[6] J. Cigler, Recurrences for some sequences of binomial sums II: A simpler approach,

preprint, 2013. Available at https://arxiv.org/abs/1302.4239.

[7] J. Cigler, Recurrences for some sequences of binomial sums, Sitzungsber. ÖAW 210 (2001), 61–83.

[8] H. Gupta, The Andrews formula for Fibonacci numbers, Fibonacci Quart. 16 (1978), 552–555.

[9] M. D. Hirschhorn, The Andrews formula for Fibonacci numbers, Fibonacci Quart. 19 (1981), 1–2.

[10] M. D. Hirschhorn, Solution to problem 1621, Math. Mag. 75 (2002), 149–250.

[11] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

    at https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A10, Secondary 05-08, 05A19, 11B37. Keywords: sequence of sums of binomial coefficients, Riordan array, Riordan array of coefficients of Morgan-Voyce polynomials, Catalan’s triangle.

(Concerned with sequences \underline{A039598} and \underline{A085478}.)

Received October 6 2023; revised versions received October 10 2023; February 28 2024. Published in Journal of Integer Sequences, February 29 2024.

Return to Journal of Integer Sequences home page.