INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A13

POWERS OF A MATRIX AND COMBINATORIAL IDENTITIES

J. Mc Laughlin

Mathematics Department, Trinity College, 300 Summit Street, Hartford, CT 06106-3100

                       james.mclaughlin@trincoll.edu

B. Sury

Stat-Math Unit, Indian Statistical Institute, 8th Mile Mysore Road, Bangalore 560 059, India.

                            sury@isibang.ac.in

Received: 12/09/04, Accepted: 6/23/05, Published: 6/29/05

Abstract

In this article we obtain a general polynomial identity in k variables, where k ≥ 2 is an arbitrary positive integer. We use this identity to give a closed-form expression for the entries of the powers of a k × k matrix. Finally, we use these results to derive various combinatorial identities.

1. Introduction

In [4], the second author had observed that the following ‘curious’ polynomial identity holds:

∑(−1)^{i}\binom{n − i}{i}(x + y)^{n−2i}(xy)^{i} = x^{n} + x^{n−1}y + ⋯ + xy^{n−1} + y^{n}.

The proof was simply observing that both sides satisfied the same recursion. He had also observed (but not published the result) that this recursion defines in a closed form the entries of the powers of a 2 × 2 matrix in terms of its trace and determinant and the entries of the original matrix. The first author had independently discovered this fact and derived several combinatorial identities as consequences [2].

In this article, for a general k, we obtain a polynomial identity and show how it gives a closed-form expression for the entries of the powers of a k × k matrix. From these, we derive some combinatorial identities as consequences.

2NTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A13

2. Main Results

Throughout the paper, let K be any fixed field of characteristic zero. We also fix a positive integer k. The main results are the following two theorems:

Theorem 1. Let x_{1}, ⋯, x_{k} be independent variables and let s_{1}, ⋯, s_{k} denote the various symmetric polynomials in the x_{i}’s of degrees 1, 2 ⋯, k respectively. Then, in the polynomial ring K[x_{1}, ⋯, x_{k}], for each positive integer n, one has the identity

∑_{r_{1}+···+r_{k}=n} x_{1}^{r_{1}}x_{2}^{r_{2}} ⋯ x_{k}^{r_{k}} =

∑_{2i_{2}+3i_{3}+···+ki_{k}≤n} c(i_{2}, ⋯, i_{k}, n)s_{1}^{n−2i_{2}−3i_{3}−···−ki_{k}}(−s_{2})^{i_{2}}s_{3}^{i_{3}} ⋯ ((−1)^{k−1}s_{k})^{i_{k}},

where

c(i_{2}, ⋯, i_{k}, n) = \frac{(n − i_{2} − 2i_{3} − ⋯ − (k − 1)i_{k})!}{i_{2}! ⋯ i_{k}!(n − 2i_{2} − 3i_{3} − ⋯ − (ki_{k})!}.

Theorem 2. Suppose A ∈ M_{k}(K) and let

T^{k} − s_{1}T^{k−1} + s_{2}T^{k−2} + ⋯ + (−1)^{k}s_{k} I

denote its characteristic polynomial. Then, for all n ≥ k, one has

A^{n} = b_{k−1}A^{k−1} + b_{k−2}A^{k−2} + ⋯ + b_{0} I,

where

b_{k−1} = a(n − k + 1),
b_{k−2} = a(n − k + 2) − s_{1}a(n − k + 1),
⋮
b_{1} = a(n − 1) − s_{1}a(n − 2) + ⋯ + (−1)^{k−2}s_{k−2}a(n − k + 1),
b_{0} = a(n) − s_{1}a(n − 1) + ⋯ + (−1)^{k−1}s_{k−1}a(n − k + 1)
= (−1)^{k−1}s_{k}a(n − k).

and

a(n) = c(i_{2}, ⋯, i_{k}, n)s_{1}^{n−i_{2}−2i_{3}−···−(k−1)i_{k}}(−s_{2})^{i_{2}}s_{3}^{i_{3}} ⋯ ((−1)^{k−1}s_{k})^{i_{k}},

with

c(i_{2}, ⋯, i_{k}, n) = \frac{(n − i_{2} − 2i_{3} − ⋯ − (k − 1)i_{k})!}{i_{2}! ⋯ i_{k}!(n − 2i_{2} − 3i_{3} − ⋯ − (ki_{k})!}.

as in Theorem 1.

Proof of Theorems 1 and 2. In Theorem 1, if a(n) denotes either side, it is straightforward to verify that

a(n) = s_{1}a(n − 1) − s_{2}a(n − 2) + ⋯ + (−1)^{k−1}s_{k}a(n − k).

Theorem 2 is a consequence of Theorem 1 on using induction on n.

□

The special cases k = 2 and k = 3 are worth noting for it is easier to derive various combinatorial identities from them.

Corollary 1. (i) Let A ∈ M_{3}(K) and let X^{3} = tX^{2} − sX + d denote the characteristic polynomial of A. Then, for all n ≥ 3,

A^{n} = a_{n−1}A + a_{n−2}Adj(A) + (a_{n} − ta_{n−1}) I, (2.1)

where

a_{n} = ∑_{2i+3j≤n}(−1)^{i}\binom{i + j}{j}\binom{n − i − 2j}{i + j}t^{n−2i−3j}s^{i}d^{j}

for n > 0 and a_{0} = 1.

(ii) Let B ∈ M_{2}(K) and let X^{2} = t X −d denote the characteristic polynomial of B. Then, for all n ≥ 2,

B^{n} = b_{n}I + b_{n−1}Adj(B)

for all n ≥ 2, where

b_{n} = ∑ \binom{n − i}{i}(−1)^{i}t^{n−2i}d^{i}.

Corollary 2. Let θ ∈ K, B ∈ M_{2}(K) and t denote the trace and d the determinant of B. We have the following identity in M_{2}(K) :

(a_{n−1} − θa_{n−2})B + (a_{n} − (θ + t)a_{n−1} + θa_{n−2}t)I = y_{n−1}B + (y_{n} − t y_{n−1})I,

where

a_{n} = ∑_{2i+3j≤n}(−1)^{i}\binom{i + j}{j}\binom{n − i − 2j}{i + j}(θ + t)^{n−2i−3j}(θt + d)^{i}(θd)^{j}

and

y_{n} = ∑ \binom{n − i}{i}(−1)^{i}t^{n−2i}d^{i}.

In particular, for any θ ∈ K, one has

b_{n} − (θ + 1)b_{n−1} + θb_{n−2} = 1,

where

b_{n} = ∑_{2i+3j≤n}(−1)^{i}\binom{i + j}{j}\binom{n − i − 2j}{i + j}(θ + 2)^{n−2i−3j}(1 + 2θ)^{i}θ^{j}.

Corollary 3. The numbers c_{n} = ∑_{2i+3j=n}(−1)^{i}\binom{i+j}{j}2^{i}3^{j} satisfy

c_{n} + c_{n−1} − 2c_{n−2} = 1.

Proof. This is the special case of Corollary 2 where we take θ = −2. Note that the sum defining c_{n} is over only those i, j for which 2i + 3j = n.

Note than when k = 3, Theorem 1 can be rewritten as follows:

Theorem 3. Let n be a positive integer and x, y, z be indeterminates. Then

(2.2) ∑_{2i+3j≤n}(−1)^{i}\binom{i + j}{j}\binom{n − i − 2j}{i + j}(x + y + z)^{n−2i−3j}(xy + yz + zx)^{i}(xyz)^{j}

= \frac{x y (x^{n+1} − y^{n+1}) − x z (x^{n+1} − z^{n+1}) + y z (y^{n+1} − z^{n+1})}{(x − y) (x − z) (y − z)}.

Proof. In Corollary 1, let

A = (\begin{matrix}x + y + z & 1 & 0 \\ −x y − x z − y z & 0 & 1 \\ x y z & 0 & 0 \end{matrix}) .

Then t = x + y + z, s = xy + xz + yz and d = xyz. It is easy to show (by first diagonalizing A) that the (1, 2) entry of A^{n} equals the right side of (2.2), with n + 1 replaced by n, and the (1, 2) entry on the right side of (2.1) is a_{n−1}.

Corollary 4. Let x and z be indeterminates and n a positive integer. Then

∑_{2i+3j≤n}(−1)^{i}\binom{i + j}{j}\binom{n − i − 2j}{i + j}(2x + z)^{n−2i−3j}(x^{2} + 2xz)^{i}(x^{2}z)^{j}

= \frac{x^{2+n} + n x^{1+n} (x − z) − 2 x^{1+n} z + z^{2+n}}{(x − z)^{2}} .

Proof. Let y → x in Theorem 3.

Some interesting identities can be derived by specializing the variables in Theorem 1. For instance, in [5], it was noted that Binet’s formula for the Fibonacci numbers is a consequence of Theorem 1 for k = 2. Here is a generalization.

Corollary 5. (Generalization of Binet’s formula) Let the numbers F_{k}(n) be defined by the recursion

F_{k}(0) = 1, F_{k}(r) = 0, ∀r < 0,
F_{k}(n) = F_{k}(n − 1) + F_{k}(n − 2) + ⋯ + F_{k}(n − k).

Then, we have

F_{k}(n) = ∑_{2i_{2}+···+ki_{k}≤n} \frac{(n − i_{2} − 2i_{3} − ⋯ − (k − 1)i_{k})!}{i_{1}!i_{2}! ⋯ i_{k}!(n − 2i_{2} − 3i_{3} − ⋯ − ki_{k})!}.

Further, this equals ∑_{r_{1}+···+r_{k}=n} λ_{1}^{r_{1}} ⋯ λ_{k}^{r_{k}} where λ_{i}, 1 ≤ i ≤ k are the roots of the equation T^{k} − T^{k−1} − T^{k−2} − ⋯ − 1 = 0.

Proof. The recursion defining F_{k}(n)’s corresponds to the case s_{1} = −s_{2} = ⋯ = (−1)^{k−1}s_{k} = 1 of the theorem.

Corollary 6.

∑ c(i_{2}, ⋯, i_{k}, n)k^{n} ∏_{j=2}^{k} ((−1)^{j−1}k^{−j}\binom{k}{j})^{i_{j}} = \binom{n + k − 1}{k}.

where

c(i_{2}, ⋯, i_{k}, n) = \frac{(n − i_{2} − 2i_{3} − ⋯ − (k − 1)i_{k})!}{i_{2}! ⋯ i_{k}!(n − 2i_{2} − 3i_{3} − ⋯ − ki_{k})!}.

Proof. Take x_{i} = 1 for all i in Theorem 1. The left side of Theorem 1 is simply the sum ∑_{r_{1}+···+r_{k}=n} 1.

From Theorem3 we have the following binomial identities as special cases.

Proposition 1. (i) Let λ be the unique positive real number satisfying λ^{3} = λ + 1. Let x, y denote the complex conjugates such that xy = λ, x + y = λ^{2}, and let z = −\frac{1}{λ}. Then,

∑_{2i+3j≤n}(−1)^{j}\binom{n − 2j}{j} = ∑_{r+s+t=n} x^{r}y^{s}z^{t}

= \frac{x y (x^{n+1} − y^{n+1}) − x z (x^{n+1} − z^{n+1}) + y z (y^{n+1} − z^{n+1})}{(x − y) (x − z) (y − z)}.

(ii)

∑_{2i+3j≤n}(−1)^{j}\binom{i + j}{j}\binom{n − i − 2j}{i + j} = [(n + 2)/2].

(iii)

∑ \binom{n − 2j}{j}(−4)^{j}3^{n−3j} = \frac{(3n + 4)2^{n+1} + (−1)^{n}}{9} .

(iv)

∑ \binom{n − 2j}{j}3^{n−3j}(−2)^{j}

= \frac{(1 + \sqrt{3})^{n+1} − (1 − \sqrt{3})^{n+1}}{2\sqrt{3}} + \frac{(1 + \sqrt{3})^{n+1} + (1 − \sqrt{3})^{n+1}}{6} − \frac{1}{3}.

3. Commutating Matrices

In this section we derive various combinatorial identities by writing a general 3 × 3 matrix A as a product of commuting matrices.

Proposition 2. Let A be an arbitrary 3 × 3 matrix with characteristic equation x^{3} − tx^{2} + s x − d = 0, d ≠ 0. Suppose p is arbitrary, with p^{3} + p^{2}t + ps + d ≠ 0, p ≠ 0, −t. If n is a positive integer, then

(3.1) A^{n} = (\frac{p d}{p^{3} + p^{2}t + sp + d})^{n} ∑_{r=0}^{3n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}

× (\frac{−p(p + t)^{2}}{d} )^{j} (\frac{−(p + t)}{p})^{k} (\frac{−A}{p + t})^{r} .

Proof. This follows from the identity

A = \frac{−1}{p^{3} + p^{2}t + sp + d} (pA^{2} − Ap(p + t) − d I) (A + p I) ,

after raising both sides to the n-th power and collecting powers of A. Note that the two matrices pA^{2} − Ap(p + t) − d I and A + p I commute.

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

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r} (\frac{p(p + x + y + z)^{2}}{xyz} )^{j}

× (\frac{p + x + y + z}{p} )^{k} \frac{x y (x^{r} − y^{r}) − x z (x^{r} − z^{r}) + y z (y^{r} − z^{r})}{(p + x + y + z)^{r}}

= (x y (x^{n} − y^{n}) − x z (x^{n} − z^{n}) + y z (y^{n} − z^{n}))

× (\frac{p^{3} + p^{2} (x + y + z) + p (x y + x z + y z) + x y z}{p x y z} )^{n} .

Proof. Let A be the matrix from Theorem 3 and compare (1, 1) entries on both sides of (3.1).

Corollary 8. Let p, x and z be indeterminates and let n be a positive integer. Then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r} (\frac{p(p + 2x + z)^{2}}{x^{2}z} )^{j}

× (\frac{p + 2x + z}{p} )^{k} \frac{r x^{1+r} − x^{r} z − r x^{r} z + z^{1+r}}{(p + 2x + z)^{r}}

= (n x^{1+n} − x^{n} z − n x^{n} z + z^{1+n}) (\frac{p^{3} + p^{2} (2x + z) + p (x^{2} + 2x z) + x^{2} z}{p x^{2} z} )^{n} .

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A13 7

Proof. Divide both sides in the corollary above by x − y and let y → x. Corollary 9. Let p and x be indeterminates and let n be a positive integer. Then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r} (\frac{p(p + 3x)^{2}}{x^{3}} )^{j} (\frac{p + 3x}{p})^{k} \frac{r (1 + r) x^{−1+r}}{2(p + 3x)^{r}}

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

Proof. Divide both sides in the corollary above by (x − z)^{2} and let z → x. Corollary 10. Let p be an indeterminate and let n be a positive integer. Then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r}p^{j−k}(p + 3)^{2j+k−r} \frac{r (1 + r)}{2}

= \frac{n (1 + n)}{2} \frac{(p + 1)^{3n}}{p^{n}} .

Proof. Replace p by p x in the corollary above and simplify. Various combinatorial identities can be derived from Theorem 3 by considering matrices A such that particular entries in A^{n} have a simple closed form. We give four examples. Corollary 11. Let n be a positive integer.

(i) If p ≠ 0, −1, then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r}p^{j−k}(p + 3)^{2j+k−r}r = n\frac{(1 + p)^{3n}}{p^{n}} .

(ii) Let F_{n} denote the n-th Fibonacci number. If p ≠ 0, −1, ϕ or 1/ϕ (where ϕ is the golden ratio, then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{k+r}p^{j−k}(p + 2)^{2j+k−r}F_{r}

= F_{n} \frac{(1 + p)^{n}(−1 + p + p^{2})^{n}}{(−p)^{n}} .

(iii) If p ≠ 0, −1 or −2, then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r}p^{j−k}(p + 4)^{2j+k−r}2^{−j}(2^{r} − 1)

= (2^{n} − 1) (\frac{(1 + p)^{2}(p + 2)}{2p})^{n} .

(iv) If p ≠ 0, −1, −g or −h and gh ≠ 0, then

∑_{r=0}^{3 n} ∑_{j=0}^{n} ∑_{k=0}^{n} \binom{n}{j}\binom{n}{k}\binom{j}{r − j − k}(−1)^{j+k+r}p^{j−k}(p + 1 + g + h)^{2j+k−r} \frac{g^{r} + h^{r}}{(g h)^{j}}

= (g^{n} + h^{n}) (\frac{(1 + p)(g + p)(h + p)}{ghp})^{n} .

Proof. The results follow from considering the (1, 2) entries on both sides in Theorem 3 for the matrices

(\begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) , (\begin{matrix}1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) , (\begin{matrix}3 & 1 & 0 \\ −2 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) , (\begin{matrix}\frac{g + h}{2} & \frac{(g − h)^{2}}{4} & 0 \\ 1 & \frac{g + h}{2} & 0 \\ 0 & 0 & 1 \end{matrix}) ,

respectively.

4. A Result of Bernstein

In [1] Bernstein showed that the only zeros of the integer function

f(n) := ∑_{j≥0}(−1)^{j}\binom{n − 2j}{j}

are at n = 3 and n = 12. We use Corollary 1 to relate the zeros of this function to solutions of a certain cubic Thue equation and hence to derive Bernstein’s result.

Let

A = (\begin{matrix}1 & 1 & 0 \\ 0 & 0 & 1 \\ −1 & 0 & 0 \end{matrix}) .

With the notation of Corollary 1, t = 1, s = 0, d = −1, so that

a_{n} = ∑_{3j≤n}(−1)^{j}\binom{n − 2j}{j} = f(n),

and, for n ≥ 4,

A^{n} = f(n − 2)A^{2} + (f(n) − f(n − 2))A + (f(n) − f(n − 1)) I

= (\begin{matrix}f(n) & f(n − 1) & f(n − 2) \\ −f(n − 2) & −f(n − 3) & −f(n − 4) \\ −f(n − 1) & −f(n − 2) & −f(n − 3) \end{matrix}) .

The last equality follows from the fact that f(k + 1) = f(k) − f(k − 2), for k ≥ 2.

Now suppose f(n − 2) = 0. Since the recurrence relation above gives that f(n − 4) = −f(n − 1) and f(n) = f(n − 1) − f(n − 3), it follows that

(−1)^{n} = det(A^{n}) = |\begin{matrix}f(n − 1) − f(n − 3) & f(n − 1) & 0 \\ 0 & −f(n − 3) & f(n − 1) \\ −f(n − 1) & 0 & −f(n − 3) \end{matrix}|

= −f(n − 1)^{3} − f(n − 3)^{3} + f(n − 1)f(n − 3)^{2}.

Thus (x, y) = ±(f(n − 1), f(n − 3)) is a solution of the Thue equation

x^{3} + y^{3} − x y^{2} = 1.

One could solve this equation in the usual manner of finding bounds on powers of fundamental units in the cubic number field defined by the equation x^{3} − x + 1 = 0. Alternatively, the Thue equation solver in PARI/GP [3] gives unconditionally (in less than a second) that the only solutions to this equation are

(x, y) ∈ {(4, −3), (−1, 1), (1, 0), (0, 1), (1, 1)} ,

leading to Bernstein’s result once again.

References

[1] Bernstein, Leon Zeros of the functions f(n) = ∑_{i=0}(−1)^{i}(^{n−}_{i}^{2i}). J. Number Theory 6 (1974), 264–270.

[2] James Mc Laughlin, Combinatorial Identities Deriving from the n-th Power of a 2 × 2 Matrix. Integers 4 (2004), A19, 14 pp.

[3] PARI/GP: http://pari.math.u-bordeaux.fr/

[4] B. Sury, A curious polynomial identity. Nieuw Arch. Wisk. (4) 11 (1993), no. 2, 93–96.

[5] —–, A parent of Binet’s forumla? Math. Magazine 77 (2004), no. 4, 308-310.