Determinants Containing Powers of Generalized Fibonacci Numbers

Aram Tangboonduangjit and Thotsaporn Thanatipanonda Mahidol University International College Nakhonpathom 73170 Thailand

                aram.tan@mahidol.ac.th
             thotsaporn.tha@mahidol.ac.th

Abstract

We study the determinants of matrices whose entries are powers of the Fibonacci numbers. We then extend the results to include entries that are powers of a secondorder linear recurrence relation. These results motivate a fundamental identity of determinants whose entries are powers of linear polynomials. Finally, we discuss the determinants of matrices whose entries are products of the general second-order linear recurrence relations.

1 Introduction

In the first issue of the Fibonacci Quarterly, Alfred posed the following problem [1]:

Prove

|\begin{matrix}F_{n}^{2} & F_{n+1}^{2} & F_{n+2}^{2} \\ F_{n+1}^{2} & F_{n+2}^{2} & F_{n+3}^{2} \\ F_{n+2}^{2} & F_{n+3}^{2} & F_{n+4}^{2} \end{matrix}| = 2(−1)^{n+1},

where F_{n} is the nth Fibonacci number.

In the second volume of the Fibonacci Quarterly, Parker [7] posed a similar problem with the exponent of each entry changed to 4 and the dimension of the matrix changed to 5 × 5. These two results naturally suggest the following question: what would be the determinant of an analogous form where the dimension of the matrix and the exponent of each entry are arbitrary? Carlitz [4] answered this question by showing that the determinant of the form D(r, n) =|F_{n+i+j}^{r}|, where i, j = 0, 1, …, r, is given by

D(r, n) = (−1)^{(n+1)\binom{r+1}{2}}(F_{1}^{r}F_{2}^{r−1} ⋯ F_{r})^{2} · ∏_{i=0}^{r} \binom{r}{i}.  (1)

In this paper we generalize the entries even further by considering the determinant of the form D(r, s, k, n) =|F_{s+k(n+i+j)}^{r}|, where i, j = 0, 1, …, r. We show that

D(r, s, k, n) = (−1)^{(s+kn+1)\binom{r+1}{2}}(F_{k}^{r}F_{2k}^{r−1} ⋯ F_{rk})^{2} · ∏_{i=0}^{r} \binom{r}{i}.  (2)

Carlitz based his proof of formula (1) on the Binet form of the Fibonacci numbers; whereas we employ the matrix methods, such as the factorization method of Krattenthaler, to prove formula (2). In addition, we require a generalized form of the Catalan identity, proved by Melham and Shannon [6]. In Section 2, we present an alternative proof of the generalized Catalan identity using a matrix representation of the sequence and the properties of the matrix multiplication. In Section 3, we then present the proof of formula (2) as a special case of the determinant with entries involving the powers of the numbers in a second-order linear recurrence with constant coefficients. In the last section, we present the determinant whose entries are the products of the numbers defined as a second-order linear recurrence with constant coefficients using the Desnanot-Jacobi identity. The methodology used for this work relies on a computer programming developed by the second author [8].

2 Generalized Catalan identity

The well-known Catalan identity states that for all nonnegative integers s and i,

F_{s+i}^{2} − F_{s}F_{s+2i} = (−1)^{s}F_{i}^{2}.

A generalization of this identity useful for this work is given by Melham and Shannon [6]. We shall, however, present an alternative proof of this generalization. For integers a, b, c_{1}, and c_{2} with c_{2} ≠ 0, let W_{n} = W_{n}(a, b; c_{1}, c_{2}) denote the second-order linear recurrence with constant coefficients, defined by

W_{0} = a, W_{1} = b and W_{n} = c_{1}W_{n−1} + c_{2}W_{n−2} for n ≥ 2.

With this notation, the Fibonacci sequence (F_{n}) and the Lucas sequence (U_{n}) correspond to F_{n} = W_{n}(0, 1; 1, 1) and U_{n} = W_{n}(0, 1; c_{1}, c_{2}), respectively. Moreover, we can use this recurrence to extend the definition of a sequence to the terms with negative indices. Usually, we can explicitly find the relationship between the negative-indexed terms and the positiveindexed terms. For example, for the Fibonacci sequence and the Lucas sequence, we have

F_{−n} = (−1)^{n+1}F_{n} and U_{−n} = (−1)^{n+1}c_{2}^{−n}U_{n} for n ≥ 1.

Proposition 1 (Generalized Catalan Identity). Let W_{n} = W_{n}(a_{0}, a_{1}; c_{1}, c_{2}) and Y_{n} = W_{n}(b_{0}, b_{1}; c_{1}, c_{2}) be second-order linear recurrences. Then

W_{s+i}Y_{s+j} − W_{s}Y_{s+i+j} = (−c_{2})^{s}(W_{1}Y_{j} − W_{0}Y_{j+1}) · U_{i},  (3)

for all integers s, j, and i.

Proof. The proof is by induction on i. For the case when i = 0, the identity is trivial. For the case when i = 1, we have

(\begin{matrix}W_{s+1} & Y_{s+j+1} \\ W_{s} & Y_{s+j} \end{matrix}) = (\begin{matrix}c_{1} & c_{2} \\ 1 & 0 \end{matrix}) (\begin{matrix}W_{s} & Y_{s+j} \\ W_{s−1} & Y_{s+j−1} \end{matrix}) = (\begin{matrix}c_{1} & c_{2} \\ 1 & 0 \end{matrix})^{s} (\begin{matrix}W_{1} & Y_{j+1} \\ W_{0} & Y_{j} \end{matrix}) for s ≥ 0,

and

(\begin{matrix}W_{s+1} & Y_{s+j+1} \\ W_{s} & Y_{s+j} \end{matrix}) = (\begin{matrix}c_{1} & c_{2} \\ 1 & 0 \end{matrix})^{−1} (\begin{matrix}W_{s+2} & Y_{s+j+2} \\ W_{s+1} & Y_{s+j+1} \end{matrix}) = (\begin{matrix}c_{1} & c_{2} \\ 1 & 0 \end{matrix})^{s} (\begin{matrix}W_{1} & Y_{j+1} \\ W_{0} & Y_{j} \end{matrix}) for s < 0,

where the second equality in both equations follows from repeated application of the matrix representation in the first equality. Taking the determinant of both sides of any one equation yields

W_{s+1}Y_{s+j} − W_{s}Y_{s+j+1} = (−c_{2})^{s}(W_{1}Y_{j} − W_{0}Y_{j+1}).  (4)

Now, consider two cases.

Case i > 1: Assume that the identity holds for some integers i − 1 and i − 2. Then

W_{s+i}Y_{s+j} − W_{s}Y_{s+i+j} = |\begin{matrix}W_{s+i} & Y_{s+i+j} \\ W_{s} & Y_{s+j} \end{matrix}|

= |\begin{matrix}c_{1}W_{s+(i−1)} + c_{2}W_{s+(i−2)} & c_{1}Y_{s+(i−1)+j} + c_{2}Y_{s+(i−2)+j} \\ W_{s} & Y_{s+j} \end{matrix}|

= c_{1} |\begin{matrix}W_{s+(i−1)} & Y_{s+(i−1)+j} \\ W_{s} & Y_{s+j} \end{matrix}| + c_{2} |\begin{matrix}W_{s+(i−2)} & Y_{s+(i−2)+j} \\ W_{s} & Y_{s+j} \end{matrix}|

= (−c_{2})^{s}(W_{1}Y_{j} − W_{0}Y_{j+1})(c_{1}U_{i−1} + c_{2}U_{i−2})

= (−c_{2})^{s}(W_{1}Y_{j} − W_{0}Y_{j+1})U_{i}, Case i < 0: Assume that the identity holds for some integers i + 1 and i + 2. Then

W_{s+i}Y_{s+j} − W_{s}Y_{s+i+j} = |\begin{matrix}W_{s+i} & Y_{s+i+j} \\ W_{s} & Y_{s+j} \end{matrix}|

= |\begin{matrix}\frac{−c_{1}}{c_{2}} W_{s+(i+1)} + \frac{1}{c_{2}} W_{s+(i+2)} & \frac{−c_{1}}{c_{2}} Y_{s+(i+1)+j} + \frac{1}{c_{2}} Y_{s+(i+2)+j} \\ W_{s} & Y_{s+j} \end{matrix}|

= \frac{−c_{1}}{c_{2}} |\begin{matrix}W_{s+(i+1)} & Y_{s+(i+1)+j} \\ W_{s} & Y_{s+j} \end{matrix}| + \frac{1}{c_{2}} |\begin{matrix}W_{s+(i+2)} & Y_{s+(i+2)+j} \\ W_{s} & Y_{s+j} \end{matrix}|

= (−c_{2})^{s}(W_{1}Y_{j} − W_{0}Y_{j+1})(\frac{−c_{1}}{c_{2}} U_{i+1} + \frac{1}{c_{2}} U_{i+2})

= (−c_{2})^{s}(W_{1}Y_{j} − W_{0}Y_{j+1})U_{i},

where we apply the induction hypothesis in the penultimate equality in both cases. Hence, the proof is complete.

We note some special cases of Proposition 1 useful in later sections:

U_{s+i}U_{s+j} − U_{s}U_{s+i+j} = (−c_{2})^{s} · U_{i}U_{j},  (5)
U_{s+i}W_{s+j} − U_{s}W_{s+i+j} = (−c_{2})^{s} · U_{i}W_{j},  (6)

and

W_{s+i}W_{s+j} − W_{s}W_{s+i+j} = (−c_{2})^{s} · (W_{1}W_{j} − W_{0}W_{j+1})U_{i} = (−c_{2})^{s} · Δ · U_{i}U_{j},  (7)

where Δ = |\begin{matrix}W_{1} & W_{2} \\ W_{0} & W_{1} \end{matrix}| = a_{1}^{2} − c_{1}a_{0}a_{1} − c_{2}a_{0}^{2}.

We justify the second equality of (7) by applying Proposition 1 as follows: In (3), let Y_{n} = W_{n}, substitute j = 1 and s = 0, respectively, and rename the index i by j.

The identity (7) can be restated as follows:

Corollary 2. Let k, n, r, s, and t be integers. Then

W_{s+k(n+t)} = A(t)W_{s+kn} + B(t)U_{s+k(n+r)},  (8)

where A(t) = \frac{W_{k(t−r)}}{W_{−kr}} and B(t) = \frac{−(−c_{2})^{−kr} · Δ · U_{kt}}{W_{−kr}}.

Proof. Let integers k′, n′, r′, s′, and t′ be given. Applying (7) with s = −k′r′, i = k′t′, and j = s′ + k′(n′ + r′), we have

W_{−k′r′}W_{s′+k′(n′+t′)} = W_{k′(t′−r′)}W_{s′+k′n′} − (−c_{2})^{−k′r′} · Δ · U_{k′t′}U_{s′+k′(n′+r′)}.

Dividing by W_{−k′r′} on both sides and renaming the variables yield the identity (8), as required.

3 Determinants involving powers of terms of secondorder recurrence

Our goal in this section is to give the closed form of the determinant of the (r + 1) × (r + 1) matrix whose entries are W_{s+k(n+i+j)}^{r}, where i, j = 0, 1, …, r, and s and k are any integers. This matrix is

𝔸_{n}^{s,k}(r) = (\begin{matrix}W_{s+kn}^{r} & W_{s+k(n+1)}^{r} & ⋯ & W_{s+k(n+r)}^{r} \\ W_{s+k(n+1)}^{r} & W_{s+k(n+2)}^{r} & ⋯ & W_{s+k(n+r+1)}^{r} \\ ⋮ & ⋮ & ... & ⋮ \\ W_{s+k(n+r)}^{r} & W_{s+k(n+r+1)}^{r} & ⋯ & W_{s+k(n+2r)}^{r} \end{matrix}) .  (9)

We begin with the following proposition on the determinant whose entries are some power of linear polynomials.

Lemma 3. Let c_{0}, …, c_{r} and x_{0}, …, x_{r} be real numbers. Then

det((c_{j}x_{i} + 1)^{r})_{0≤i,j≤r} = ∏_{0≤i<j≤r}(x_{i} − x_{j}) ∏_{0≤i<j≤r}(c_{i} − c_{j}) ∏_{i=0}^{r} \binom{r}{i}.  (10)

Proof. We prove Lemma 3 by using the factorization method [5]. The determinant will be 0 if x_{0} is replaced by any x_{i} for 0 < i ≤ r, since some two rows of the matrix would be equal. This implies that (x_{0} − x_{i}) is a factor of the determinant for each i = 1, 2, …, r. Similarly, we have that (x_{1} − x_{i}) is a factor of the determinant for each i = 2, …, r, and so on. In a similar manner, we see that if c_{0} is replaced by any c_{j} for 0 < j ≤ r, then two columns of the matrix will be the same yielding the zero determinant. This implies that (c_{0} − c_{j}) is a factor of the determinant for each j = 1, 2, …, r. Similarly, we have that (c_{1} − c_{j}) is a factor of the determinant for each j = 2, …, r, and so on. Therefore

∏_{0≤i<j≤r}(x_{i} − x_{j}) ∏_{0≤i<j≤r}(c_{i} − c_{j})  (11)

is a factor of this determinant. As a function of x_{i} for some fixed i or a function of c_{j} for some fixed j the determinant is a polynomial of degree r. This implies that the factor (11) and the required determinant have the same degree. Therefore, we can write the determinant as

det((c_{j}x_{i} + 1)^{r})_{0≤i,j≤r} = C ∏_{0≤i<j≤r}(x_{i} − x_{j}) ∏_{0≤i<j≤r}(c_{i} − c_{j}),

for some constant C. To find C, we compare on both sides the coefficients of the monomial

(c_{r}x_{r})^{r}(c_{r−1}x_{r−1})^{r−1} ⋯ (c_{0}x_{0})^{0}.  (12)

On the right-hand side, the monomial (12) appears as

∏_{0<i<j≤r}(−x_{j})(−c_{j}) = ∏_{0<i<j≤r} x_{j}c_{j}.

Hence, the coefficient of the monomial (12) on the right-hand side is just equal to C. We see that for each 0 ≤ i ≤ r, the term (c_{i}x_{i})^{i} appears in (c_{i}x_{i} + 1)^{r}. Hence, on the left-hand side, the monomial (12) appears as

± ∏_{0≤i≤r}(c_{i}x_{i} + 1)^{r}.

By the definition of the determinant, the sign in front of the expression is determined by the parity of the identity permutation (0)(1) ⋯ (r). Since (0)(1) ⋯ (r) = (01)(01), it follows that the identity permutation is even. Hence, the sign is determined to be +. Since, for each 0 ≤ i ≤ r, the coefficient of (c_{i}x_{i})^{i} in (c_{i}x_{i} + 1)^{r} is \binom{r}{i}, it follows that

C = ∏_{i=0}^{r} \binom{r}{i}.

This completes the proof of Lemma 3.

Corollary 4. Let A(j), B(j), X_{i}, Y_{i} be real numbers for 0 ≤ i, j ≤ r. Then

det((A(j)X_{i} + B(j)Y_{i})^{r})_{0≤i,j≤r}

= ∏_{0≤i<j≤r}(X_{i}Y_{j} − X_{j}Y_{i}) ∏_{0≤i<j≤r}(A(i)B(j) − A(j)B(i)) ∏_{i=0}^{r} \binom{r}{i}. (13)

Proof. We prove in the case of B(j) ≠ 0 and Y_{i} ≠ 0 for all 0 ≤ i, j ≤ r. Applying Lemma 3 with c_{j} = A(j)/B(j) and x_{i} = X_{i}/Y_{i} for all 0 ≤ i, j ≤ r and clearing the denominators, we obtain (13). The proof of the other case when some of B(j) or Y_{i} are 0 follows from the fact that the determinant with polynomial entries is a continuous function.

Thus, this allows us to prove one of the main results of this paper.

Theorem 5. The determinant of the matrix 𝔸_{n}^{s,k}(r) is given by

det 𝔸_{n}^{s,k}(r) = (−1)^{(s+kn+1)\binom{r+1}{2}} · c_{2}^{(s+kn)\binom{r+1}{2}+2k\binom{r+1}{3}} · Δ^{\binom{r+1}{2}} · ∏_{i=0}^{r} \binom{r}{i}U_{(i+1)k}^{2(r−i)}.

Proof. By (9), (8), (13), and (6) respectively, we have det 𝔸_{n}^{s,k}(r) = det(W_{s+k(n+i+j)}^{r})_{0≤i,j≤r} = det((A(j)W_{s+k(n+i)} + B(j)U_{s+k(n+r+i)})^{r})_{0≤i,j≤r}

= ∏_{0≤i<j≤r}(W_{s+k(n+i)}U_{s+k(n+r+j)} − W_{s+k(n+j)}U_{s+k(n+r+i)}) ∏_{0≤i<j≤r} (A(i)B(j) − A(j)B(i)) ∏_{i=0}^{r} \binom{r}{i}

= ∏_{0≤i<j≤r}((−c_{2})^{s+k(n+r+i)}U_{k(j−i)}W_{−kr}) ∏_{0≤i<j≤r} (\frac{−Δ · (−c_{2})^{−kr}}{W_{−kr}^{2}} (−c_{2})^{ki}U_{k(j−i)}W_{−kr}) ∏_{i=0}^{r} \binom{r}{i}

= ∏_{0≤i<j≤r} (−Δ · (−c_{2})^{s+k(n+2i)}U_{k(j−i)}^{2}) ∏_{i=0}^{r} \binom{r}{i},

Rearranging the last expression allows us to obtain the desired identity. Remark 6. By letting W_{n} = F_{n} in Theorem 5 and noting that for the Fibonacci sequence c_{2} = 1 and Δ = 1, we then derive (2).

4 Determinants involving products of terms of second-

order recurrence

The following lemma was mentioned by Krattenthaler [5] as part of the factorization method. We provide a different proof of this lemma using the Desnanot-Jacobi identity [3]. Lemma 7. Let X_{0}, …, X_{r}, D_{1}, …, D_{r}, and E_{1}, …, E_{r} be indeterminates. Then

det ( ∏_{ℓ=j+1}^{r}(X_{i} + D_{ℓ}) · ∏_{m=1}^{j}(X_{i} + E_{m}))_{0≤i,j≤r} = ∏_{0≤i<j≤r}(X_{j} − X_{i}) · ∏_{1≤i≤j≤r}(D_{j} − E_{i}).

An alternative way of writing this identity would be

det ( ∏_{ℓ=j+1}^{r}(A(d_{ℓ})X_{i} + B(e_{ℓ})Y_{i}) · ∏_{m=1}^{j}(A(e_{m})X_{i} + B(e_{m})Y_{i}))_{0≤i,j≤r}

= ∏_{0≤i<j≤r}(X_{i}Y_{j} − X_{j}Y_{i}) ∏_{1≤i≤j≤r}(B(e_{i})A(d_{j}) − A(e_{i})B(d_{j})). (14)

The main result of this section is as follows:

Theorem 8. Let d_{1}, …, d_{r} and e_{1}, …, e_{r} be sequences of integers. Then

det ( ∏_{ℓ=j+1}^{r} W_{s+k(n+i+d_{ℓ})} · ∏_{m=1}^{j} W_{s+k(n+i+e_{m})})_{0≤i,j≤r}

= (−Δ)^{\binom{r+1}{2}} · (−c_{2})^{(s+kn)\binom{r+1}{2}+k\binom{r+1}{3}} · ∏_{ℓ=1}^{r} U_{kℓ}^{r+1−ℓ} ∏_{1≤i≤j≤r}(−c_{2})^{kd_{j}}U_{k(e_{i}−d_{j})}.

Proof. We respectively apply the identities (8),(14), and (7), and the details of the proof are similar to those of Theorem 5.

The following slight variation of the result by Alfred [2] called basic power determinant is a special case of this theorem.

Corollary 9. Let r, s, and k be integers with r ≥ 0. Then

|\begin{matrix}F_{s}^{r} & F_{s}^{r−1}F_{s+k} & ⋯ & F_{s+k}^{r} \\ F_{s+k}^{r} & F_{s+k}^{r−1}F_{s+2k} & ⋯ & F_{s+2k}^{r} \\ ⋮ & ⋮ & ... & ⋮ \\ F_{s+rk}^{r} & F_{s+rk}^{r−1}F_{s+(r+1)k} & ⋯ & F_{s+(r+1)k}^{r} \end{matrix}| = (−1)^{(s+1)\binom{r+1}{2}+k\binom{r+1}{3}}F \binom{r+1}{2}_{k} ∏_{ℓ=1}^{r} F_{kℓ}^{r+1−ℓ}.

Proof. This identity follows immediately from Theorem 8 by letting d_{1} = d_{2} = ⋯ = d_{r} = 0, e_{1} = e_{2} = ⋯ = e_{r} = 1, n = 0 together with the recurrence and the initial values of the Fibonacci numbers.

Another interesting case arises when we let (d_{j}) and (e_{j}) in Theorem 8 be in some specific forms.

Corollary 10. Let s, k, n, and p be integers. Let d_{j} = p−1+j and e_{j} = j −1 for 1 ≤ j ≤ r. Then

det ( ∏_{ℓ=j+1}^{r} W_{s+k(n+i+d_{ℓ})} · ∏_{m=1}^{j} W_{s+k(n+i+e_{m})})_{0≤i,j≤r}

= Δ^{\binom{r+1}{2}}(−c_{2})^{(s+kn)\binom{r+1}{2}+2k\binom{r+1}{3}} · ∏_{ℓ=1}^{r} U_{ℓk}^{r+1−ℓ} · ∏_{ℓ=0}^{r−1} U_{k(p+ℓ)}^{r−ℓ}.

5 Acknowledgments

We thank the anonymous referee and Ramesh Boonratana for their meticulous reading and helpful comments.

References

[1] Brother U. Alfred, Advanced problems and solutions, Fibonacci Quart. 1 (1963), 48.

[2] Brother U. Alfred, Some determinants involving powers of Fibonacci numbers, Fibonacci Quart. 2 (1964), 81–92.

[3] T. Amdeberhan and D. Zeilberger, Determinants through the looking glass, Adv. Appl. Math. 27 (2001), 225–230.

[4] L. Carlitz, Some determinants containing powers of Fibonacci numbers, Fibonacci Quart. 4 (1966), 129–134.

[5] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166.

[6] R. S. Melham and A. G. Shannon, A generalization of the Catalan identity and some consequences, Fibonacci Quart. 33 (1995), 82–84.

[7] F. D. Parker, Advanced problems and solutions, Fibonacci Quart. 2 (1964), 303.

[8] T. Thanatipanonda, Personal website, http://thotsaporn.com/DetFibo.txt.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B20. Keywords: Fibonacci number, determinant, second-order recurrence, Catalan identity.

(Concerned with sequence \underline{A000045}.)

Received February 10 2016; revised versions received June 20 2016; July 16 2016. Published in Journal of Integer Sequences, August 29 2016.

Return to Journal of Integer Sequences home page.