INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A19

COMBINATORIAL IDENTITIES DERIVING FROM THE n-th POWER OF A 2 × 2 MATRIX

J. Mc Laughlin ^{1}

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

                      james.mclaughlin@trincoll.edu

Received: 1/27/04, Revised: 10/11/04, Accepted: 10/15/04, Published: 10/27/04

Abstract

In this paper we give a new formula for the n-th power of a 2 × 2 matrix.

More precisely, we prove the following: Let A = (\begin{matrix}a & b \\ c & d \end{matrix}) be an arbitrary 2×2 matrix,

T = a + d its trace, D = ad − bc its determinant and define

y_{n} : = ∑_{i=0}^{⌊n/2⌋} \binom{n − i}{i}T^{n−2i}(−D)^{i}.

Then, for n ≥ 1,

A^{n} = (\begin{matrix}y_{n} − d y_{n−1} & b y_{n−1} \\ c y_{n−1} & y_{n} − a y_{n−1} \end{matrix}) .

We use this formula together with an existing formula for the n-th power of a matrix, various matrix identities, formulae for the n-th power of particular matrices, etc, to derive various combinatorial identities.

1. Introduction

In this paper we derive a formula for the n-th power of a 2 × 2 matrix. Although we were initially not aware of the fact, the formula is not new and in fact Schwerdtfeger ([7], pages 104–105) outlines a method due to Jacobsthal [3] for finding the n-th power of an arbitrary 2 × 2 matrix A which, after a little manipulation, is essentially equivalent to the method described in Theorem 1. What makes the formula somewhat interesting is that various combinatorial identities follow immediately from it and we show how to derive some of these. We further exploit the formula by showing how to use certain elementary matrix identities to derive other known combinatorial identities and also some new identities.

1http://www.trincoll.edu/ jmclaugh/

Throughout the paper, let I denote the 2 × 2-identity matrix and n an arbitrary positive integer. In [11], Williams gave the following formula for the n-th power of 2 × 2 matrix A with eigenvalues α and β:

A^{n} = \begin{cases}α^{n} (\frac{A−βI}{α−β} ) + β^{n} (\frac{A−αI}{β−α} ) , if α ≠ β, \\ α^{n−1}(nA − (n − 1)αI),  if α = β. \end{cases}  (1)

Blatz had given a similar, if slightly more complicated expression, in [1].

For our present purposes (producing combinatorial identities), it is preferable to express A^{n} directly in terms of the entries of A, rather than the eigenvalues of A. If we let T denote the trace of A and D its determinant, then, without loss of generality, α = (T + \sqrt{T^{2} − 4 D})/2 and β = (T − \sqrt{T^{2} − 4 D})/2. A little elementary arithmetic gives that (in the case α ≠ β), if

z_{n} := \frac{α^{n} − β^{n}}{α − β} = \frac{∑_{m=0}^{⌊(n−1)/2⌋} \binom{n}{2m+1}T^{n−2m−1}(T^{2} − 4D)^{m}}{2^{n−1}} ,  (2)

then

A^{n} = z_{n}A − z_{n−1} D I.  (3)

Equation 3 also holds in the case of equal eigenvalues (when T^{2} − 4 D = 0), if z_{n} is assumed to have the value on the right of (2). The key point here is that if another closed-form expression exists for A^{n}, then equating the expressions for the entries of A^{n} from this closed form with the expressions derived from Equations 2 and 3 will produce various identities.

As an illustration, we consider the following example. Let {F_{n}}_{n=1}^{∞} denote the Fibonacci sequence, defined by F_{0} = 0, F_{1} = 1 and F_{i+1} = F_{i} + F_{i−1}, for i ≥ 1. The identity

(\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix})^{n} = (\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{n−1} \end{matrix})  (4)

leads directly to several of the known formulae involving the Fibonacci numbers. For example, direct substitution of T = −D = 1 in Equation 2 gives Formula 91 from Vajda’s list [9]:

F_{n} = \frac{∑_{m=0}^{⌊(n−1)/2⌋} \binom{n}{2m+1}5^{m}}{2^{n−1}} .  (5)

Many other formulae can be similarly derived. This method of deriving combinatorial identities of course needs two expressions for A^{n} and for a general 2 × 2 matrix, these have not been available.

In this present paper we remedy this situation by presenting a new formula for A^{n}, where the entries are also expressed in terms of the entries in A.

2. Main Theorem

We prove the following theorem.

Theorem 1 Let

A = (\begin{matrix}a & b \\ c & d \end{matrix})  (6)

be an arbitrary 2 × 2 matrix and let T = a + d denote its trace and D = ad − bc its determinant. Let

y_{n} = ∑_{i=0}^{⌊n/2⌋} \binom{n − i}{i}T^{n−2i}(−D)^{i}.  (7)

Then, for n ≥ 1,

A^{n} = (\begin{matrix}y_{n} − d y_{n−1} & b y_{n−1} \\ c y_{n−1} & y_{n} − a y_{n−1} \end{matrix}) .  (8)

Proof. The proof is by induction. Equation 8 is easily seen to be true for n = 1, 2, so suppose it is true for n = 1, …, k. This implies that

A^{k+1} = (\begin{matrix}a y_{k} + (b c − a d)y_{k−1} & b y_{k} \\ c y_{k} & d y_{k} + (b c − a d)y_{k−1} \end{matrix}) .

Thus the result will follow if it can be shown that

y_{k+1} = (a + d)y_{k} + (b c − a d)y_{k−1}.

Upon substituting from Equation 7, we have that

(a + d)y_{k} + (b c − a d)y_{k−1}

= ∑_{i=0}^{⌊k/2⌋} \binom{k − i}{i}T^{k+1−2i}(−D)^{i} + ∑_{i=0}^{⌊(k−1)/2⌋} \binom{k − 1 − i}{i}T^{k−1−2i}(−D)^{i+1}

= ∑_{i=0}^{⌊k/2⌋} \binom{k − i}{i}T^{k+1−2i}(−D)^{i} + ∑_{i=1}^{⌊(k+1)/2⌋} \binom{k − i}{i − 1}T^{k+1−2i}(−D)^{i}.

If k is even, then ⌊k/2⌋ = ⌊(k + 1)/2⌋, and

(a + d)y_{k} + (b c − a d)y_{k−1} = \binom{k}{0}T^{k+1} + ∑_{i=1}^{⌊(k+1)/2⌋} (\binom{k − i}{i} + \binom{k − i}{i − 1}) T^{k+1−2i}(−D)^{i}

= ∑_{i=0}^{⌊(k+1)/2⌋} \binom{k + 1 − i}{i}T^{k+1−2i}(−D)^{i} = y_{k+1}.

If k is odd, then ⌊k/2⌋ = ⌊(k − 1)/2⌋, and

(a + d)y_{k} + (b c − a d)y_{k−1} = \binom{k}{0}T^{k+1} + ∑_{i=1}^{⌊(k−1)/2⌋} (\binom{k − i}{i} + \binom{k − i}{i − 1}) T^{k+1−2i}(−D)^{i}

+ \binom{k − ⌊(k + 1)/2⌋}{⌊(k + 1)/2⌋ − 1}T^{k+1−2⌊(k+1)/2⌋}(−D)^{⌊(k+1)/2⌋}

= ∑_{i=0}^{⌊(k+1)/2⌋} \binom{k + 1 − i}{i}T^{k+1−2i}(−D)^{i} = y_{k+1}.

This completes the proof. □

The aim now becomes to use combinations of the formulae at (3) and (8), together with various devices such writing A^{nk} = (A^{k})^{n}, writing A = B + C or A = B C where B and C commute, etc, to produce combinatorial identities. One can also consider particular matrices A whose n-th power has a simple form, and then use the formulae at (3) and (8) to derive combinatorial identities,

As an immediate consequence of (3) and (8), we have the following corollary to Theorem 1.

Corollary 1 For 1 ≤ j ≤ ⌊(n − 1)/2⌋,

\binom{n}{2j + 1} = ∑_{i=j}^{⌊(n−1)/2⌋}(−1)^{i−j}2^{n−1−2i}\binom{i}{j}\binom{n − 1 − i}{i},  (9)

\binom{n − 1 − j}{j} = 2^{−n+1+2j} ∑_{i=j}^{⌊(n−1)/2⌋} \binom{n}{2i + 1}\binom{i}{j}.

Proof. For the first identity, we equate the (1, 2) entries at (3) and (8) and then let T = 2x and D = x^{2} − y. This gives that

∑_{i=0}^{⌊(n−1)/2⌋} \binom{n − 1 − i}{i}(2x)^{n−1−2i}(y − x^{2})^{i} = ∑_{i=0}^{⌊(n−1)/2⌋} \binom{n}{2 i + 1}x^{n−1−2i}y^{i}.

We now expand the left side and equate coefficients of equal powers of y/x^{2}.

For the second identity, we similarly equate the (1, 2) entries at (3) and (8), expand (T^{2} −4D)^{m} by the binomial theorem and compare coefficients of like powers of (−D/T^{2}). □

Remark: The literature on combinatorial identities is quite extensive and all of the identities we describe in this paper may already exist elsewhere. However, we believe that at least some of the methods used to generate/prove them are new.

3. Some Formulae for the Fibonacci Numbers

The identity ([10], pp. 18-20)

F_{n} = ∑_{i=0}^{⌊(n−1)/2⌋} \binom{n − 1 − i}{i}  (10)

follows from (4), (7) and (8), upon setting T = −D = b = 1.

The Lucas sequence {L_{n}}_{n=1}^{∞} is defined by L_{1} = 1, L_{2} = 3 and L_{n+1} = L_{n} + L_{n−1}, for n ≥ 2. The identity A^{n k} = (A^{n})^{k} implies

(\begin{matrix}F_{n k+1} & F_{n k} \\ F_{n k} & F_{n k−1} \end{matrix}) = (\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{n−1} \end{matrix})^{k} .

The facts that L_{n} = F_{n+1} + F_{n−1} and F_{n+1}F_{n−1} − F_{n}^{2} = (−1)^{n} together with Theorem 1 now imply the following identity from [4] (page 5):

F_{n k} = F_{n} ∑_{i=0}^{⌊(k−1)/2⌋} \binom{k − 1 − i}{i}L_{n}^{k−1−2i}(−1)^{i(n+1)}.  (11)

Let i := \sqrt{−1} and define B := \frac{1}{\sqrt{2 i−1}} (\begin{matrix}1 + i & i \\ i & 1 \end{matrix}). Then B^{2} = (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}), leading to the

identity:

F_{k} = \frac{1}{i^{k−1}} ∑_{m=0}^{k−1} \binom{2k − 1 − m}{m}(2 + i)^{k−1−m}(−1)^{m},  (12)

a variant of Ram’s formula labelled FeiPi at [6].

Many similar identities for the Fibonacci and Lucas sequences can also be easily derived from Theorem 1.

4. A Binomial Expansion from Williams’ Formula

Proposition 1 Let n ∈ ℕ and 1 ≤ t ≤ n, t integral. Then

\binom{n}{t} = ∑_{m=0}^{⌊ \frac{n−1}{2} ⌋} ∑_{j=0}^{n−1−2m}(−1)^{m}2^{n−1−2m−j}\binom{n − 1 − m}{m}\binom{n − 1 − 2m}{j}\binom{m}{t − j − 1}. (13)

Proof. Let A = (\begin{matrix}f + 2e & 1 \\ 0 & f \end{matrix}). The eigenvalues of A are clearly f + 2e and f. With the

notation of Theorem 1, T = 2(e + f) and D = f(f + 2e). If we now equate the (1, 2) entry from the left side of Equation 1 with the (1, 2) entry from the left side of Equation 8, we get, after a little manipulation, that

(f + 2e)^{n} = f^{n} + 2e ∑_{m=0}^{⌊(n−1)/2⌋} \binom{n − 1 − m}{m}(2(e + f))^{n−1−2m} (−f(2e + f))^{m} .

Next, replace e by e/2 to get that

(f + e)^{n} = f^{n} + e ∑_{m=0}^{⌊(n−1)/2⌋} \binom{n − 1 − m}{m}(e + 2f)^{n−1−2m} (−f(e + f))^{m} .  (14)

Finally, set f = 1, expand both sides of Equation 14 and compare coefficients of like powers of e to get the result. □

5. Commutating Matrices I

As before, let

A = (\begin{matrix}a & b \\ c & d \end{matrix}) .

We write

A = (mA + w I) + ((1 − m)A − w I),  (15)

noting that the matrices on the right commute.

A^{n} = ∑_{j=0}^{n} \binom{n}{j}(mA + w I)^{n−j}((1 − m)A − w I)^{j}  (16)

and we might hope to use the formulae at (1) and (6) to derive new identities. We give two examples.

Proposition 2 Let n ∈ ℕ and k, r integers with 0 ≤ k ≤ r ≤ n. Then

(−1)^{n−k} ∑_{j=0}^{n−k} \binom{n}{j}\binom{n − j}{k}\binom{j}{r − k}(−1)^{j} = \begin{cases}\binom{n}{k}, & r = n, \\ 0, & r ≠ n. \end{cases}  (17)

Proof. Expand the right side of Equation 16 and re-index to get that

A^{n} = ∑_{r=0}^{n} w^{n−r}A^{r}(1 − m)^{r}(−1)^{r} ∑_{k=0}^{n} (\frac{m}{1 − m})^{k} (−1)^{k}

× ∑_{j=0}^{n−k} \binom{n}{j}\binom{n − j}{k}\binom{j}{r − k}(−1)^{j}.

If we compare coefficients of w on both sides, it is clear that

∑_{k=0}^{n} (\frac{m}{1 − m})^{k} (−1)^{k} ∑_{j=0}^{n−k} \binom{n}{j}\binom{n − j}{k}\binom{j}{r − k}(−1)^{j} = \begin{cases}(m − 1)^{−n}, & r = n, \\ 0, & r ≠ n. \end{cases}

Equivalently,

∑_{k=0}^{n} m^{k}(1 − m)^{n−k}(−1)^{n−k} ∑_{j=0}^{n−k} \binom{n}{j}\binom{n − j}{k}\binom{j}{r − k}(−1)^{j} = \begin{cases}1, & r = n, \\ 0, & r ≠ n. \end{cases}

Finally, equating coefficients of powers of m on both sides of the last equality give the result. We note that the case for r = n follows since the left side then must equal (m + (1 − m))^{n}. □

Proposition 3 Let n ∈ ℕ and t an integer such that 0 ≤ t ≤ n. For each integer i ∈ [0, ⌊(n − 1)/2⌋],

∑_{j=1}^{n} ∑_{r=i}^{⌊(j−1)/2⌋} ∑_{k=0}^{j−1−2r} \binom{n}{j}\binom{j − 1 − r}{r}\binom{j − 1 − 2r}{k}\binom{r}{i}  (18)

× \binom{r − i}{j − k − r + i − n + t}(−1)^{r+t+j+n+i}2^{k} = \begin{cases}\binom{n−1−i}{i}, & t = 0, \\ 0, & t ≠ 0. \end{cases}

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A19 8

Proof. We set m = 0 in Equations 15 and 16, so that

(\begin{matrix}a & b \\ c & d \end{matrix})^{n} = ∑_{j=0}^{n} \binom{n}{j}w^{n−j} (\begin{matrix}a − w & b \\ c & d − w \end{matrix})^{j} .

If we use Theorem 1 and compare values in the (1, 2) position, we deduce that

∑_{i=0}^{⌊(n−1)/2⌋} \binom{n − 1 − i}{i}(a + d)^{n−1−2i}(bc − ad)^{i} =

∑_{j=1}^{n} \binom{n}{j}w^{n−j} ∑_{r=0}^{⌊(j−1)/2⌋} \binom{j − 1 − r}{r}(a + d − 2w)^{j−1−2r}(bc − (a − w)(d − w))^{r}. (19)

For ease of notation we replace a + d by T and ad − bc by D. If we then expand the right side and collect powers of w, we get that

∑_{i=0}^{⌊(n−1)/2⌋} \binom{n − 1 − i}{i}T^{n−1−2i}(−D)^{i} =

∑_{j=1}^{n} ∑_{r=0}^{⌊(j−1)/2⌋} ∑_{k=0}^{j−1−2r} ∑_{m=0}^{r} ∑_{p=0}^{m} \binom{n}{j}\binom{j − 1 − r}{r}\binom{j − 1 − 2r}{k}\binom{r}{m}\binom{m}{p}

× (−1)^{k+r−m+p}2^{k}T^{j−1−2r−k+m−p}D^{r−m}w^{n−j+k+m+p}.

If we solve t = n − j + k + m + p for p, we have that

∑_{i=0}^{⌊(n−1)/2⌋}\binom{n − 1 − i}{i}T^{n−1−2i}(−D)^{i}

= ∑_{t=0}^{n−1} w^{t} ∑_{j=1}^{n} ∑_{r=0}^{⌊(j−1)/2⌋} ∑_{k=0}^{j−1−2r} ∑_{m=0}^{r} \binom{n}{j}\binom{j − 1 − r}{r}\binom{j − 1 − 2r}{k}\binom{r}{m}

× \binom{m}{j − k − m − n + t}(−1)^{r+t+j+n}2^{k}T^{2m+n−t−2r−1}D^{r−m}.

Next, cancel a factor of T^{n−1} from both sides, replace T by 1/y, D by −x/y^{2} and m by r − i to get that

∑_{i=0}^{⌊(n−1)/2⌋}\binom{n − 1 − i}{i}x^{i}

= ∑_{t=0}^{n−1}(wy)^{t} ∑_{j=1}^{n} ∑_{r=0}^{⌊(j−1)/2⌋} ∑_{k=0}^{j−1−2r} ∑_{i=0}^{r} \binom{n}{j}\binom{j − 1 − r}{r}\binom{j − 1 − 2r}{k}\binom{r}{r − i}

× \binom{r − i}{j − k − r + i − n + t}(−1)^{r+t+j+n+i}2^{k}x^{i}

= ∑_{t=0}^{n−1}(wy)^{t} ∑_{i=0}^{⌊(n−1)/2⌋} ∑_{j=1}^{n} ∑_{r=i}^{⌊(j−1)/2⌋} ∑_{k=0}^{j−1−2r} \binom{n}{j}\binom{j − 1 − r}{r}\binom{j − 1 − 2r}{k}\binom{r}{i}

× \binom{r − i}{j − k − r + i − n + t}(−1)^{r+t+j+n+i}2^{k}x^{i}

Finally, compare coefficients of x^{i}(wy)^{t} to get the result. □

Corollary 2 For every complex number w different from 0, 1/2, ϕ (the golden ratio) or −1/ϕ,

F_{n} = ∑_{j=1}^{n} ∑_{r=0}^{⌊(j−1)/2⌋} \binom{n}{j}\binom{j − 1 − r}{r}w^{n−j}(1 − 2w)^{j−1−2r}(1 + w − w^{2})^{r}.  (20)

Proof. Let a = b = c = 1, d = 0 in Equation 19 and once again use the identity at (10). □

This identity contains several of the known identities for the Fibonacci sequence as special cases. For example, letting w → ϕ gives Binet’s Formula (after summing using the Binomial Theorem); w → 0 gives the formula at (10); w → 1/2 gives (5); w = 1 gives the identity

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

which is a special case of Formula 46 from Vajda’s list ([9], page 179).

6. Commutating Matrices II

Let A = (\begin{matrix}a & b \\ c & d \end{matrix}) with T = a + d and D = ad − bc and I the 2 × 2 identity matrix as

before. Let g be an arbitrary real or complex number such that g^{2} + T g + D ≠ 0. It is easy to check that

A = \frac{1}{g^{2} + T g + D}(A + g I)(g A + D I),  (21)

and that A + g I and g A + D I commute. If both sides of Equation 21 are now raised to the n-th power, the right side expanded via the Binomial Theorem and powers of A collected, we get the following proposition:

Proposition 4 Let A be an arbitrary 2 × 2 matrix with trace T and determinant D ≠ 0. Let g be a complex number such that g^{2} + T g + D ≠ 0, g ≠ 0 and let n be a positive integer. Then

A^{n} = (\frac{g D}{g^{2} + T g + D})^{n} ∑_{r=0}^{2n} ∑_{i=0}^{r} \binom{n}{i}\binom{n}{r − i} (\frac{D}{g^{2}} )^{i} (\frac{g}{D})^{r} A^{r}.  (22)

Corollary 3 Let n be a positive integer and let m be an integer with 0 ≤ m ≤ 2n. Then for −n ≤ w ≤ n,

∑_{k=0}^{n−1} \binom{n − 1 − k}{k}\binom{n}{w + k}\binom{k + w}{m − k − w}(−1)^{k} =

∑_{k=−2w−n+m+1}^{m−w} \binom{n}{k + w}\binom{n}{n + k + w − m}\binom{k + n + 2w − m − 1}{k}(−1)^{k}. (23)

Remark: Consideration of the binomial coefficients on either side of (23) shows that this identity is non-trivial only for m/2 − ⌊(n − 1)/2⌋ ≤ w ≤ m, but we prefer to state the limits on w as we have done for neatness reasons. Proof. If Equation 22 is multiplied by (g^{2} + T g + D)^{n}, both sides expanded and coefficients of like powers of g compared, we get that for each integer m ∈ [0, 2n],

A^{n} ∑_{j=0}^{n} \binom{n}{j}\binom{j}{m − j}D^{n−j}T^{2j−m} =

∑_{r=0}^{2n} \frac{1 + (−1)^{r+m+n}}{2} \binom{n}{\frac{r−m+n}{2}}\binom{n}{\frac{r+m−n}{2}}D^{(3n−r−m)/2}A^{r}. (24)

If we next assume that (1, 2) entry of A is non-zero, apply Theorem 1 to the various powers of A on each side of Equation 24 and compare the (1, 2) entries on each side of (24), we get that

∑_{k=0}^{⌊(n−1)/2⌋} \binom{n − 1 − k}{k}T^{n−1−2k}(−D)^{k} ∑_{j=0}^{n} \binom{n}{j}\binom{j}{m − j}D^{n−j}T^{2j−m} =

∑_{r=0}^{2n} \frac{1 + (−1)^{r+m+n}}{2} \binom{n}{\frac{r−m+n}{2}}\binom{n}{\frac{r+m−n}{2}}D^{(3n−r−m)/2} ∑_{k=0}^{⌊ \frac{r−1}{2} ⌋} \binom{r − 1 − k}{k}T^{r−1−2k}(−D)^{k}. (25)

Equivalently, after re-indexing and changing the order of summation,

∑_{v=0}^{2n} ∑_{k=0}^{n} \binom{n − 1 − k}{k}\binom{n}{k + n − v}\binom{k + n − v}{m − k − n + v}(−1)^{k} (\frac{D}{T^{2}} )^{v}

= ∑_{v=0}^{2n} ∑_{k=2v−3n+m+1}^{v+m−n} \binom{n}{k − v + n}\binom{n}{k − v + 2n − m}

× \binom{k − 2v + 3n − m − 1}{k}(−1)^{k} (\frac{D}{T^{2}} )^{v} . (26)

The result follows from comparing coefficients of equal powers of D/T^{2} and replacing v by n − w. □

Corollary 4 Let n be a positive integer and let m ∈ {0, 1 …, 2n}. Then

∑_{j=0}^{n} \binom{n}{j}\binom{j}{m − j}2^{2j−m} = ∑_{\begin{matrix}r=0, \\ r+m+n even \end{matrix}}^{2n} \binom{n}{\frac{r−m+n}{2}}\binom{n}{\frac{r+m−n}{2}},  (27)

(n + 1) ∑_{j=0}^{n} \binom{n}{j}\binom{j}{m − j}2^{2j−m} = ∑_{\begin{matrix}r=0, \\ r+m+n even \end{matrix}}^{2n} \binom{n}{\frac{r−m+n}{2}}\binom{n}{\frac{r+m−n}{2}}(r + 1), (28)

(2^{n+1} − 1) ∑_{j=0}^{n} \binom{n}{j}\binom{j}{m − j}2^{n−j}3^{2j−m} =

∑_{\begin{matrix}r=0, \\ r+m+n even \end{matrix}}^{2n} \binom{n}{\frac{r−m+n}{2}}\binom{n}{\frac{r+m−n}{2}}2^{(3n−r−m)/2}(2^{r+1} − 1), (29)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A19 12

and

F_{n+2} ∑_{j=0}^{n} \binom{n}{j}\binom{j}{m − j}(−1)^{m+j} = ∑_{\begin{matrix}r=0, \\ r+m+n even \end{matrix}}^{2n} \binom{n}{\frac{r−m+n}{2}}\binom{n}{\frac{r+m−n}{2}}(−1)^{(−n+r−m)/2}F_{r+2}. (30)

Proof. Equations (27) to (30) follow from comparing (1, 1) entries at (24), using, respectively, the following identities:

I^{n} = I,
(\begin{matrix}2 & 1 \\ −1 & 0 \end{matrix})^{n} = (\begin{matrix}n + 1 & n \\ −n & −n + 1 \end{matrix}) ,
(\begin{matrix}3 & 1 \\ −2 & 0 \end{matrix})^{n} = (\begin{matrix}2^{n+1} − 1 & 2^{n} − 1 \\ −2^{n+1} + 2 & −2^{n} + 2 \end{matrix}) ,
(\begin{matrix}−2 & −1 \\ 1 & 1 \end{matrix})^{n} = (−1)^{n} (\begin{matrix}F_{n+2} & F_{n} \\ −F_{n} & −F_{n−2} \end{matrix}) .
□

Corollary 5 If g is a complex number different from 0, −ϕ or 1/ϕ, then

F_{n} = (\frac{−g}{g^{2} + g − 1})^{n} ∑_{r=0}^{2n} ∑_{i=0}^{r} \binom{n}{i}\binom{n}{r − i} (−1)^{r+i} g^{r−2i}F_{r}.  (31)

Proof. Let A = (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}) and compare the (1, 2) entries on each side of Equation 22, using (4). □

7. Miscellaneous identities derived from particular matrices The identities in Corollary 4 derived from the fact that the n-th power of each of the various matrices mentioned in the proof has a simple, elegant form. It is of course easy to construct such 2 × 2 matrices whose n-th power has a similar “nice” form by constructing matrices (\begin{matrix}a & b \\ c & d \end{matrix}) with a predetermined pair of eigenvalues α and β and using the formula of Williams at (1). Theorem 1 can then be applied to any such matrix to produce identities of the form

∑_{i=0}^{⌊(n−1)/2⌋} \binom{n − 1 − i}{i}(a + d)^{n−1−2i}(−(ad − bc))^{i} = \begin{cases}\frac{α^{n}−β^{n}}{α−β} , if α ≠ β, \\ nα^{n−1}, if α = β. \end{cases}

As an example, the matrix (\begin{matrix}2 & 1 \\ −1 & 0 \end{matrix}) has both eigenvalues equal to 1, leading to the following identity for n ≥ 1:

n = ∑_{i=0}^{⌊(n−1)/2⌋} \binom{n − 1 − i}{i}2^{n−1−2i}(−1)^{i}.  (32)

We give one additional example.

Proposition 5 Let n be a positive integer, and s an integer with 0 ≤ s ≤ n − 1. Then

∑_{k≥0} \binom{s}{k}\binom{n − k − 1}{s − 1}(−1)^{k} = 0.  (33)

Proof. We consider (\begin{matrix}i & 0 \\ 0 & j \end{matrix})^{n} and use Theorem 1 to get that

i^{n} = ∑_{k=0}^{⌊n/2⌋} \binom{n − k}{k}(i + j)^{n−2k}(−i j)^{k} − j ∑_{k=0}^{⌊(n−1)/2⌋} \binom{n − 1 − k}{k}(i + j)^{n−1−2k}(−i j)^{k}.

Upon expanding powers of i + j and re-indexing, we get that

i^{n} = i^{n} + ∑_{s=0}^{n−1} i^{s}j^{n−s} ∑_{k} \{\binom{n − k}{k}\binom{n − 2k}{s − k} − \binom{n − 1 − k}{k}\binom{n − 1 − 2k}{s − k}\} (−1)^{k}. (34)

Finally, we note that

\binom{n − k}{k}\binom{n − 2k}{s − k} − \binom{n − 1 − k}{k}\binom{n − 1 − 2k}{s − k} = \binom{s}{k}\binom{n − k − 1}{s − 1}

and compare coefficients of i^{s}j^{n−s} on both sides of (34) to get the result. □

8. Concluding remarks

Theorem 1 can be applied in a number of other ways. The identity

(\begin{matrix}cos nθ & sin nθ \\ − sin nθ & cos nθ \end{matrix}) = (\begin{matrix}cos θ & sin θ \\ − sin θ & cos θ \end{matrix})^{n}

will give alternative (to those derived from De Moivre’s Theorem) expressions for cos nθ and sin nθ.

If (x_{n}, y_{n}) denotes the n-th largest pair of positive integers satisfying the Pell equation x^{2} − my^{2} = 1, the identity

(\begin{matrix}x_{n} & m y_{n} \\ y_{n} & x_{n} \end{matrix}) = (\begin{matrix}x_{1} & m y_{1} \\ y_{1} & x_{1} \end{matrix})^{n}

will give alternative expressions for x_{n} and y_{n} to those derived from the formula x_{n} + \sqrt{m}y_{n} = (x_{1} + \sqrt{m}y_{1})^{n}.

Similarly, one can use Theorem 1 to find various identities for the Brahmagupta polynomials [8] x_{n} and y_{n} defined by

(\begin{matrix}x_{n} & y_{n} \\ t y_{n} & x_{n} \end{matrix}) = (\begin{matrix}x_{1} & y_{1} \\ t y_{1} & x_{1} \end{matrix})^{n}

and the Morgan-Voyce polynomials [5] B_{n} and b_{n} defined by

(\begin{matrix}B_{n} & −B_{n−1} \\ B_{n−1} & −B_{n−2} \end{matrix}) = (\begin{matrix}x + 2 & −1 \\ 1 & 0 \end{matrix})^{n}

and b_{n} = B_{n} − B_{n−1}.

It may be possible to extend some of the methods used in this paper to develop new combinatorial identities. For example, it may be possible to exploit the equation

A = (m_{1}A + w_{1}I) + (m_{2}A + w_{2}I) + ((1 − m_{1} − m_{2})A − (w_{1} + w_{2})I)

or, more generally, the equation

A = ∑_{i=1}^{p}(m_{i}A + w_{i}I) + ((1 − ∑_{i=1}^{p} m_{i}) A − ∑_{i=1}^{p} w_{i}I)

to find new combinatorial identities in a way similar to the use of Equation 15 in the section Commuting Matrices I. We hope to explore some of these ideas in a later paper.

References

[1] P. J. Blatz, On the Arbitrary Power of an Arbitrary (2 × 2)-Matrix (in Brief Versions). The American Mathematical Monthly, Vol. 75, No. 1. (Jan., 1968), pp. 57-58.

[2] H. W. Gould, A history of the Fibonacci Q-matrix and a higher-dimensional problem. Fibonacci Quart. 19 (1981), no. 3, 250–257.

[3] E. Jacobsthal, Fibonaccische Polynome und Kreistheilungsgleichungen. Sitzungsberischte der berliner Math. Gesellschaft, 17, (1919–20), 43–47.

[4] R. C. Johnson, Matrix methods for Fibonacci and related sequences.

http:// maths.dur.ac.uk/ dma0rcj/PED/fib.pdf, (August 2003).

[5] A. M. Morgan-Voyce, Ladder Network Analysis Using Fibonacci Numbers. IRE Trans. Circuit Th. CT-6, 321-322, Sep. 1959.

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

[7] Hans Schwerdtfeger, Geometry of complex numbers. Mathematical Expositions, No. 13 University of Toronto Press, Toronto 1962 xi+186 pp.

[8] E. R. Suryanarayan, The Brahmagupta Polynomials. Fib. Quart. 34, 30-39, 1996.

[9] S. Vajda, Fibonacci & Lucas numbers, and the golden section. Theory and applications. Ellis Horwood Series: Mathematics and its Applications. Ellis Horwood Ltd., Chichester; Halsted Press [John Wiley & Sons, Inc.], New York, 1989. 190 pp.

[10] N. N. Vorob’ev, Fibonacci numbers. Translated from the Russian by Halina Moss; translation editor Ian N. Sneddon Blaisdell Publishing Co. (a division of Random House), New York-London 1961 viii+66 pp.

[11] Kenneth S. Williams, The nth Power of a 2 × 2 Matrix (in Notes). Mathematics Magazine, Vol. 65, No. 5. (Dec., 1992), p. 336.