A DETERMINANT OF GENERALIZED FIBONACCI NUMBERS

CHRISTIAN KRATTENTHALER^{†} AND ANTONIO M. OLLER-MARCÉN

Abstract. We evaluate a determinant of generalized Fibonacci numbers, thus providing a common generalization of several determinant evaluation results that have previously appeared in the literature, all of them extending Cassini’s identity for Fibonacci numbers.

1. Introduction

The well-known Fibonacci sequence is given by f_{n} = f_{n−1} + f_{n−2} with f_{0} = f_{1} = 1. Numerous properties of this sequence are known. We refer the reader to the monograph [9] for a wealth of information on this sequence. One of these properties is the so called Cassini identity, given by

f_{n}f_{n+2} − f_{n+1}^{2} = (−1)^{n},

which can be written in matrix form as

det (\begin{matrix}f_{n} & f_{n+1} \\ f_{n+1} & f_{n+2} \end{matrix}) = (−1)^{n}.  (1.1)

Miles [6] introduced k-generalized Fibonacci numbers f_{n}^{(k)} by

f_{n}^{(k)} = ∑_{i=1}^{k} f_{n−i}^{(k)},

with f_{n}^{(k)} = 0 for every 0 ≤ n ≤ k−2, f_{k−1}^{(k)} = 1, and he gave the following generalization of (1.1):

det (\begin{matrix}f_{n}^{(k)} & f_{n+1}^{(k)} & ⋯ & f_{n+k−1}^{(k)} \\ f_{n+1}^{(k)} & f_{n+2}^{(k)} & ⋯ & f_{n+k}^{(k)} \\ ⋮ & ⋮ & ... & ⋮ \\ f_{n+k−1}^{(k)} & f_{n+k}^{(k)} & ⋯ & f_{n+2k−2}^{(k)} \end{matrix}) = (−1)^{\frac{(2n+k)(k−1)}{2}} .  (1.2)

More recently, Stakhov [8] has generalized Cassini’s identity for sequences of the form f_{n} = f_{n−1} + f_{n−p−1}.

Hoggat and Lind [4] consider the so called “dying rabbit problem”, previously introduced in [1] and studied in [2] or [3], which modifies the original Fibonacci setting by letting rabbits die. In previous work by one of the authors [7], the sequence arising in this setting was studied in detail. For instance, the recurrence relation for this sequence depends on two parameters k, ℓ ≥ 2 and is given by

2010 Mathematics Subject Classification. Primary 11B39; Secondary 05A10 05A19 11C20.

Key words and phrases. generalized Fibonacci numbers, Cassini’s identity, determinant evaluation.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

C_{n}^{(k,ℓ)} = C_{n−ℓ}^{(k,ℓ)} + C_{n−ℓ−1}^{(k,ℓ)} + ⋯ + C_{n−k−ℓ+1}^{(k,ℓ)},

where C_{0}^{(k,ℓ)}, …, C_{k+ℓ−2}^{(k,ℓ)} are initial values which will be specified below. It was also proved that, if r_{1}, …, r_{k+ℓ−1} are the distinct roots of g_{k,ℓ}(x) = x^{k+ℓ−1} − \frac{x^{k}−1}{x−1}, then the

general term of the sequence is given by C_{n}^{(k,ℓ)} = ∑_{i=1}^{k+ℓ−1} a_{i}r_{i}^{n}, with

a_{i} = \frac{(−1)^{k+ℓ+i−1}}{∏_{j>i}(r_{j} − r_{i}) ∏_{j<i}(r_{i} − r_{j})}

× (∑_{l=0}^{k−2} C_{l}^{(k,ℓ)} \frac{r_{i}^{l+1} − 1}{r_{i}^{l+1}(r_{i} − 1)} + ∑_{l=k−1}^{k+ℓ−3} C_{l}^{(k,ℓ)} \frac{r_{i}^{k} − 1}{r_{i}^{l+1}(r_{i} − 1)} + C_{k+ℓ−2}^{(k,ℓ)}) . (1.3)

Given the previous sequence, for every j ≥ 0 we can define a matrix A_{j,k,ℓ} by

A_{j,k,ℓ} = (\begin{matrix}C_{j}^{(k,ℓ)} & C_{j+ℓ}^{(k,ℓ)} & C_{j+ℓ+1}^{(k,ℓ)} & … & C_{j+k+2ℓ−3}^{(k,ℓ)} \\ C_{j+1}^{(k,ℓ)} & C_{j+ℓ+1}^{(k,ℓ)} & C_{j+ℓ+2}^{(k,ℓ)} & … & C_{j+k+2ℓ−2}^{(k,ℓ)} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ C_{j+k+ℓ−2}^{(k,ℓ)} & C_{j+k+2ℓ−2}^{(k,ℓ)} & C_{j+k+2ℓ−1}^{(k,ℓ)} & … & C_{j+2k+3ℓ−5}^{(k,ℓ)}. \end{matrix})

The main goal of this paper will be to find an explicit expression for det(A_{j,k,ℓ}), thus extending (1.1) and (1.2).

2. Extending Cassini’s identity

Before we proceed, we have to fix our initial conditions. In the original setting [7], when we start with a pair of rabbits that become mature ℓ months after their birth and die k months after their matureness, the k + ℓ − 1 initial conditions are given by C_{0}^{(k,ℓ)} = ⋯ = C_{ℓ−1}^{(k,ℓ)} = 1 and C_{n}^{(k,ℓ)} = C_{n−1}^{(k,ℓ)} + C_{n−ℓ}^{(k,ℓ)} for every ℓ ≤ n ≤ k + ℓ − 2. Instead, in what follows we will consider the following initial conditions:

C̃_{0}^{(k,ℓ)} = 1,
C̃_{1}^{(k,ℓ)} = ⋯ = C̃_{k−1}^{(k,ℓ)} = 0,
C̃_{k}^{(k,ℓ)} = ⋯ = C̃_{k+ℓ−2}^{(k,ℓ)} = 1.

Note that this change in the initial conditions results only in a shift of indices. Namely, if C_{n}^{(k,ℓ)} denotes the original sequence and C̃_{n}^{(k,ℓ)} denotes the sequence given by the same recurrence relation and these new initial conditions, then for every n ≥ 0 we have

C_{n}^{(k,ℓ)} = C̃_{n+k+1}^{(k,ℓ)}.

Thus, if Ã_{j,k,ℓ} is the corresponding matrix (defined in the obvious way), we have A_{j,k,ℓ} = Ã_{j+k+1,k,ℓ}. Hence, we can focus on finding a formula for det(Ã_{j,k,ℓ}).

First of all, observe that det(Ã_{j,k,ℓ}) = (−1)^{k+ℓ−2} det(Ã_{j−1,k,ℓ}) because Ã_{j,k,ℓ} is obtained from Ã_{j−1,k,ℓ} by replacing the first row by the sum of the first k rows of the matrix, and then permuting the rows so that the first row becomes the last one. If we apply this idea repeatedly, we obtain that det(Ã_{j,k,ℓ}) = (−1)^{j(k+ℓ−2)} det(Ã_{0,k,ℓ}). Hence, it is sufficient to compute this latter determinant.

We shall focus now on computing this determinant, which explicitly is

det(Ã_{0,k,ℓ}) = det (\begin{matrix}C̃_{0}^{(k,ℓ)} & C̃_{ℓ}^{(k,ℓ)} & C̃_{ℓ+1}^{(k,ℓ)} & … & C̃_{k+2ℓ−3}^{(k,ℓ)} \\ C̃_{1}^{(k,ℓ)} & C̃_{ℓ+1}^{(k,ℓ)} & C̃_{ℓ+2}^{(k,ℓ)} & … & C̃_{k+2ℓ−2}^{(k,ℓ)} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ C̃_{k+ℓ−2}^{(k,ℓ)} & C̃_{k+2ℓ−2}^{(k,ℓ)} & C̃_{k+2ℓ−1}^{(k,ℓ)} & … & C̃_{2k+3ℓ−5}^{(k,ℓ)} \end{matrix}) .

To do so, recall that we have C̃_{n}^{(k,ℓ)} = ∑_{s=1}^{k+ℓ−1} a_{s}r_{s}^{n}, where the a_{i}’s are given by (1.3).

We substitute this in the above determinant and use multilinearity in the columns to expand it into the sum

∑_{1≤s_{1},...,s_{k+ℓ−1}≤k+ℓ−1} ( ∏_{j=1}^{k+ℓ−1} a_{s_{j}}) det_{1≤i≤k+ℓ−1} (r_{s_{1}}^{i−1} r_{s_{2}}^{i+ℓ−1} r_{s_{3}}^{i+ℓ} ⋯ r_{s_{k+ℓ−1}}^{i+k+2ℓ−4}) .

Now, if in this sum two of the s_{j}’s should equal each other, then the corresponding two columns in the determinant would be dependent so that the determinant would vanish. We can therefore restrict the sum to permutations of {1, 2, …, k + ℓ − 1}. With S_{k+ℓ−1} denoting the set of these permutations, this leads to

det(Ã_{0,k,ℓ}) = ∑_{σ∈S_{k+ℓ−1}} ( ∏_{j=1}^{k+ℓ−1} a_{σ(j)}) det_{1≤i≤k+ℓ−1} (r_{σ(1)}^{i−1} r_{σ(2)}^{i+ℓ−1} r_{σ(3)}^{i+ℓ} ⋯ r_{σ(k+ℓ−1)}^{i+k+2ℓ−4})

= ( ∏_{j=1}^{k+ℓ−1} a_{j}) ∑_{σ∈S_{k+ℓ−1}} ( ∏_{j=2}^{k+ℓ−1} r_{σ(j)}^{ℓ+j−2}) det_{1≤i,j≤k+ℓ−1} (r_{σ(j)}^{i−1})

= ( ∏_{j=1}^{k+ℓ−1} a_{j}) ∑_{σ∈S_{k+ℓ−1}}(sgn σ) ( ∏_{j=2}^{k+ℓ−1} r_{σ(j)}^{ℓ+j−2}) det_{1≤i,j≤k+ℓ−1} (r_{j}^{i−1})

= ( ∏_{j=1}^{k+ℓ−1} a_{j}) ( ∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})) ∑_{σ∈S_{k+ℓ−1}}(sgn σ) ( ∏_{j=2}^{k+ℓ−1} r_{σ(j)}^{ℓ+j−2})

= ( ∏_{j=1}^{k+ℓ−1} a_{j}) ( ∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})) det_{1≤i≤k+ℓ−1} (1 r_{i}^{ℓ} r_{i}^{ℓ+1} ⋯ r_{i}^{k+2ℓ−3})

= ( ∏_{j=1}^{k+ℓ−1} a_{j}) ( ∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})) ( ∏_{i=1}^{k+ℓ−1} r_{i})^{k+2ℓ−3}

× det_{1≤i≤k+ℓ−1} (r_{i}^{−k−2ℓ+3} r_{i}^{−k−ℓ+3} r_{i}^{−k−ℓ+4} ⋯ 1)

= ( ∏_{j=1}^{k+ℓ−1} a_{j}) ( ∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})(r_{i}^{−1} − r_{j}^{−1})) ( ∏_{i=1}^{k+ℓ−1} r_{i})^{k+2ℓ−3}

× h_{ℓ−1}(r_{1}^{−1}, …, r_{k+ℓ−1}^{−1}).  (2.1)

In the last line we have used the following notations and facts: first of all, h_{m}(x_{1}, …, x_{N}) denotes the m-th complete homogeneous symmetric function in N variables x_{1}, …, x_{N}, explicitly given by

h_{m}(x_{1}, …, x_{N}) = ∑_{1≤i_{1}≤···≤i_{m}≤N} x_{i_{1}} ⋯ x_{i_{m}}.

Furthermore, the Schur function indexed by a partition λ = (λ_{1}, …, λ_{N}) in the variables x_{1}, …, x_{N} is defined by

s_{λ}(x_{1}, …, x_{N}) = \begin{matrix}det_{1≤i,j≤N} & (x_{i}^{λ_{j}+N−j}) \\ det_{1≤i,j≤N} & (x_{i}^{N−j}) \end{matrix} = \frac{det_{1≤i,j≤N} (x_{i}^{λ_{j}+N−j})}{∏_{1≤i<j≤N}(x_{i} − x_{j})}.

It is well-known (cf. [5, p. 41, Eq. (3.4)]) that for λ = (m, 0, …, 0) the Schur function s_{λ}(x_{1}, …, x_{N}) reduces to h_{m}(x_{1}, …, x_{N}). These facts together explain the last line in the above computation.

To proceed further, let us first observe that, by reading off the constant coefficient of g_{k,ℓ}(x), we obtain

∏_{i=1}^{k+ℓ−1} r_{i} = (−1)^{k+ℓ}.

Furthermore, we have

g_{k,ℓ}(x) = x^{k+ℓ−1} − \frac{x^{k} − 1}{x − 1} = ∏_{i=1}^{k+ℓ−1}(x − r_{i}) = (−1)^{k+ℓ−1} ∏_{i=1}^{k+ℓ−1} r_{i}(1 − r_{i}^{−1}x)

= − ∏_{i=1}^{k+ℓ−1}(1 − r_{i}^{−1}x).

Hence, we obtain

∑_{m=0}^{∞} h_{m}(r_{1}^{−1}, …, r_{k+ℓ−1}^{−1})x^{m} = \frac{1}{∏_{i=1}^{k+ℓ−1}(1 − r_{i}^{−1}x)}

= \frac{1}{\frac{x^{k}−1}{x−1} − x^{k+ℓ−1}}

= \frac{1 − x}{1 − x^{k} − x^{k+ℓ−1} + x^{k+ℓ}}

= 1 − x + x^{k} − x^{k+1} + ⋯ + O(x^{k+ℓ−1}).

In order to evaluate h_{ℓ−1}(r_{1}^{−1}, …, r_{k+ℓ−1}^{−1}), we just have to extract the coefficient of x^{ℓ−1} in the expansion on the right-hand side. This is easy: if ℓ − 1 equals a multiple of k then we obtain 1, if ℓ − 2 equals a multiple of k then we obtain −1, and in all other cases we obtain 0.

We continue evaluating the other factors in (2.1). We have

∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})(r_{i}^{−1} − r_{j}^{−1}) = ∏_{1≤i<j≤k+ℓ−1} \frac{(r_{j} − r_{i})^{2}}{r_{i}r_{j}}

= \frac{∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})^{2}}{( ∏_{i=1}^{k+ℓ−1} r_{i})^{k+ℓ−2}}

= \frac{∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})^{2}}{(−1)^{k+ℓ}} .

Furthermore, we must compute ∏_{j=1}^{k+ℓ−1} a_{j}. To begin with, recall the formula (1.3) and

the fact that C̃_{0}^{(k,ℓ)} = C̃_{k}^{(k,ℓ)} = ⋯ = C̃_{k+ℓ−2}^{(k,ℓ)} = 1 and C̃_{1}^{(k,ℓ)} = ⋯ = C̃_{k−1}^{(k,ℓ)} = 0. With this in mind, we get

∏_{j=1}^{k+ℓ−1} a_{j} = \frac{∏_{j=1}^{k+ℓ−1}(−1)^{k+ℓ+j−1}}{∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})^{2}} ∏_{j=1}^{k+ℓ−1} (\frac{r_{j} − 1}{r_{j}(r_{j} − 1)} + ∑_{i=1}^{ℓ−2} \frac{r_{j}^{k} − 1}{r_{j}^{k+i}(r_{j} − 1)} + 1)

= \frac{(−1)^{\frac{(3k+3ℓ−2)(k+ℓ−1)}{2}}}{∏_{1≤i<j≤k+ℓ−1}(r_{j} − r_{i})^{2}} ∏_{j=1}^{k+ℓ−1} (\frac{1}{r_{j}} + ∑_{i=1}^{ℓ−2} \frac{r_{j}^{k} − 1}{r_{j}^{k+i}(r_{j} − 1)} + 1) .

Moreover, observe that

\frac{1}{r_{j}} + ∑_{i=1}^{ℓ−2} \frac{r_{j}^{k} − 1}{r_{j}^{k+i}(r_{j} − 1)} + 1 = \frac{1}{r_{j}} + \frac{r_{j}^{k} − 1}{r_{j} − 1} ∑_{i=1}^{ℓ−2} \frac{1}{r_{j}^{k+i}} + 1

= \frac{1}{r_{j}} + r_{j}^{k+ℓ−1} ∑_{i=1}^{ℓ−2} \frac{1}{r_{j}^{k+i}} + 1

= \frac{r_{j}^{ℓ} − 1}{r_{j}(r_{j} − 1)}.

Here, to obtain the second line, we have used the fact that 1 ≠ r_{j} is a root of x^{k+ℓ−1} − \frac{x^{k}−1}{x−1}.

Now, to conclude we must compute ∏_{j=1}^{k+ℓ−1} \frac{r_{j}^{ℓ} − 1}{r_{j}(r_{j} − 1)}. To do so, let ω be a primitive

ℓ-th root of unity. Then

∏_{j=1}^{k+ℓ−1}(r_{j}^{ℓ} − 1) = ∏_{j=1}^{k+ℓ−1} ∏_{i=1}^{ℓ}(r_{j} − ω^{i}) = ∏_{i=1}^{ℓ} ∏_{j=1}^{k+ℓ−1}(r_{j} − ω^{i})

= ( ∏_{j=1}^{k+ℓ−1}(r_{j} − 1)) (∏_{i=1}^{ℓ−1} ∏_{j=1}^{k+ℓ−1}(r_{j} − ω^{i}))

= ( ∏_{j=1}^{k+ℓ−1}(r_{j} − 1)) (−1)^{(k+ℓ−1)(ℓ−1)} (∏_{i=1}^{ℓ−1} g_{k,ℓ}(ω^{i})) .

Furthermore, g_{k,ℓ}(ω^{i}) = ω^{i(k+ℓ−1)} − \frac{ω^{ik}−1}{ω^{i}−1} = −\frac{ω^{i(k−1)}−1}{ω^{i}−1}. Consequently, we have

∏_{j=1}^{k+ℓ−1} \frac{r_{j}^{ℓ} − 1}{r_{j}(r_{j} − 1)} = (−1)^{(k+ℓ)ℓ} (∏_{i=1}^{ℓ−1} \frac{ω^{i(k−1)} − 1}{ω^{i} − 1}) .

Finally observe that

∏_{i=1}^{ℓ−1} \frac{ω^{i(k−1)} − 1}{ω^{i} − 1} = \begin{cases}1, & if gcd(ℓ, k − 1) = 1; \\ 0, & otherwise. \end{cases}

We can now collect all the work done to obtain the following result.

Theorem. For all integers k and ℓ with k, ℓ ≥ 2, we have

det(Ã_{0,k,ℓ}) = \begin{cases}(−1)^{\frac{(k+ℓ)(k+ℓ−1)}{2} +1}, & if ℓ − 1 = αk and gcd(ℓ, k − 1) = 1; \\ (−1)^{\frac{(k+ℓ)(k+ℓ−1)}{2}} , & if ℓ − 2 = βk and gcd(ℓ, k − 1) = 1; \\ 0, & otherwise. \end{cases}

Corollary. Let k_{0}, ℓ_{0} ≥ 2 be any integers. Then the following hold:

i) The sequence {α_{ℓ}}_{ℓ≥2} given by α_{ℓ} = | det(Ã_{0,k_{0},ℓ})| is periodic, and its period is a

divisor of k_{0} · rad(k_{0} − 1).
ii) The sequence {β_{k}}_{k≥2} given by β_{k} = | det(Ã_{0,k,ℓ_{0}})| is eventually zero.

Proof. Clearly gcd(ℓ, k − 1) > 1 implies that gcd(ℓ + k · rad(k − 1), k − 1) > 1. In the same way, if ℓ − 1 and ℓ − 2 are not multiples of k, then neither are ℓ + k · rad(k − 1) − 1 or ℓ + k · rad(k − 1) − 2. Consequently, if a_{ℓ} = 0, also a_{ℓ+k·rad(k−1)} = 0 as claimed. □

3. A general setting for further work

The computations that have been carried out in the previous section make sense in a more general setting. Indeed, let m be a natural number and consider two families of integers F_{1} = {α_{0}, …, α_{m−1}} and F_{2} = {β_{1}, …, β_{m}}. We can now define a sequence in the following recursive way:

s_{n} = \begin{cases}α_{n}, & if n < m, \\ ∑_{j=1}^{m} β_{j}s_{n−j}, & otherwise. \end{cases}

Given a third family of integers F_{3} = {γ_{1}, …, γ_{m}} we define a sequence {A(n)}_{n≥0} of m × m matrices by:

A(n)_{i,j} = s_{n+i+γ_{j}}, 1 ≤ i, j ≤ m.

In this setting, we have the following easy lemma.

Lemma 1. Up to a constant, the sequence {det A(n)}_{n≥0} is a geometric progression defined by powers of β_{m}; i.e., det A(n) = Cβ_{m} for some constant C.

Proof. This is an easy consequence of the definition of {s_{n}}, together with elementary properties of determinants. Namely, the last row of A(n) is given by

A(n)_{m,j} = s_{n+m+γ_{j}} = ∑_{i=1}^{m} β_{i}s_{n+m+γ_{j}−i}.

Hence, it follows that

det A(n) = (−1)^{m−1}β_{m} det A(n − 1),

as claimed. □

As a consequence of the lemma above, the only point of interest is to compute the constant C which, of course, will depend on the three families F_{1}, F_{2}, F_{3}. In Section 2, we have considered the case when m = k + l − 1 and:

F_{1} = {C_{0}^{(k,l)}, …, C_{k+k−2}^{(k,l)}},
F_{2} = {1, 1, 1, …, 1},
F_{3} = {0, l, l + 1, …, k + 2l − 3}.

A good source for future work would be to try to understand the dependency of C as a function of the families F_{1}, F_{2}, F_{3} in this general setting.

References

[1] Alfred B.U., Exploring Fibonacci numbers, Fibonacci Quart. 1 (1963), no. 1, 57–63.

[2] Alfred B.U., Dying rabbit problem revived, Fibonacci Quart. 1 (1963), no. 4, 482–487.

[3] Cohn, J.H.E., Letter to the editor, Fibonacci Quart. 2 (1964), 108.

[4] Hoggat V.E., Lind D.A., The dying rabbit problem, Fibonacci Quart. 7 (1969), no. 5, 482– 487.

[5] Macdonald, I.G., Symmetric funtions and Hall polynomials, 2nd ed., Oxford University Press, New York/London, 1995.

[6] Miles, E., Generalized Fibonacci numbers and related matrices, Amer. Math. Monthly 67 (1960), 745–752.

[7] Oller-Marcén, A.M., The dying rabbit problem revisited, Integers 9 (2009), 129–138.

[8] Stakhov, A.P., Fibonacci matrices, a generalization of the “Cassini formula”, and a new coding theory, Chaos Solitons Fractals 30 (2006), no. 1, 1108–1109.

[9] Vajda, S., Fibonacci and Lucas numbers, and the golden section, John Wiley & Sons, New York, 1989.

Fakultät für Mathematik, Universität Wien, Nordbergstrasze 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.

Centro Universitario de la Defensa, Ctra. de Huesca s/n, 50090 Zaragoza (España)

E-mail address: oller@unizar.es