INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A12

LINEAR RECURRENT SEQUENCES AND POWERS OF A SQUARE MATRIX

Hacène Belbachir^{1}

USTHB, Department of Mathematics, P.O.Box 32 El Alia, 16111, Bab Ezzouar, Algiers, Algeria

              hbelbachir@usthb.dz and hacenebelbachir@gmail.com

Farid Bencherif^{2}

USTHB, Department of Mathematics, P.O.Box 32 El Alia, 16111, Bab Ezzouar, Algiers, Algeria

                 fbencherif@usthb.dz and fbencherif@yahoo.fr

Received: 8/10/05, Revised: 3/20/06, Accepted: 4/4/06, Published: 4/24/06

Abstract

In this paper, we establish a formula expressing explicitly the general term of a linear recurrent sequence, allowing us to generalize the original result of J. McLaughlin [7] concerning powers of a matrix of size 2, to the case of a square matrix of size m ≥ 2. Identities concerning Fibonacci and Stirling numbers and various combinatorial relations are derived.

1. Introduction

The main theorem of J. McLaughlin [7] states the following:

Theorem 1. Let A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) be a square matrix of order two, let T = a + d be its trace,

and let D = ad − bc be its determinant. Let

y_{n} = ∑_{i=0}^{⌊n/2⌋} ( \begin{matrix}n − i \\ i \end{matrix} ) T^{n−2i} (−D)^{i} .  (1)

Then, for n ≥ 1,

A^{n} = ( \begin{matrix}y_{n} − dy_{n−1} & by_{n−1} \\ cy_{n−1} & y_{n} − ay_{n−1} \end{matrix} ) .  (2)

1Partially supported by the laboratory LAID3.

2Partially supported by the laboratory LATN.

We remark that in this theorem, (y_{n})_{n≥−1} is a linear recurrent sequence that satisfies

\{ \begin{matrix}y_{−1} = 0, \\ y_{0} = 1, \\ y_{n} = T y_{n−1} − Dy_{n−2} for all integer n ≥ 1. \end{matrix}  (3)

By setting A_{0} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) and A_{1} = ( \begin{matrix}−d & b \\ c & −a \end{matrix} ) , relation (2) of Theorem 1 may be written as follows:

A^{n} = y_{n}A_{0} + y_{n−1}A_{1} for all integers n ≥ 0,  (4)

with A_{0} = I_{2} and A_{1} = A − T I_{2} (where I_{2} is the unit matrix).

In Section 3, we extend this result (relation (4)) to any matrix A ∈ M_{m} (A) of order m ≥ 2, A being a unitary commutative ring.

We prove the following result: Let A ∈ M_{m} (A) and let P (X) = X^{m} − a_{1}X^{m−1} − ⋯ − a_{m−1}X − a_{m} be the characteristic polynomial of A. Let A_{0}, A_{1}, …, A_{m−1} be matrices of M_{m} (A) defined by

A_{k} = − ∑_{i=0}^{k} a_{i}A^{k−i}, for 0 ≤ k ≤ m − 1, with a_{0} = −1,

and let (y_{n})_{n>−m} be the sequence of elements of A satisfying

y_{n} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{m}^{k_{m}}, for n > −m.

Then, for all integers n ≥ 0, A^{n} = y_{n}A_{0} + y_{n−1}A_{1} + ⋯ + y_{n−m+1}A_{m−1}.

The proof of this result is based on Theorem 2 given in Section 2.

In this section, we generalize Theorem 2, which permits us to express the general term u_{n} of a recurrent linear sequence satisfying the relation

u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ + a_{m}u_{n−m} for all n ≥ 1,

in terms of the coefficients a_{1}, a_{2}, …, a_{m} and u_{0}, u_{−1}, u_{−2}, …, u_{−(m−1)}. Applications to Fibonacci, generalized Fibonacci and “multibonacci” sequences are also given.

Finally, in Section 4, further combinatorial identities are derived, including identities concerning the Stirling numbers of the first and second kind.

As an illustration, we give a nice duality between the two following relations (Corollaries 5 and 7):

∑_{k_{1}+2k_{2}+···+mk_{m}=n}( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} ) (−1)^{n−(∑_{i=1}^{m} k_{i})} ( \begin{matrix}m \\ m − 1 \end{matrix} )^{k_{1}}… ( \begin{matrix}m \\ 0 \end{matrix} )^{k_{m}}= ( \begin{matrix}n + m − 1 \\ m − 1 \end{matrix} ) ,

∑_{k_{1}+2k_{2}+···+mk_{m}=n}( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} ) (−1)^{n−(∑_{i=1}^{m} k_{i})} [ \begin{matrix}m \\ m − 1 \end{matrix} ]^{k_{1}}… [ \begin{matrix}m \\ 0 \end{matrix} ]^{k_{m}}= \{ \begin{matrix}n + m − 1 \\ m − 1 \end{matrix} \} ,

where ( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} ) is the multinomial coefficient (Section 2), and [ \begin{matrix}n \\ k \end{matrix} ] and \{ \begin{matrix}n \\ k \end{matrix} \}

are, respectively, the Stirling numbers of the first and second kind as defined in [5].

2. Explicit Expression of the General Term of a Recurrent Linear Sequence

In this section, we let m ≥ 2 be an integer, A a unitary commutative ring, a_{1}, a_{2}, …, a_{m}, α_{0}, α_{1}, …, α_{m−1} elements of A, and (u_{n})_{n>−m} a sequence of elements of A defined by

\{ \begin{matrix}u_{−j} = α_{j} for 0 ≤ j ≤ m − 1, \\ u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ + a_{m}u_{n−m} for n ≥ 1. \end{matrix}  (5)

The aim of this section is to give an explicit expression of u_{n} in terms of n, a_{1}, a_{2}, …, a_{m}, α_{0}, α_{1}, …, α_{m−1} (Theorem 3).

Let us define the sequence (y_{n})_{n∈ℤ} of elements of A, with the convention that an empty sum is zero, by

y_{n} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{m}^{k_{m}}, for n ∈ ℤ,  (6)

the summation being taken over all m-tuples (k_{1}, k_{2}, …, k_{m}) of integers k_{j} ≥ 0 satisfying k_{1} + 2k_{2} + ⋯ + mk_{m} = n. With the previous convention, we have y_{n} = 0 for n < 0. The multinomial coefficient that appears in the summation is defined for integers k_{1}, k_{2}, …, k_{m} ≥ 0, by

( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) = \frac{(k_{1} + k_{2} + ⋯ + k_{m})!}{k_{1}!k_{2}! ⋯ k_{m}!},

and can always be written as a product of binomial coefficients

( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) = ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1} + k_{2} + ⋯ + k_{m−1} \end{matrix} ) ⋯ ( \begin{matrix}k_{1} + k_{2} + k_{3} \\ k_{1} + k_{2} \end{matrix} ) ( \begin{matrix}k_{1} + k_{2} \\ k_{1} \end{matrix} ) .

Let us adopt the following convention. For k_{1} + k_{2} + ⋯ + k_{m} ≥ 1, we put

( \begin{matrix}k_{1} + k_{2} + ⋯ + (k_{j} − 1) + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{j} − 1, …, k_{m} \end{matrix} ) = 0 when k_{j} = 0,

for any j ∈ {1, 2, …, m} . We can now state the following lemma [p. 80 (Vol. 1), 4].

Lemma 1. Let k_{j} ≥ 0 be integers for j ∈ {1, 2, …, m} , such that k_{1} + ⋯ + k_{m} ≥ 1. Then

( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) = ∑_{j=1}^{m} ( \begin{matrix}k_{1} + ⋯ + (k_{j} − 1) + ⋯ + k_{m} \\ k_{1}, …, k_{j} − 1, …, k_{m} \end{matrix} ) .

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A12 4

This lemma permits us to easily prove the following result. Lemma 2. The sequence (y_{n})_{n∈ℤ} , defined by relation (6) , satisfies the recurrence relation

y_{n} = a_{1}y_{n−1} + a_{2}y_{n−2} + ⋯ + a_{m}y_{n−m} for n ≥ 1

with y_{0} = 1 and y_{n} = 0 for n < 0. Proof. First notice that, for n ≥ 1, for all j ∈ {1, 2, …, m} we have

a_{j}y_{n−j} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + ⋯ + (k_{j} − 1) + ⋯ + k_{m} \\ k_{1}, …, k_{j} − 1, …, k_{m} \end{matrix} ) a_{1}^{k_{1}} … a_{j}^{k_{j}} … a_{m}^{k_{m}}.

Applying Lemma 1, we obtain ∑_{j=1}^{m} a_{j}y_{n−j} = y_{n}. The relations y_{0} = 1 and y_{n} = 0 for n < 0 follow immediately. □

We can now state the following result. Theorem 2. Let (u_{n})_{n>−m} the sequence of elements of A defined by

\{ \begin{matrix}u_{−j} = 0 for 1 ≤ j ≤ m − 1, \\ u_{0} = 1, \\ u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ + a_{m}u_{n−m} for n ≥ 1. \end{matrix}

Then for all integers n > −m,

u_{n} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{m}^{k_{m}}.

Corollary 1. Let q ≥ 1 be an integer, a, b ∈ A, and let (v_{n})_{n≥−q} be the sequence of elements of A defined by

\{ \begin{matrix}v_{−j} = 0 for 1 ≤ j ≤ q, \\ v_{0} = 1, \\ v_{n+1} = av_{n} + bv_{n−q} for n ≥ 0. \end{matrix}  (7)

Then, for all n ≥ −q,

v_{n} = \begin{matrix}⌊ & \frac{n}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} ( \begin{matrix}n − kq \\ k \end{matrix} ) a^{n−k(q+1)}b^{k},  (8)

and, for all n ≥ 0,

v_{n+1} + bv_{n−q} = 2v_{n+1} − av_{n} = \begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} \frac{n + 1 − k (q − 1)}{n + 1 − kq} ( \begin{matrix}n + 1 − kq \\ k \end{matrix} ) a^{n+1−k(q+1)}b^{k}. (9)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A12 5

Proof. We deduce relation (8) directly from Theorem 2, with m = q + 1, a_{1} = a, a_{m} = b and a_{k} = 0 for 1 < k < m. From (8) , we deduce (9) as follows:

v_{n+1} + bv_{n−q} = \begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix}( \begin{matrix}n + 1 − kq \\ k \end{matrix} ) a^{n+1−k(q+1)}b^{k} +\begin{matrix}⌊ & \frac{n−q}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} ( \begin{matrix}n − (k + 1) q \\ k \end{matrix} ) a^{n−q−(q+1)k}b^{k+1}
= \begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix}( \begin{matrix}n + 1 − kq \\ k \end{matrix} ) a^{n+1−k(q+1)}b^{k} +\begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=1 \end{matrix} ( \begin{matrix}n − kq \\ k − 1 \end{matrix} ) a^{n+1−k(q+1)}b^{k}
= \begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix}( \begin{matrix}n + 1 − kq \\ k \end{matrix} ) a^{n+1−k(q+1)}b^{k} +\begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix}\frac{k}{n+1−kq} ( \begin{matrix}n + 1 − kq \\ k \end{matrix} ) a^{n+1−k(q+1)}b^{k}
= \begin{matrix}⌊ & \frac{n+1}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} \frac{n + 1 − k (q − 1)}{n + 1 − kq} ( \begin{matrix}n + 1 − kq \\ k \end{matrix} ) a^{n+1−k(q+1)}b^{k}.
□

We now give some applications of the above corollary. Application 1. Let (F_{n})_{n≥0} be the Fibonacci sequence

\{ \begin{matrix}F_{0} = 0, \\ F_{1} = 1, \\ F_{n+1} = F_{n} + F_{n−1} for n ≥ 1. \end{matrix}

Then, by setting φ_{n} = F_{n+1} for n ≥ −1, we see that (φ_{n})_{n≥−1} is also defined by

\{ \begin{matrix}φ_{−1} = 0, \\ φ_{0} = 1, \\ φ_{n} = φ_{n−1} + φ_{n−2} for n ≥ 1. \end{matrix}

The application of Corollary 1 gives us that

φ_{n} = F_{n+1} = ∑_{k=0}^{⌊n/2⌋} ( \begin{matrix}n − k \\ k \end{matrix} ) , for n ≥ −1,

the relation given in [pp. 18-20, 12], and announced in [9] . Also

F_{n} + F_{n+2} = \begin{matrix}⌊ & \frac{n+1}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \frac{n + 1}{n + 1 − k} ( \begin{matrix}n + 1 − k \\ k \end{matrix} ) , for n ≥ 0,

and we find the relations given in Problem 6.98 of [10] , which state that

F_{2n−1} + F_{2n+1} = ∑_{k=0}^{n} \frac{2n}{2n − k} ( \begin{matrix}2n − k \\ k \end{matrix} )

and

F_{2n} + F_{2n+2} = ∑_{k=0}^{n} \frac{2n + 1}{2n + 1 − k} ( \begin{matrix}2n + 1 − k \\ k \end{matrix} ) .

Application 2. For q ≥ 1, let (G_{n}^{(q)})_{n≥0} be the generalized Fibonacci sequence as cited in

[8] , and let (H_{n}^{(q)})_{n≥0} be a sequence of numbers defined as follows:

\{ \begin{matrix}G_{0}^{(q)} = G_{1}^{(q)} = ⋯ = G_{q}^{(q)} = 1, \\ G_{n+1}^{(q)} = G_{n}^{(q)} + G_{n−q}^{(q)} for n ≥ q, \end{matrix}  and \{ \begin{matrix}H_{0}^{(q)} = H_{1}^{(q)} = ⋯ = H_{q}^{(q)} = 1, \\ H_{n+1}^{(q)} = H_{n}^{(q)} − H_{n−q}^{(q)} for n ≥ q. \end{matrix}

We can extend easily the above sequences to (G_{n})_{n≥−q} and (H_{n})_{n≥−q} by

\{ \begin{matrix}G_{−j}^{(q)} = 0 for 1 ≤ j ≤ q, \\ G_{0}^{(q)} = 1, \\ G_{n+1}^{(q)} = G_{n}^{(q)} + G_{n−q}^{(q)} for n ≥ 0, \end{matrix}  and \{ \begin{matrix}H_{−j}^{(q)} = 0 for 1 ≤ j ≤ q, \\ H_{0}^{(q)} = 1, \\ H_{n+1}^{(q)} = H_{n}^{(q)} − H_{n−q}^{(q)} for n ≥ 0. \end{matrix}

The application of Corollary 1 gives us, for n ≥ −q, the relations

G_{n}^{(q)} = \begin{matrix}⌊ & \frac{n}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} ( \begin{matrix}n − kq \\ k \end{matrix} ), and H_{n}^{(q)} = \begin{matrix}⌊ & \frac{n}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} (−1)^{k} ( \begin{matrix}n − kq \\ k \end{matrix} ) .

Notice that G_{n}^{(1)} = F_{n+1} = φ_{n}, and H_{n}^{(2)} is the integer function studied by L. Bernstein [1] , who showed that the only zeros of H_{n}^{(2)} are at n = 3 and n = 12. This result was treated also by L. Carlitz [2, 3] and recently by J. McLaughlin and B. Sury [8].

The following theorem gives us an explicit formulation for u_{n} in terms of n, a_{1}, a_{2}, …, a_{m}, α_{0}, α_{1}, …, α_{m−1}, and thus generalizes Theorem 2.

Theorem 3. Let (u_{n})_{n>−m} be a sequence of elements of A defined by

\{ \begin{matrix}u_{−j} = α_{j} for 0 ≤ j ≤ m − 1, \\ u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ + a_{m}u_{n−m} for n ≥ 1. \end{matrix}  (10)

Let (λ_{j})_{0≤j≤m−1}and (y_{n})_{n>−m} be the sequences of elements of A defined by

λ_{j} = − ∑_{k=j}^{m−1} a_{k−j}α_{k}, for 0 ≤ j ≤ m − 1, with a_{0} = −1,  (11)

and

y_{n} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{m}^{k_{m}}, for n > −m.

Then for all integer n > −m, we have u_{n} = λ_{0}y_{n} + λ_{1}y_{n+1} + ⋯ + λ_{m−1}y_{n+m−1}. Remark. Note that (11) is equivalent to

( λ_{0} ; λ_{1} ; λ_{2} ; ⋮ ; λ_{m−2} ; λ_{m−1} ) = ( \begin{matrix}1 & −a_{1} & −a_{2} & ⋯ & −a_{m−2} & −a_{m−1} \\ 0 & 1 & −a_{1} & −a_{2} & ⋯ & −a_{m−2} \\ 0 & 0 & 1 & −a_{1} & ⋯ & −a_{m−3} \\ ⋮ & ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & 0 & 1 & −a_{1} \\ 0 & 0 & 0 & ⋯ & 0 & 1 \end{matrix} ) ( α_{0} ; α_{1} ; α_{2} ; ⋮ ; α_{m−2} ; α_{m−1} ) .

or

[λ_{0}, λ_{1}, …, λ_{m−1}]^{t} = C [α_{0}, α_{1}, …, α_{m−1}]^{t} ,  (12)

where

C = (c_{ij})_{1≤i,j≤m} , with c_{ij} = \{ \begin{matrix}0 if i > j, \\ 1 if i = j, \\ −a_{j−i} if i < j. \end{matrix}

We deduce also from relations (10) and (12) the matrix equality

( u_{n} ; u_{n+1} ; ⋮ ; u_{n+m−2} ; u_{n+m−1} ) = ( \begin{matrix}y_{n} & y_{n+1} & ⋯ & y_{n+m−2} & y_{n+m−1} \\ y_{n+1} & y_{n+2} & ⋯ & y_{n+m−1} & y_{n+m} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ y_{n+m−2} & y_{n+m−1} & ⋯ & y_{n+2m−4} & y_{n+2m−3} \\ y_{n+m−1} & y_{n+m} & ⋯ & y_{n+2m−3} & y_{n+2m−2} \end{matrix} ) ×

× ( \begin{matrix}1 & −a_{1} & −a_{2} & ⋯ & −a_{m−1} \\ 0 & 1 & −a_{1} & ... & ⋮ \\ ⋮ & ... & ... & ... & −a_{2} \\ 0 & & 0 & 1 & −a_{1} \\ 0 & 0 & ⋯ & 0 & 1 \end{matrix} ) ( α_{0} ; α_{1} ; ⋮ ; α_{m−2} ; α_{m−1} )

Proof. Let S be the A-module of sequences (v_{n})_{n>−m} satisfying the recurrence relation

v_{n} − a_{1}v_{n−1} − a_{2}v_{n−2} − ⋯ − a_{m}v_{n−m} = 0 for all n ≥ 1.

Let us consider the family of sequences (v_{n}^{(k)})_{n>−m} , for 0 ≤ k ≤ m − 1, defined by

{ v_{n}^{(0)} = y_{n}, ; v_{n}^{(1)} = y_{n+1} − a_{1}y_{n}, ; v_{n}^{(2)} = y_{n+2} − a_{1}y_{n+1} − a_{2}y_{n}, ; ⋮ ; v_{n}^{(m−1)} = y_{n+m−1} − a_{1}y_{n+m−2} − a_{2}y_{n+m−3} − ⋯ − a_{m−1}y_{n},

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A12 8

i.e.,

v_{n}^{(k)} = y_{n+k} − (a_{1}y_{n+k−1} + a_{2}y_{n+k−2} + ⋯ + a_{k}y_{n})  (13)
= ∑_{i=0}^{k} −a_{i}y_{n+k−i},  with a_{0} = −1.

By Theorem 2, we have (y_{n})_{n>−m} ∈ S. Consequently, (y_{n+q})_{n>−m} ∈ S for q ≥ 0, and finally we deduce that

(v_{n}^{(k)})_{n>−m} ∈ S, for 0 ≤ k ≤ m − 1.  (14)

It is easy to observe that we also have, for j, k ∈ {0, 1, 2, …, m − 1} ,

v_{−j}^{(k)} = δ_{kj} = \{ \begin{matrix}1 & if k = j \\ 0 & if k ≠ j \end{matrix}  (15)

In fact, with a_{0} = −1, we can write, for j, k ∈ {0, 1, …, m − 1} ,v_{−j}^{(k)} = − ∑_{i=0}^{k} a_{i}y_{−j+k−i}.

If k < j, then −j + k − i < 0 for 1 ≤ i ≤ k and v_{−j}^{(k)} = 0 (because y_{q} = 0 for q < 0). If

k = j, then v_{−j}^{(k)} = v_{−j}^{(j)} = − ∑_{i=0}^{j} a_{i}y_{−i} = −a_{0}y_{0} = 1. If k > j, then for r = k − j < 0, we have

r ≥ 1 and

v_{−j}^{(k)} = y_{r} − (a_{1}y_{r−1} + a_{2}y_{r−2} + ⋯ + a_{k}y_{r−k}) , and by using r − k = −j ≤ 0,
= y_{r} − (a_{1}y_{r−1} + a_{2}y_{r−2} + ⋯ + a_{k}y_{r−k} + ⋯ + a_{m}y_{r−m})
= 0  because (y_{n})_{n>−m} ∈ S and r ≥ 1.

Relations (14) and (15) give easily, that for all n > −m,u_{n} = ∑_{k=0}^{m−1} α_{k}v_{n}^{(k)} and, with (13) ,

u_{n} = ∑_{k=0}^{m−1} α_{k} (∑_{i=0}^{k} −a_{i}y_{n+k−i})
= ∑_{k=0}^{m−1} ∑_{j=0}^{k} −a_{k−j}α_{k}y_{n+j}
= ∑_{j=0}^{m−1} (∑_{k=j}^{m−1} −a_{k−j}α_{k}) y_{n+j}
= ∑_{j=0}^{m−1} λ_{j}y_{n+j},

where λ_{j} is as defined in (11) . □

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A12 9

Theorem 3 allows us to find various formulae for the Fibonacci numbers. Corollary 2. For all integers n ≥ 1,

F_{n} = \frac{1}{2^{n+2}} ∑_{k=1}^{n} \frac{n + 1 − k}{k} ( \begin{matrix}k \\ n + 1 − 2k \end{matrix} ) 8^{k}.

Remark. In this summation, we may, in fact, restrict the sum to those integers i ranging between \frac{n+1}{3} and \frac{n+1}{2}, the binomial coefficient of the formula being zero for the other integers. Proof. Note that F_{n} =2F_{n−2}+F_{n−3} for n ≥ 3. Denoting by (y_{n})_{n≥−2} the sequence defined by

\{ \begin{matrix}y_{−2} = y_{−1} = 0, \\ y_{0} = 1, \\ y_{n} = 2y_{n−2} + y_{n−3} for n ≥ 1, \end{matrix}

we see that, for n ≥ 1,F_{n} = y_{n−1} + y_{n−2}. Theorem 3 allows us to state that, for n ≥ −2,

y_{n} = ∑_{2k+3l=n} ( \begin{matrix}k + l \\ l \end{matrix} ) 2^{k} = ∑_{0≤t≤n} ( \begin{matrix}t \\ n − 2t \end{matrix} ) 2^{3t−n},

and Corollary 2 follows by simple calculations. □ The following result can also be easily deduced from Theorem 3.

Corollary 3. For all integers m ≥ 1, F_{2m−1} = ∑_{k=0}^{⌊m/3⌋} \frac{m + k}{m − k} ( \begin{matrix}m − k \\ 2k \end{matrix} ) 2^{m−1−3k}.

Now, let us consider for q > 1, the “multibonacci” sequence (ϕ_{n}^{(q)})_{n>−q} defined by

\{ \begin{matrix}ϕ_{−(q−1)}^{(q)} = ⋯ = ϕ_{−2}^{(q)} = ϕ_{−1}^{(q)} = 0, \\ ϕ_{0}^{(q)} = 1, \\ ϕ_{n}^{(q)} = ϕ_{n−1}^{(q)} + ϕ_{n−2}^{(q)} + ⋯ + ϕ_{n−q}^{(q)} for n ≥ 1, \end{matrix}  (16)

where ϕ_{n}^{(2)} = φ_{n} = F_{n+1} = G_{n}^{(1)}. Theorem 3 also implies that, for all n ≥ 0,

ϕ_{n}^{(q)} = ∑_{k_{1}+2k_{2}+···+qk_{q}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{q} \\ k_{1}, k_{2}, …, k_{q} \end{matrix} ) .

Thus, for q = 3, we obtain

ϕ_{n}^{(3)} = ∑_{i+2j+3k=n} ( \begin{matrix}i + j + k \\ i, j, k \end{matrix} ) = ∑_{2i+3j≤n} ( \begin{matrix}n − i − 2j \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) .

We deduce from (16) that ϕ_{n+1}^{(q)} = 2ϕ_{n}^{(q)} − ϕ_{n−q}^{(q)}, for n ≥ 1. Let us consider (ψ_{n})_{n≥−q} , the sequence defined by ψ_{n} := ϕ_{n}^{(q)}, for n > −q and ψ_{−q} = 1, which satisfies the recurrence relationψ_{n+1} = 2ψ_{n} − ψ_{n−q}, for n ≥ 0. After applying Theorem 3, we find that, for n ≥ 0,

ψ_{n} (= ϕ_{n}^{(q)}) = λ_{0}z_{n} + λ_{1}z_{n+1} + ⋯ + λ_{q}z_{n+q}
= z_{n} − 2z_{n+q−1} + z_{n+q},

with z_{n} = \begin{matrix}⌊ & \frac{n}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} ( \begin{matrix}n − kq \\ k \end{matrix} ) 2^{n−k(q+1)} (−1)^{k} , for n ≥ −q. We know, via Theorem 3 and

Corollary 1, that the sequence (z_{n})_{n≥−q} satisfies the recurrence relation z_{n+1} − 2z_{n} + z_{n−q} = 0, for n ≥ 0. This gives, for n ≥ 0,

ϕ_{n}^{(q)} = z_{n} − z_{n−1} + (z_{n+q} − 2z_{n+q−1} + z_{n−1})
= z_{n} − z_{n−1}.

Applying relation (9) in Corollary 1, we can write, for n ≥ 1,

ϕ_{n}^{(q)} = \begin{matrix}⌊ & \frac{n}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} \frac{n − k (q − 1)}{n − kq} ( \begin{matrix}n − kq \\ k \end{matrix} ) 2^{n−1−k(q+1)} (−1)^{k} .

Thus,

∑_{k_{1}+2k_{2}+···+qk_{q}=n} ( \begin{matrix}k_{1} + ⋯ + k_{q} \\ k_{1}, …, k_{q} \end{matrix} ) = \begin{matrix}⌊ & \frac{n}{q+1} & ⌋ \\ ∑ \\ k=0 \end{matrix} \frac{n − k (q − 1)}{n − kq} ( \begin{matrix}n − kq \\ k \end{matrix} ) 2^{n−1−k(q+1)} (−1)^{k} . (17)

For q = 3, we obtain

∑_{i+2j+3k=n} ( \begin{matrix}i + j + k \\ i, j, k \end{matrix} ) = ∑_{2i+3j≤n} ( \begin{matrix}n − i − 2j \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} )

= \begin{matrix}⌊ & \frac{n}{4} & ⌋ \\ ∑ \\ k=0 \end{matrix} \frac{n − 2k}{n − 3k} (−1)^{k} ( \begin{matrix}n − 3k \\ k \end{matrix} ) 2^{n−1−4k}.

3. Powers of a Square Matrix of Order m

We start this section with the main result of this paper.

Theorem 4. Let A ∈ M_{m} (A) and let P (X) = X^{m} − a_{1}X^{m−1} − ⋯ − a_{m−1}X − a_{m} be the characteristic polynomial of A. Let A_{0}, A_{1}, …, A_{m−1} be matrices of M_{m} (A) defined by

A_{k} = − ∑_{i=0}^{k} a_{i}A^{k−i}, for 0 ≤ k ≤ m − 1, with a_{0} = −1,  (18)

and let (y_{n})_{n>−m} be the sequence of elements of A satisfying

y_{n} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{m}^{k_{m}}, for n > −m.

Then, for all integers n ≥ 0,

A^{n} = y_{n}A_{0} + y_{n−1}A_{1} + ⋯ + y_{n−m+1}A_{m−1}  (19)

Proof. Define, for 0 ≤ k ≤ m,

P_{k} (X) = − ∑_{i=0}^{k} a_{i}X^{k−i}, with a_{0} = −1.  (20)

For 0 ≤ k ≤ m − 1, we have

XP_{k} (X) = P_{k+1} (X) + a_{k+1}.  (21)

Relation (20) shows that the degree of P_{k} is k for 0 ≤ k ≤ m. It implies that (P_{0}, P_{1}, …, P_{m−1}) is a basis of the free A-module A_{m−1} [X] consisting of polynomials of A [X] of degree ≤ m−1.

For all n ≥ 0, the remainder R_{n} of the euclidean division of X^{n} by P_{m} is written as a linear combination of polynomials P_{0}, P_{1}, …, P_{m−1}. Then, for all n ≥ 0, there exists a unique family (α_{n,k})_{0≤k≤m−1} such that

R_{n} = ∑_{k=0}^{m−1} α_{n,k}P_{k}.  (22)

For 0 ≤ n ≤ m−1, we have R_{n} (X) = X^{n}, where X^{n} is a linear combination of P_{0}, …, P_{m−1}, and

\{ \begin{matrix}α_{0,0} = 1 \\ α_{n,k} = 0 for n < k ≤ m − 1. \end{matrix}  (23)

Relations (21) and (22) imply that

XR_{n} (X) = ∑_{k=0}^{m−1} α_{n,k} (P_{k+1} (X) + a_{k+1})

= ∑_{k=0}^{m−1} a_{k+1}α_{n,k} + ∑_{k=1}^{m−1} α_{n,k−1}P_{k} (X) + α_{n,m−1}P_{m} (X) .

As a consequence, the polynomial R_{n+1} (X) − XR_{n} (X) − α_{n,m−1}P_{m} (X) , of degree ≤ m − 1, is divisible by P_{m} (X), which is of degree m. This polynomial is thus the zero polynomial as well as its components in the basis (P_{0}, P_{1}, …, P_{m−1}). This provides us with the following relations:

α_{n+1,0} = ∑_{k=0}^{m−1} a_{k+1}α_{n,k}, for n ≥ 0,  (24)

α_{n+1,k} = α_{n,k−1} for 1 ≤ k ≤ m − 1.  (25)

Let us set, for all integers n ∈ ℤ,

z_{n} = \{ \begin{matrix}α_{n,0} & for n ≥ 0, \\ 0 & for n < 0. \end{matrix}  (26)

One checks easily that for all integers n ≥ 0 and for 0 ≤ k ≤ m − 1,

α_{n,k} = z_{n−k}.  (27)

Indeed, if n ≥ k this relation follows from (25) and (26) , and if 0 ≤ n < k ≤ m − 1 it follows from (23) and (26). From (25) , (26) and (27) , we find that

\{ \begin{matrix}z_{n} = 0 for n < 0, \\ z_{0} = 1, \\ z_{n} = a_{1}z_{n−1} + a_{2}z_{n−2} + ⋯ + a_{m−1}z_{n−m−1} + a_{m}z_{n−m} for n ≥ 1. \end{matrix}

Theorem 2 implies that z_{n} = y_{n}, for all n ∈ ℤ, where

y_{n} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + k_{2} + ⋯ + k_{m} \\ k_{1}, k_{2}, …, k_{m} \end{matrix} ) a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{m}^{k_{m}}.

This last fact, together with the Cayley-Hamilton Theorem, (22) , (20) , (18) and (27) now give that

A^{n} = R_{n} (A) = ∑_{i=0}^{m−1} α_{n,i}P_{i} (A) = ∑_{i=0}^{m−1} z_{n−i}A_{i} = ∑_{i=0}^{m−1} y_{n−i}A_{i}.

which completes the proof of (19) . □

4. Further Combinatorial Identities

Some nice combinatorial identities can be derived from Theorem 4 by considering various particular matrices with simple forms.

Corollary 4. Let n be a positive integer. Then

∑_{k_{1}+2k_{2}+···+mk_{m}=n}( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} )(−1)^{n−(k_{1}+···+k_{m})} ( \begin{matrix}m \\ m − 1 \end{matrix} )^{k_{1}}… ( \begin{matrix}m \\ 0 \end{matrix} )^{k_{m}}= ( \begin{matrix}n + m − 1 \\ m − 1 \end{matrix} ),

where ( \begin{matrix}n + m − 1 \\ m − 1 \end{matrix} ) is the number of m- combinations with repetition of finite set \{1, …, n\} ,

and the summation is taken over all m-tuples (k_{1}, k_{2}, …, k_{m}) of integers k_{j} ≥ 0 satisfying the relation k_{1} + 2k_{2} + ⋯ + mk_{m} = n.

Proof. Let J_{m} be the m × m Jordan matrix,

J_{m} = ( \begin{matrix}1 & 1 & 0 & ⋯ & 0 \\ 0 & 1 & 1 & ... & ⋮ \\ 0 & 0 & ... & ... & 0 \\ ⋮ & ⋮ & ... & 1 & 1 \\ 0 & 0 & ⋯ & 0 & 1 \end{matrix} ) .

The characteristic polynomial of J_{m} is (X − 1)^{m}. We also have J_{m}^{n} = (( \begin{matrix}n \\ j − i \end{matrix} ))_{1≤i,j≤m} .

Applying Theorem 4 with A = J_{m}, and considering the (1, m) entries of both sides of

(19), we obtain the relation ( \begin{matrix}n \\ m − 1 \end{matrix} ) = y_{n−(m−1)}, which leads to the result. □

From Corollary 4, we obtain the following combinatorial identities, for m = 2, 3, 4.

∑_{2i≤n} (−1)^{i} ( \begin{matrix}n − i \\ i \end{matrix} ) 2^{n−2i} = n + 1,

∑_{2i+3j≤n} (−1)^{i} ( \begin{matrix}n − i − 2j \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) 3^{n−i−3j} = \binom{n + 1}{2}

∑_{2i+3j+4k≤n} (−1)^{i+k} ( \begin{matrix}n − i − 2j − 3k \\ i + j + k \end{matrix} ) ( \begin{matrix}i + j + k \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) 2^{2n−3i−4j−8k}3^{i} = \binom{n + 3}{3}

Like J. Mc Laughlin and B. Sury [8, Corollary 6], we can also derive Corollary 4 from the following result.

Corollary 5. ([8, Theorem 1]) Let x_{1}, x_{2}, …, x_{m} be elements of the unitary commutative ring A with s_{k} = ∑_{1≤i_{1}<i_{2}<···<i_{k}≤m} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}}, for 1 ≤ k ≤ m. Then, for each positive integer n,

∑_{k_{1}+k_{2}+···+k_{m}=n} x_{1}^{k_{1}} … x_{m}^{k_{m}} = ∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} ) (−1)^{n−k_{1}−···−k_{m}} s_{1}^{k_{1}} … s_{m}^{k_{m}},

with the summations being taken over all m-tuples (k_{1}, k_{2}, …, k_{m}) of integers k_{j} ≥ 0 satisfying the relations k_{1} + k_{2} + ⋯ + k_{m} = n for the left-hand side and k_{1} + 2k_{2} + ⋯ + mk_{m} = n for the right-hand side.

Proof. Let us give a proof of this result by using Theorem 2. For n > −m and 1 ≤ l ≤ m,

consider q_{n}^{(l)} := ∑_{k_{1}+k_{2}+···+k_{l}=n} x_{1}^{k_{1}}x_{2}^{k_{2}} … x_{l}^{k_{l}}, and q_{n} := q_{n}^{(m)}. Let E : β_{n} ⟼ β_{n+1} be the shift

operator which acts on any sequence (β_{n})_{n}, and, for 1 ≤ l ≤ m, let Q_{l} be the operator given by Q_{l} := (E − x_{1}) (E − x_{2}) ⋯ (E − x_{l}) . Notice that Q_{m} = E^{m} − s_{1}E^{m−1} + ⋯ + (−1)^{m} s_{m}. Then, for n ≥ 1 and 2 ≤ l ≤ m, we have (E − x_{l}) · q_{n−l}^{(l)} = q_{n−(l−1)}^{(l−1)}. Therefore,

Q_{m} (q_{n−m}^{(m)}) = Q_{m−1} (q_{n−(m−1)}^{(m−1)}) = ⋯ = Q_{1} (q_{n−1}^{(1)}) = 0.

Thus,

q_{n} = s_{1}q_{n−1} − s_{2}q_{n−2} + ⋯ + (−1)^{m−1} s_{m}q_{n−m}, for n ≥ 1.  (28)

By the definition of q_{n}, we also have

q_{n} = 0 for n < 0 and q_{0} = 1.  (29)

Applying Theorem 2 to the sequence (q_{n})_{n>−m} , we obtain the result. □

Corollary 4 follows immediately by setting x_{i} = 1 for all i in the previous corollary.

The following theorem is an extension of a result of J. Mc Laughlin and B. Sury [8, Theorem 3].

Theorem 5. Let K be a field of characteristic zero, and let x_{1}, x_{2}, …, x_{m} be independent variables. Then, in K (x_{1}, x_{2}, …, x_{m}) ,

∑_{k_{1}+···+k_{m}=n} x_{1}^{k_{1}}x_{2}^{k_{2}} … x_{m}^{k_{m}} = ∑_{i=1}^{m} \frac{x_{i}^{n+m−1}}{∏_{j≠i} (x_{i} − x_{j})}.

Proof. For γ_{1}, γ_{2}, …, γ_{m} ∈ K (x_{1}, x_{2}, …, x_{m}) , let V (γ_{1}, γ_{2}, …, γ_{m}) denote the Vandermonde determinant defined by V (γ_{1}, γ_{2}, …, γ_{m}) = det (γ_{i}^{j−1})_{1≤i,j≤m} . It is well known that

V (γ_{1}, γ_{2}, …, γ_{m}) = ∏_{1≤i<j≤m} (γ_{j} − γ_{i}) . By (28) , the sequence (q_{n})_{n>−m} defined by

q_{n} = ∑_{k_{1}+k_{2}+···+k_{m}=n} x_{1}^{k_{1}}x_{2}^{k_{2}} … x_{m}^{k_{m}}

is a recurrent sequence with characteristic polynomial

X^{m} − s_{1}X^{m−1} + ⋯ + (−1)^{m} s_{m} = (X − x_{1}) (X − x_{2}) ⋯ (X − x_{m}) .

This polynomial has m distincts roots x_{1}, x_{2}, …, x_{m}. We deduce that there exist m elements A_{i} = A_{i} (x_{1}, x_{2}, …, x_{m}) ∈ K (x_{1}, x_{2}, …, x_{m}) , 1 ≤ i ≤ m, such that

q_{n} = ∑_{i=1}^{m} A_{i}x_{i}^{n} for n ≥ −m.

The initial conditions given by (28) lead to the Cramer system ∑_{i=1}^{m} \frac{A_{i}}{x_{i}^{j}} = δ_{j,0} for 0 ≤ j ≤ m − 1. The resolution of this system gives

A_{i} = \frac{V (\frac{1}{x_{1}} , …, \frac{1}{x_{i−1}} , 0, \frac{1}{x_{i+1}} , …, \frac{1}{x_{m}} )}{V (\frac{1}{x_{1}} , …, \frac{1}{x_{i−1}} , \frac{1}{x_{i}} , \frac{1}{x_{i+1}} , …, \frac{1}{x_{m}} )} = \frac{x_{i}^{m−1}}{∏_{j≠i} (x_{i} − x_{j})}, for 1 ≤ i ≤ m.

This completes the proof. □

Let us now give an application to Stirling numbers. For n ≥ 0, with the notations of [5] , the Stirling numbers of the first kind [ \begin{matrix}n \\ k \end{matrix} ] , and the Stirling numbers of the second kind \{ \begin{matrix}n \\ k \end{matrix} \} , can be defined by the equations

X\overline{n} = ∑_{k=0}^{n} [ \begin{matrix}n \\ k \end{matrix} ] X^{k},  (30)

with X\overline{n} := \{ \begin{matrix}1 if n = 0, \\ X (X + 1) (X + 2) ⋯ (X + n − 1) if n ≥ 1, \end{matrix} and

X^{n} = ∑_{k=0}^{n} \{ \begin{matrix}n \\ k \end{matrix} \} X\underline{k},  (31)

with X\underline{k} := \{ \begin{matrix}1 if k = 0, \\ X (X − 1) (X − 2) ⋯ (X − k + 1) if k ≥ 1. \end{matrix}

It is well known [p. 38 (Vol. 2), 4] that \{ \begin{matrix}n \\ k \end{matrix} \} = \frac{1}{k!} ∑_{i=0}^{k} (−1)^{k−i} \binom{k}{i}i^{n}. From Theorem 5 and Corollary 5, we deduce

∑_{k_{1}+2k_{2}+···+mk_{m}=n} ( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} ) (−1)^{n−k_{1}−···−k_{m}} s_{1}^{k_{1}} … s_{m}^{k_{m}} = ∑_{i=1}^{m} \frac{x_{i}^{n+m−1}}{∏_{j≠i} (x_{i} − x_{j})}. (32)

If we take x_{k} = − (k − 1) for 1 ≤ k ≤ m, we have s_{k} = (−1)^{k} [ \begin{matrix}m \\ m − k \end{matrix} ], for 1 ≤ k ≤ m, and relation (32) gives the following result Corollary 6. For all positive integers m and n,

∑_{k_{1}+2k_{2}+···+mk_{m}=n}( \begin{matrix}k_{1} + ⋯ + k_{m} \\ k_{1}, …, k_{m} \end{matrix} ) (−1)^{n−(k_{1}+···+k_{m})} [ \begin{matrix}m \\ m − 1 \end{matrix} ]^{k_{1}}… [ \begin{matrix}m \\ 0 \end{matrix} ]^{k_{m}}= \{ \begin{matrix}n + m − 1 \\ m − 1 \end{matrix} \} .

Note that Theorem 5 gives the following relation, which is stated in [p. 42, (Vol. 2), 4].

For all positive integers m and n, \{ \begin{matrix}n + m − 1 \\ m − 1 \end{matrix} \} = ∑_{k_{1}+···+k_{m−1}=n} 1^{k_{1}}2^{k_{2}} … (m − 1)^{k_{m−1}} .

For m = 3, 4 and 5, we obtain

∑_{2i≤n} (−1)^{i} ( \begin{matrix}n − i \\ i \end{matrix} ) 2^{i}3^{n−2i} = 2^{n+1} − 1,

∑_{2i+3j≤n} (−1)^{i} ( \begin{matrix}n − i − 2j \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) 6^{n−2i−2j}11^{i} = \frac{3^{n+2} − 2^{n+3} + 1}{2},

\begin{matrix}∑_{2i+3j+4k≤n} (−1)^{i+k} ( \begin{matrix}n − i − 2j − 3k \\ i + j + k \end{matrix} ) ( \begin{matrix}i + j + k \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) 2^{n−2i−2j−k}3^{k}5^{n−i−j−4k}7^{i} \\ = \frac{4^{n+3} − 3^{n+4} + 3 · 2^{n+3} − 1}{6}. \end{matrix}

Corollary 7. Let n be a positive integer and let x and y be indeterminates. Then

∑_{2i+3j+4k≤n} (−1)^{i+k} ( \begin{matrix}n − i − 2j − 3k \\ i + j + k \end{matrix} ) ( \begin{matrix}i + j + k \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) (2x + 2y)^{n−2i−2j−4k} ×

× (xy)^{j+2k} (x^{2} + 4xy + y^{2})^{i} = \frac{(n + 1) (x^{n+3} − y^{n+3}) − (n + 3) xy (x^{n+1} − y^{n+1})}{(x − y)^{3}}.

Corollary 8. Let n a positive integer and x, y be indeterminates. Then

∑_{2i+3j+4k≤n} (−1)^{i+k} ( \begin{matrix}n − i − 2j − 3k \\ i + j + k \end{matrix} ) ( \begin{matrix}i + j + k \\ i + j \end{matrix} ) ( \begin{matrix}i + j \\ i \end{matrix} ) ×

× (3x + y)^{n−2i−3j−4k} x^{i+2j+3k}y^{k} (3x + 3y)^{i} (x + 3y)^{j}

= \frac{(n + 1) (n + 2) (x^{n+3} − y^{n+3}) − (n + 3) y [n (x^{n+2} − y^{n+2}) + (n + 2) x^{n+1} (x − y)]}{2 (x − y)^{3}}.

Proof of Corollaries 7 and 8. It suffices to put, in Corollary 4, x_{1} = x_{2} = x and x_{3} = x_{4} = y to obtain Corollary 7; x_{1} = x_{2} = x_{3} = x and x_{4} = y to obtain Corollary 8. □

Acknowledgments. The authors are grateful to the referee and would like to thank him/her for comments which improved the quality of this paper.

References

[1] L. Bernstein: Zeros of the function f (n) = ∑_{i} (−1 )^{i} ( \begin{matrix}n − 2i \\ i \end{matrix} ). J. Number Theory, 6 (1974), 264-270.

[2] L. Carlitz: Some combinatorial identities of Bernstein. SIAM J. Math. Anal., 9 (1978), no. 1, 65–75.

[3] L. Carlitz: Recurrences of the third order and related combinatorial identities. Fibonacci Quarterly, 16 (1978), no. 1, 11–18.

[4] L. Comtet: Analyse combinatoire. Puf, Coll. Sup. Paris, (1970), Vol. 1 & Vol. 2.

[5] R. L. Graham, D. E. Knuth, O. Patashnik: Concrete Mathematics. Addison Wesley Publishing Company, Inc., (1994).

[6] R. C. Johnson: Matrix methods for Fibonacci and related sequences. www.dur.ac.uk/ bob.johnson/ fibonacci/, (2004).

[7] J. Mc Laughlin: Combinatorial identities deriving from the n-th power of 2×2 matrix. Electronic Journal of Combinatorial Number Theory, A19, 4 (2004).

[8] J. Mc Laughlin, B. Sury: Powers of matrix and combinatorial identities. Electronic Journal of Combinatorial Number Theory, A13, 5 (2005).

[9] Rajesh Ram: Fibonacci number formulae. http://users.tellurian.net/hsejar/maths/ fibonacci/ (2003).

[10] Z. F. Starc: Solution of the Problem 6.98. Univ. Beograd. Publikac. Elektrotehn. Fak. Ser. Mat. 13 (2002), 103-105.

[11] S. Tanny, M. Zuker: Analytic methods applied to a sequence of binomial coeffients. Discrete Math., 24 (1978), 299-310.

[12] N. N. Vorob’ev: Fibonacci numbers. Translated from the russian by Halina Moss, Translation editor Ian N. Sneddon Blaisdell Publishing Co., New York-London, (1961).