LINEAR RECURRENCES
EMRAH KILIC1 AND PANTELIMON ST ˘ANIC ˘A2
Abstract. We consider𝑘sequences of generalized order-𝑘linear recurrences with arbitrary initial conditions and coefficients, and we give their generalized Binet formulas and generating functions. We also obtain a new matrix method to derive explicit formulas for the sums of terms of the𝑘sequences. Further, some relationships between determinants of certain Hessenberg matrices and the terms of these sequences are obtained.
1. Introduction
Linear recurrences have played (and will most certainly play) an important role in many areas of mathematics. A lot of authors have studied various properties of linear recurrences (such as the well-known Fibonacci and Pell sequences).
In [2], Er defined𝑘 linear recurring sequences of order at most𝑘 as shown: for 𝑛 >0 and 1≤𝑖≤𝑘,
𝑔𝑛𝑖 =
𝑘
∑
𝑗=1
𝑔𝑖𝑛−𝑗 with initial conditions
𝑔𝑛𝑖 =
{ 1 if𝑛= 1−𝑖,
0 otherwise, for 1−𝑘≤𝑛≤0,
where𝑔𝑛𝑖 is the𝑛term of the𝑖th generalized order-𝑘 Fibonacci sequence.
More generally, in [6], the author gave the generalized order-𝑘 Fibonacci and Pell (F-P) sequence as follows: for𝑚≥0, 𝑛 >0 and 1≤𝑖≤𝑘
𝑢𝑖𝑛 = 2𝑚𝑢𝑖𝑛−1+𝑢𝑖𝑛−2+⋅ ⋅ ⋅+𝑢𝑖𝑛−𝑘 with initial conditions
𝑢𝑖𝑛 =
{ 1 if𝑛= 1−𝑖,
0 otherwise, for 1−𝑘≤𝑛≤0, where𝑢𝑖𝑛 is the𝑛term of the𝑖th generalized order-𝑘F-P sequence.
When 𝑚 = 0, the generalized order-𝑘 F-P sequence { 𝑢𝑖𝑛}
is reduced to the generalized order-𝑘 Fibonacci sequence {
𝑔𝑖𝑛}
. Also when𝑚 = 1, the generalized order-𝑘F-P sequence is reduced to the generalized order-𝑘Pell sequence{
𝑃𝑛𝑖} (for more details see [5]).
Define 𝑘 sequences of 𝑘-th order linear recurrence relation { 𝑓𝑛𝑖}
as shown, for 𝑛 >0 and 1≤𝑖≤𝑘
𝑓𝑛𝑖 =𝑐1𝑓𝑛−1𝑖 +𝑐2𝑓𝑛−2𝑖 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘𝑖 (1.1)
2000Mathematics Subject Classification. 11B37, 40C05, 15A36, 15A15.
Key words and phrases. Higher order recurrence, generating matrix, sum, matrix method.
1
2 EMRAH KILIC AND PANTELIMON ST ˘ANIC ˘A
with initial conditions 𝑓𝑛𝑖 =
{ 1 if𝑛= 1−𝑖,
0 otherwise, for 1−𝑘≤𝑛≤0
where𝑐𝑗, 1≤𝑗 ≤𝑘,are real constant coefficients, and𝑓𝑛𝑖 is the𝑛th term of the𝑖th sequence. When 𝑘= 2, 𝑐1 =𝑐2 = 1, respectively,𝑘=𝑐1 = 2, 𝑐2= 1 the sequence {𝑓𝑛2}
is reduced to the Fibonacci sequence {𝐹𝑛}, respectively, the Pell sequence {𝑃𝑛}.
Define the𝑘×𝑘 companion matrix𝐴and the matrix𝐺𝑛 as follows:
𝐴=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
𝑐1 𝑐2 . . . 𝑐𝑘−1 𝑐𝑘
1 0 . . . 0 0
0 1 . . . 0 0
... ... . .. ... ...
0 0 . . . 1 0
⎤
⎥
⎥
⎥
⎥
⎥
⎦
and𝐺𝑛=
⎡
⎢
⎢
⎢
⎣
𝑓𝑛1 𝑓𝑛2 . . . 𝑓𝑛𝑘 𝑓𝑛−11 𝑓𝑛−12 . . . 𝑓𝑛−1𝑘
... ... . .. ... 𝑓𝑛−𝑘+11 𝑓𝑛−𝑘+12 . . . 𝑓𝑛−𝑘+1𝑘
⎤
⎥
⎥
⎥
⎦ (1.2) Using the approach of Kalman [3], Er [2] showed that
𝐺𝑛=𝐴𝑛 (1.3)
and
𝑓𝑛+1𝑖 = 𝑐𝑖𝑓𝑛1+𝑓𝑛𝑖+1, for 1≤𝑖≤𝑘−1 (1.4)
𝑓𝑛+1𝑘 = 𝑐𝑘𝑓𝑛1. (1.5)
Matrix methods are helpful and convenient in solving certain problems stemming from linear recursion relations, such as that of finding an explicit expression for the 𝑛th term of the Fibonacci sequence (see [9]), or of analyzing the vibration of a weighted string [10, pp. 152–154]. Here we will consider a more general case using matrix methods to obtain some explicit formulas for the 𝑛th term of a general recurrence relation and the sums of terms of the recurrence. The general linear recurrence relations have been considered by many mathematicians (for references, one may see [1, 2, 4, 5]). The authors of [4, 6, 7] give the generalized Binet formula for the generalized order-𝑘Fibonacci, Lucas and Pell numbers by matrix methods.
In this paper, we consider𝑘sequences of general order-𝑘linear recurrences with 𝑘 arbitrary initial conditions and coefficients. Then we study the properties of 𝑘 linear recursive sequences and derive many applications to matrices.
2. General linear recurrence with𝑘 initial conditions
Define a set of𝑘 sequences satisfying the generalized order-𝑘 linear recurrence {𝑡𝑖𝑛(𝑟1, 𝑟2, . . . , 𝑟𝑘)} as shown: for𝑛 >0 and 1≤𝑖≤𝑘
𝑡𝑖𝑛=𝑐1𝑡𝑖𝑛−1+𝑐2𝑡𝑖𝑛−1+⋅ ⋅ ⋅+𝑐𝑘𝑡𝑖𝑛−𝑘 with𝑘initial conditions
𝑡𝑖𝑛=
⎧
⎨
⎩
𝑟1 if𝑛= 1−𝑖, 𝑟2 if𝑛= 2−𝑖,
... ... 𝑟𝑘 if𝑛=𝑘−𝑖,
0 otherwise,
for 1−𝑘≤𝑛≤0
where the coefficients𝑐𝑖 and the initial conditions 𝑟𝑖 are arbitrary, for 1≤𝑖 ≤𝑘, and𝑡𝑖𝑛is the𝑛th term of𝑖th sequence. Clearly,{
𝑡𝑖𝑛(1,0, . . . ,0)}
={ 𝑓𝑛𝑖}
, where𝑓𝑛𝑖 are given by (1.1).
Next, we define a𝑘×𝑘matrix𝐻𝑛= [ℎ𝑖𝑗] by
𝐻𝑛 =
⎡
⎢
⎢
⎢
⎣
𝑡1𝑛 𝑡2𝑛 . . . 𝑡𝑘𝑛 𝑡1𝑛−1 𝑡2𝑛−1 . . . 𝑡𝑘𝑛−1
... ... . .. ... 𝑡1𝑛−𝑘+1 𝑡2𝑛−𝑘+1 . . . 𝑡𝑘𝑛−𝑘+1
⎤
⎥
⎥
⎥
⎦
. (2.1)
By Kalman’s [3] approach, we find that
𝐻𝑛=𝐴𝐻𝑛−1 and so, 𝐻𝑛=𝐴𝑛−1𝐻1, (2.2) where the matrix𝐴is given by (1.2).
Theorem 1. For𝑛 >0,
𝑡𝑖𝑛=
𝑖
∑
𝑗=1
𝑟𝑖+1−𝑗𝑓𝑛𝑗, where𝑓𝑛𝑖 is defined as before.
Proof. From (2.2), we have𝐻𝑛=𝐴𝑛−1𝐻1.From (2.1) we get
𝐻1=
⎡
⎢
⎢
⎢
⎣
𝑡11 𝑡21 ⋅ ⋅ ⋅ 𝑡𝑘1 𝑡10 𝑡20 ⋅ ⋅ ⋅ 𝑡𝑘0 ... ... . .. ... 𝑡12−𝑘 𝑡22−𝑘 ⋅ ⋅ ⋅ 𝑡𝑘2−𝑘
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
∑
𝑗=1
𝑐𝑗𝑟2−𝑗
2
∑
𝑗=1
𝑐𝑗𝑟3−𝑗 . . .
𝑘
∑
𝑗=1
𝑐𝑗𝑟𝑘+1−𝑗
𝑟1 𝑟2 ⋅ ⋅ ⋅ 𝑟𝑘
0 𝑟1 ⋅ ⋅ ⋅ 𝑟𝑘−1
... ... . .. ...
0 0 ⋅ ⋅ ⋅ 𝑟1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦ ,
which implies that
𝐻1=𝐴𝐸, (2.3)
where the matrix𝐸is the𝑘×𝑘upper tridiagonal matrix of the form
𝐸=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
𝑟1 𝑟2 𝑟3 . . . 𝑟𝑘 𝑟1 𝑟2 . . . 𝑟𝑘−1
𝑟1 . . . 𝑟𝑘−2 . .. ...
0 𝑟1
⎤
⎥
⎥
⎥
⎥
⎥
⎦ .
Using Er’s approach [2] and (1.3), we obtain 𝐴𝑛 =𝐺𝑛. Since 𝐻𝑛 =𝐴𝑛−1𝐻1 and 𝐻1=𝐴𝐸, we get
𝐻𝑛 =𝐴𝑛𝐸, (2.4)
which can be re-written as
𝑡𝑖𝑛=
𝑖
∑
𝑗=1
𝑟𝑖+1−𝑗𝑓𝑛𝑗, (2.5)
and the proof is complete.
Therefore we see that the general recurrence with arbitrary initial conditions can be written as a linear combination of terms of the recurrence{
𝑓𝑛𝑖}
.By this result, we can easily derive some properties of the recurrence{
𝑡𝑖𝑛} .
4 EMRAH KILIC AND PANTELIMON ST ˘ANIC ˘A
Corollary 1. For𝑛∈ℤ,
det
⎛
⎜
⎜
⎜
⎝
𝑡1𝑛 𝑡2𝑛 . . . 𝑡𝑘𝑛 𝑡1𝑛−1 𝑡2𝑛−1 . . . 𝑡𝑘𝑛−1
... ... ...
𝑡1𝑛−𝑘+1 𝑡2𝑛−𝑘+1 . . . 𝑡𝑘𝑛−𝑘+1
⎞
⎟
⎟
⎟
⎠
= (−1)𝑘+1𝑐𝑘𝑟1𝑘.
Proof. Let 𝐻𝑛, 𝐺𝑛 and 𝐸 be the matrices defined in the proof of Theorem 1. It is clear that det𝐺𝑛 = (−1)𝑘+1𝑐𝑘 and det𝐸 = 𝑟1𝑘. Taking the determinant in 𝐻𝑛 =𝐺𝑛𝐸 shows our claim.
Corollary 1 is a vast generalization of the well known Cassini’s identity for the Fibonacci numbers, that is,𝐹𝑛2−𝐹𝑛−1𝐹𝑛+1= (−1)𝑛−1.
Corollary 2. Let 𝑥𝑘 −𝑐1𝑥𝑘−1−𝑐2𝑥𝑘−2 − ⋅ ⋅ ⋅ −𝑐𝑘 = (𝑥−𝜆1)⋅ ⋅ ⋅(𝑥−𝜆𝑘) and 𝑒𝑛=𝜆𝑛1+𝜆𝑛2+⋅ ⋅ ⋅+𝜆𝑛𝑘.Then
𝑒𝑛=
𝑘
∑
𝑖=1
( 𝑖
∑
𝑚=1
𝑟𝑖+1−𝑚𝑓𝑛+1−𝑡𝑚 )
.
Proof. 𝐴is the companion matrix from (1.2) and 𝑥𝑘−𝑐1𝑥𝑘−1−𝑐2𝑥𝑘−2− ⋅ ⋅ ⋅ −𝑐𝑘
is its characteristic polynomial, whose roots (also, eigenvalues of𝐴) are𝜆1, . . . , 𝜆𝑘. Thus the eigenvalues of𝐴𝑛 are𝜆𝑛1, . . . , 𝜆𝑛𝑘. Denote the trace of the matrix 𝑊 by tr(𝑊).By Theorem 1,
𝑒𝑛 = 𝜆𝑛1+𝜆𝑛2+⋅ ⋅ ⋅+𝜆𝑛𝑘 = tr (𝐻𝑛) = tr (𝐺𝑛𝐸)
=
𝑘
∑
𝑖=1
( 𝑖
∑
𝑚=1
𝑟𝑖+1−𝑚𝑓𝑛+1−𝑡𝑚 )
. Thus the proof is complete.
3. Sums of the terms of recurrence { 𝑡𝑘𝑛} In this section we deal with the sums of the terms of recurrence{
𝑡𝑘𝑛}
subscripted from 1 to𝑛.By the result of Theorem 1, clearly
𝑡𝑘𝑛=
𝑘
∑
𝑗=1
𝑟𝑘−𝑗+1𝑓𝑛𝑗. (3.1)
The characteristic polynomial of both the matrix 𝐴 and the sequence{ 𝑓𝑛𝑘}
is 𝐸(𝑥) =𝑥𝑘−𝑐1𝑥𝑘−1−𝑐2𝑥𝑘−2−⋅ ⋅ ⋅−𝑐𝑘−1𝑥−𝑐𝑘.Let𝜆1, 𝜆2, . . . , 𝜆𝑘be the characteristic roots of the equation.
Hypothesis 1. Throughout this paper, we suppose that the roots 𝜆1, . . . , 𝜆𝑘 are distinct (which happens if gcd(𝐸, 𝐸′) = 1) and not equal to 1.
As special cases, we note that when 𝑐𝑖 = 1 for 1 ≤ 𝑖 ≤𝑘, the equation𝑥𝑘− 𝑥𝑘−1− ⋅ ⋅ ⋅ −𝑥−1 = 0 does not have multiple roots (see [7]). Also, when𝑐1 = 2 and 𝑐𝑖 = 1 for 2≤𝑖≤𝑘, the equation 𝑥𝑘−2𝑥𝑘−1−𝑥𝑘−2− ⋅ ⋅ ⋅ −𝑥−1 = 0 does not have multiple roots (see [5]). For the case𝑐1 = 2𝑚, 𝑐𝑖 = 1 for 2≤𝑖≤𝑘 and 𝑚≥0,we refer to [6].
Let𝑉 = Λ𝑇 be a𝑘×𝑘Vandermonde matrix, where
Λ =
⎡
⎢
⎢
⎢
⎣
𝜆𝑘−11 𝜆𝑘−21 . . . 𝜆1 1 𝜆𝑘−12 𝜆𝑘−22 . . . 𝜆2 1 ... ... ... ... 𝜆𝑘−1𝑘 𝜆𝑘−2𝑘 . . . 𝜆𝑘 1
⎤
⎥
⎥
⎥
⎦
. (3.2)
Let𝑤𝑘𝑖 be the column matrix
𝑤𝑘𝑖 =
⎡
⎢
⎢
⎢
⎣
𝜆𝑛+𝑘−𝑖1 𝜆𝑛+𝑘−𝑖2
... 𝜆𝑛+𝑘−𝑖𝑘
⎤
⎥
⎥
⎥
⎦
and Λ(𝑖)𝑗 be the𝑘×𝑘matrix obtained from Λ by replacing the𝑗th column of Λ by 𝑤𝑖𝑘.
The generalized Binet formula for the recurrence { 𝑓𝑛𝑖}
can be expressed using 𝑉 = Λ𝑇 and𝑉𝑗(𝑖)= Λ(𝑖)𝑗 .
Theorem 2. For𝑛 >0and1≤𝑖≤𝑘, 𝑓𝑛−𝑖+1𝑗 =
det( 𝑉𝑗(𝑖)) det (𝑉) .
Proof. Since the eigenvalues of𝐴are distinct (by our Hypothesis 1), we infer that𝐴 is diagonalizable. It is readily seen that𝐴𝑉 =𝑉 𝐷,where𝐷=𝑑𝑖𝑎𝑔(𝜆1, 𝜆2, . . . , 𝜆𝑘). Since 𝑉 is invertible, 𝑉−1𝐴𝑉 = 𝐷. Hence, 𝐴 is similar to 𝐷. So we obtain 𝐴𝑛𝑉 = 𝑉 𝐷𝑛. Since 𝐴𝑛 = 𝐺𝑛 = [𝑔𝑖𝑗], we obtain the following linear system of equations:
𝑔𝑖1𝜆𝑘−11 +𝑔𝑖2𝜆𝑘−21 +⋅ ⋅ ⋅+𝑔𝑖𝑘 =𝜆𝑛+𝑘−𝑖1 𝑔𝑖1𝜆𝑘−12 +𝑔𝑖2𝜆𝑘−22 +⋅ ⋅ ⋅+𝑔𝑖𝑘 =𝜆𝑛+𝑘−𝑖2
... ...
𝑔𝑖1𝜆𝑘−1𝑘 +𝑔𝑖2𝜆𝑘−2𝑘 +⋅ ⋅ ⋅+𝑔𝑖𝑘 =𝜆𝑛+𝑘−𝑖𝑘 Thus, for 𝑗 = 1,2, . . . , 𝑘, we get 𝑔𝑖𝑗 =
det( Λ(𝑖)𝑗 )
det (Λ) , where 𝐺𝑛 = [𝑔𝑖𝑗] and 𝑔𝑖𝑗 = 𝑓𝑛−𝑖+1𝑗 . The proof is complete.
Corollary 3. For𝑛 >0, we have𝑡𝑖𝑛= 1 det (Λ)
𝑖
∑
𝑗=1
𝑟𝑘+1−𝑗det( Λ(1)𝑗 )
.
For example, when 𝑐1 = 2 and 𝑐𝑖 = 1 for all 2 ≤ 𝑗 ≤ 𝑘, the sequence { 𝑓𝑛𝑖} is reduced to the generalized order-𝑘 Pell sequence {
𝑃𝑛𝑖}
and so the sums of the generalized order-𝑘 Pell numbers is given by
𝑛
∑
𝑖=1
𝑃𝑖𝑘 =(
𝑃𝑛1+𝑃𝑛2+⋅ ⋅ ⋅+𝑃𝑛𝑘−1) /𝑘.
6 EMRAH KILIC AND PANTELIMON ST ˘ANIC ˘A
When𝑘= 3, 𝑐𝑖= 1 for 1≤𝑖≤3,the sequence{ 𝑓𝑛𝑖}
is reduced to the generalized Tribonacci sequence{
𝑇𝑛𝑖} and so
𝑛
∑
𝑖=1
𝑇𝑖3=(
𝑇𝑛1+𝑇𝑛2+𝑇𝑛3−1) /2 and by the definition of the{
𝑇𝑛𝑖}
, we have𝑇𝑛1=𝑇𝑛+13 and 𝑇𝑛2=𝑇𝑛3+𝑇𝑛−13 . For easy writing, we denote𝑇𝑛3by𝑇𝑛.Thus we can write
𝑛
∑
𝑖=1
𝑇𝑖= (𝑇𝑛+1+ 2𝑇𝑛+𝑇𝑛−1−1)/2 = (𝑇𝑛+2+𝑇𝑛−1)/2.
We expand our matrix method to find all sums of terms of𝑘 sequences of gen- eralized order-𝑘recurrences{
𝑓𝑛𝑖}
subscripted 1 to𝑛for all 1≤𝑖≤𝑘.
Define the following two sums: for 1≤𝑖 ≤𝑘, let𝑆(𝑖)𝑛 =∑𝑛−1
𝑚=1𝑓𝑚𝑖 and 𝑇𝑛(𝑖)=
∑𝑛−𝑖
𝑚=1−𝑖𝑓𝑚𝑖 .Then𝑇𝑛(𝑖)=𝑆𝑛−𝑖+1(𝑖) + 1,since 𝑓𝑛𝑖 =
{ 1 if𝑖= 1−𝑛,
0 otherwise, for 1−𝑘≤𝑛≤0.
Further,
𝑆𝑛+1(𝑖) = 𝑓𝑛𝑖 +𝑆𝑛(𝑖) (3.3)
𝑇𝑛+1(𝑖) = 𝑓𝑛−𝑖+1𝑖 +𝑇𝑛(𝑖) (3.4)
We next define two (𝑘+ 1)×(𝑘+ 1) matrices as follows:
𝐵𝑖 =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0 . . . 0
0 ...
0 𝐴
1 0 ... 0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
←(𝑖+ 1) st row
and
𝑌𝑛,𝑖=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0 . . . 0
𝑆𝑛(𝑖)
𝑆𝑛−1(𝑖)
... 𝐺𝑛
𝑆(𝑖)𝑛−𝑖+2 𝑇𝑛(𝑖)
𝑇𝑛−1(𝑖) ... 𝑇𝑛−𝑘+𝑖(𝑖)
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
← 1st row
← 2nd row
... ...
← (𝑖−1) st row
← 𝑖th row
← (𝑖+ 1) st row ... ...
← 𝑘th row
where the matrices𝐴and𝐺𝑛 were defined before. We have the following result.
Theorem 3. For𝑛 >0,
𝑌𝑛,𝑖=𝐵𝑖𝑛.
Proof. Combining the identities (3.3) and (3.4), we obtain 𝑌𝑛+1,𝑖=𝑌𝑛,𝑖𝐵𝑖=⋅ ⋅ ⋅=𝑌1,𝑖𝐵𝑛𝑖. From the definitions of{
𝑇𝑛(𝑖)
} and{
𝑆𝑛(𝑖)
}
,we can easily check that𝑌1,𝑖=𝐵𝑖, and the theorem is proven.
Now we are going to derive an explicit expression for every sum𝑆𝑛(𝑖)for 1≤𝑖≤𝑘 by matrix methods.
We first make some observations. If we expand det𝐵𝑖 with respect to the first row, we get
det𝐵𝑖= det𝐴 and the characteristic polynomials of𝐴, 𝐵𝑖 satisfy
𝐶𝐵𝑖(𝜆) = (1−𝜆)𝐶𝐴(𝜆).
Since𝜆1, 𝜆2, . . . , 𝜆𝑘 are the roots of𝐶𝐴(𝜆) (distinct and nonequal to 1), the eigen- values of matrix𝐵𝑖are𝜆1, 𝜆2, . . . , 𝜆𝑘,1.Therefore the eigenvalues of the matrix𝐵𝑖
are distinct, and so𝐵𝑖 is diagonalizable.
For easy writing, let
𝜇𝑖=
𝑘
∑
𝑡=𝑖
𝑐𝑡 1−
𝑘
∑
𝑡=1
𝑐𝑡
for 1< 𝑖≤𝑘and𝜇1= 1 1−
𝑘
∑
𝑡=1
𝑐𝑡
.
The following (𝑘+ 1)×(𝑘+ 1) matrix for 1< 𝑖≤𝑘
𝑃 =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0 0 . . . 0
𝜇𝑖 𝜆𝑘−11 𝜆𝑘−12 . . . 𝜆𝑘−1𝑘 𝜇𝑖 𝜆𝑘−21 𝜆𝑘−22 . . . 𝜆𝑘−2𝑘
... ... ... ...
𝜇𝑖 𝜆𝑘−𝑖+11 𝜆𝑘−𝑖+12 𝜆𝑘−𝑖+1𝑘 𝜇𝑖+ 1 𝜆𝑘−𝑖1 𝜆𝑘−𝑖2 𝜆𝑘−𝑖𝑘 𝜇𝑖+ 1 𝜆𝑘−𝑖−11 𝜆𝑘−𝑖−12 𝜆𝑘−𝑖−1𝑘
... 𝜆1 𝜆2 . . . 𝜆𝑘
𝜇𝑖+ 1 1 1 . . . 1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0 0 . . . 0 𝜇𝑖
𝜇𝑖
... 𝑉
𝜇𝑖 𝜇𝑖+ 1
... 𝜇𝑖+ 1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
satisfies 𝐵𝑖𝑃 =𝑃 𝐷1, where 𝐷1 is the (𝑘+ 1)×(𝑘+ 1) diagonal matrix defined previously,𝐷1=𝑑𝑖𝑎𝑔(1, 𝜆1, 𝜆2, . . . , 𝜆𝑘).Here we note that if we expand det𝑃 with respect to the first row, then we get det𝑃 = det Λ. Since Λ is the Vandermonde matrix, the matrix𝑃 is invertible.
Theorem 4. For𝑛 >0and1< 𝑖 < 𝑘, 𝑆(𝑖)𝑛 =𝜇𝑖
⎛
⎝1−
𝑘
∑
𝑗=1
𝑓𝑛𝑗
⎞
⎠−
𝑘
∑
𝑚=𝑖
𝑓𝑛𝑚 and
𝑆𝑛(1)=𝜇1
⎛
⎝1−
𝑘
∑
𝑗=1
𝑓𝑛𝑗
⎞
⎠.
8 EMRAH KILIC AND PANTELIMON ST ˘ANIC ˘A
Proof. Since 𝐵𝑖𝑃 = 𝑃 𝐷1 for 1 < 𝑖 ≤ 𝑘 and the matrix 𝑃 is invertible, we write 𝐵𝑖𝑛𝑃 =𝑃 𝐷1𝑛 and so 𝑌𝑛,𝑖𝑃 =𝑃 𝐷𝑛1. By equating the (2,1) entries of the equality 𝑌𝑛,𝑖𝑃=𝑃 𝐷1𝑛, we have the conclusion.
For the case𝑖= 1,one can see that𝐵𝑃1=𝑃1𝐷1where the (𝑘+ 1)×(𝑘+ 1) matrices 𝐵 and𝑃1are as follows
𝐵=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1 0 . . . 0 1
0 𝐴
... 0
⎤
⎥
⎥
⎥
⎥
⎥
⎦
and𝑃1=
⎡
⎢
⎢
⎢
⎣
1 0 . . . 0 𝜇1
... 𝑉 𝜇1
⎤
⎥
⎥
⎥
⎦ .
By induction on𝑛, we see that
𝑌 =𝐵𝑛=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0 . . . 0
𝑆𝑛(𝑖)
𝑆𝑛−1(𝑖) 𝐺𝑛 ...
𝑆𝑛−𝑘+1(𝑖)
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦ .
Similar to the cases 1< 𝑖≤𝑘, the proof is easily seen for the case𝑖= 1.
As a consequence of Theorem 4, we get 𝑆𝑛 =
𝑛
∑
𝑖=1
𝑓𝑖𝑘= 𝑐𝑘
(∑𝑘
𝑗=1𝑓𝑛𝑗−1) 𝑐1+𝑐2+⋅ ⋅ ⋅+𝑐𝑘−1.
Let𝑉𝑖,𝑗be a𝑘×𝑘matrix obtained from the Vandermonde matrix𝑉 by replacing the𝑗th column of 𝑉 by𝑒𝑖 where𝑉 = Λ𝑇 is defined as in (3.2) and𝑒𝑖 is the 𝑖th element of the natural basis forℝ𝑛,that is,
𝑒𝑖= (0, . . . ,0, 1
↑ 𝑖th
,0, . . .0)𝑇 and
𝑉𝑖,𝑗=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
𝜆𝑘−11 . . . 𝜆𝑘−1𝑗−1 0 𝜆𝑘−1𝑗+1 . . . 𝜆𝑘−1𝑘 𝜆𝑘−21 . . . 𝜆𝑘−2𝑗−1 0 𝜆𝑘−2𝑗+1 . . . 𝜆𝑘−2𝑘
... ... ... ... ...
𝜆𝑘−𝑖+11 . . . 𝜆𝑘−𝑖+1𝑗−1 0 𝜆𝑘−𝑖+1𝑗+1 . . . 𝜆𝑘−𝑖+1𝑘 𝜆𝑘−𝑖1 . . . 𝜆𝑘−𝑖𝑗−1 1 𝜆𝑘−𝑖𝑗+1 . . . 𝜆𝑘−𝑖𝑘 𝜆𝑘−𝑖−11 . . . 𝜆𝑘−𝑖−1𝑗−1 0 𝜆𝑘−𝑖−1𝑗+1 . . . 𝜆𝑘−𝑖−1𝑘
... ... ... ... ...
𝜆1 . . . 𝜆𝑗−1 0 𝜆𝑗+1 . . . 𝜆𝑘
1 . . . 1 0 1 . . . 1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
↑ 𝑒𝑖
.
Let𝑞𝑗(𝑖)= ∣𝑉∣𝑉𝑖,𝑗∣∣.
Theorem 5. For any integer𝑛and1≤𝑖≤𝑘, 𝑓𝑛𝑖 =
𝑘
∑
𝑗=1
𝑞(𝑖)𝑗 𝜆𝑛+𝑘−1𝑗 .
Proof. We consider the following system of 𝑘 linear equations in 𝑘 unknowns 𝑥1, 𝑥2, . . . , 𝑥𝑘:
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
𝜆𝑘−11 𝜆𝑘−12 . . . 𝜆𝑘−1𝑘 ... ... ... 𝜆𝑘−𝑖1 𝜆𝑘−𝑖2 . . . 𝜆𝑘−𝑖𝑘
... ... ... 𝜆1 𝜆2 . . . 𝜆𝑘
1 1 . . . 1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣ 𝑥1
... 𝑥𝑗
... 𝑥𝑘
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣ 0
... 1 ... 0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
| {z }
𝑒𝑖
.
Using Vandermonde’s determinants and Cramer rule, we get 𝑞(𝑖)𝑗 =∣𝑉𝑖,𝑗∣
∣𝑉∣ (𝑖= 1,2, . . . , 𝑘), and so, for 𝑛, 𝑘 > 0 and 1≤ 𝑖 ≤𝑘, 𝑓𝑛𝑖 =∑𝑘
𝑗=1𝑞(𝑖)𝑗 𝜆𝑛+𝑘−1𝑗 , which completes the proof.
Consequently, we extend the result of Theorem 5 to the general order linear recurrences{
𝑡𝑖𝑛}
by the result given by (2.5).
Corollary 4. For any integer𝑛and1≤𝑖≤𝑘, 𝑡𝑖𝑛 =
𝑖
∑
𝑗=1 𝑘
∑
𝑠=1
𝑟𝑖+1−𝑗𝑞(𝑗)𝑠 𝜆𝑛+𝑘−1𝑠 . As an example, we consider the sequence{
𝑇𝑛𝑖} ,
𝑇𝑛𝑖 =𝑇𝑛−1𝑖 + 3𝑇𝑛−2𝑖 +𝑇𝑛−2𝑖 , 𝑛≥2,1≤𝑖≤3 with
𝑇𝑛𝑖 =
{ 1 if𝑖= 1−𝑛,
0 otherwise, for 1−𝑘≤𝑛≤0, displayed in the following table
𝑖∖𝑛 1 2 3 4 5 6 7 8
1 1 4 8 21 49 120 288 697 . . . { 𝑇𝑛1} 2 3 4 13 28 71 168 409 984 . . . {
𝑇𝑛2}
3 1 1 4 8 21 49 120 288 . . . {
𝑇𝑛3}
Table 1
Here we note that𝛾1=−1, 𝛾2= 1 +√
2, 𝛾3= 1−√ 2 and 𝑞1(1)=(𝛾 1
1−𝛾3)(𝛾1−𝛾2), 𝑞2(1)=(𝛾 1
2−𝛾3)(𝛾2−𝛾1), 𝑞(1)3 = (𝛾 1
2−𝛾3)(𝛾1−𝛾3), 𝑞1(2)=−(𝛾 𝛾2+𝛾3
1−𝛾2)(𝛾1−𝛾3), 𝑞2(2)= (𝛾 𝛾1+𝛾3
2−𝛾3)(𝛾1−𝛾2), 𝑞3(2)=−(𝛾 𝛾1+𝛾2
2−𝛾3)(𝛾1−𝛾3), 𝑞1(3)=(𝛾 𝛾2𝛾3
1−𝛾3)(𝛾1−𝛾2), 𝑞2(3)=−(𝛾 𝛾1𝛾3
1−𝛾2)(𝛾2−𝛾3), 𝑞3(3)= (𝛾 𝛾1𝛾2
2−𝛾3)(𝛾1−𝛾3).
10 EMRAH KILIC AND PANTELIMON ST ˘ANIC ˘A
Therefore, by Theorem 5, we get 𝑇𝑛1= 𝛾𝑛+21
(𝛾1−𝛾3) (𝛾1−𝛾2)+ 𝛾𝑛+22
(𝛾2−𝛾3) (𝛾2−𝛾1)+ 𝛾𝑛+23
(𝛾2−𝛾3) (𝛾1−𝛾3), 𝑇𝑛2=− (𝛾2+𝛾3)𝛾𝑛+21
(𝛾1−𝛾2) (𝛾1−𝛾3)+ (𝛾1+𝛾3)𝛾𝑛+22
(𝛾2−𝛾3) (𝛾1−𝛾2)− (𝛾1+𝛾2)𝛾𝑛+23 (𝛾2−𝛾3) (𝛾1−𝛾3) and since𝛾1𝛾2𝛾3= 1,
𝑇𝑛3 = 𝛾2𝛾3𝛾𝑛+21
(𝛾1−𝛾3) (𝛾1−𝛾2)− 𝛾1𝛾3𝛾𝑛+22
(𝛾1−𝛾2) (𝛾2−𝛾3)+ 𝛾1𝛾2𝛾𝑛+23 (𝛾2−𝛾3) (𝛾1−𝛾3)
= 𝛾𝑛+11
(𝛾1−𝛾3) (𝛾1−𝛾2)+ 𝛾𝑛+12
(𝛾2−𝛾1) (𝛾2−𝛾3)+ 𝛾𝑛+13 (𝛾2−𝛾3) (𝛾1−𝛾3)
= 𝑇𝑛−11 .
Observe (from Table 1) that𝑇𝑛3=𝑇𝑛−11 .
4. Generating Functions
In this section we derive the family of generating functions𝐺(𝑖, 𝑥) =∑∞ 𝑛=0𝑓𝑛𝑖𝑥𝑛 for the generalized order-𝑘recurrences{
𝑓𝑛𝑖}
for all𝑖, 1≤𝑖≤𝑘.
Theorem 6. For1≤𝑖≤𝑘, 𝐺(𝑖, 𝑥) =
𝑓0𝑖+∑𝑘−1 𝑚=1
(∑𝑘
𝑣=𝑚+1𝑐𝑣𝑓𝑚−𝑣𝑖 ) 𝑥𝑚 1−𝑐1𝑥−𝑐2𝑥2− ⋅ ⋅ ⋅ −𝑐𝑘𝑥𝑘 . Proof. Let𝐺(𝑖, 𝑥) =𝑓0𝑖𝑥0+𝑓1𝑖𝑥1+𝑓2𝑖𝑥2+⋅ ⋅ ⋅+𝑓𝑛𝑖𝑥𝑛+⋅ ⋅ ⋅ .Consider
(1−𝑐1𝑥−𝑐2𝑥2− ⋅ ⋅ ⋅ −𝑐𝑘𝑥𝑘) 𝐺(𝑖, 𝑥)
=𝑓0𝑖+𝑓1𝑖𝑥+𝑓2𝑖𝑥2+⋅ ⋅ ⋅+𝑓𝑘𝑖𝑥𝑘+⋅ ⋅ ⋅+𝑓𝑛𝑖𝑥𝑛+⋅ ⋅ ⋅
−𝑐1𝑓0𝑖𝑥−𝑐1𝑓1𝑖𝑥2−𝑐1𝑓2𝑖𝑥3− ⋅ ⋅ ⋅ −𝑐1𝑓𝑘−1𝑖 𝑥𝑘− ⋅ ⋅ ⋅ −𝑐1𝑓𝑛−1𝑖 𝑥𝑛− ⋅ ⋅ ⋅
−𝑐𝑘𝑓0𝑖𝑥𝑘−𝑐𝑘𝑓1𝑖𝑥𝑘+1−𝑐𝑘𝑓2𝑖𝑥𝑘+2− ⋅ ⋅ ⋅ −𝑐𝑘𝑓𝑛−𝑘𝑖 𝑥𝑛− ⋅ ⋅ ⋅
=𝑓0𝑖+(
𝑓1𝑖−𝑐1𝑓0𝑖) 𝑥+(
𝑓2𝑖−𝑐1𝑓1𝑖−𝑐2𝑓0𝑖)
𝑥2+⋅ ⋅ ⋅+ (𝑓𝑘−1𝑖 −𝑐1𝑓𝑘−2𝑖 −𝑐2𝑓𝑘−3𝑖 − ⋅ ⋅ ⋅ −𝑐𝑘−1𝑓0𝑖)
𝑥𝑘−1 +(
𝑓𝑘𝑖−𝑐1𝑓𝑘−1𝑖 −𝑐2𝑓𝑘−2𝑖 − ⋅ ⋅ ⋅ −𝑐𝑘−1𝑓0𝑖−𝑐𝑘𝑓1𝑖)
𝑥𝑘+⋅ ⋅ ⋅+ (𝑓𝑛𝑖 −𝑐1𝑓𝑛−1𝑖 −𝑐2𝑓𝑛−2𝑖 − ⋅ ⋅ ⋅ −𝑐𝑘𝑓𝑛−𝑘𝑖 )
𝑥𝑛+⋅ ⋅ ⋅ .
Now we compute the coefficients of𝑥𝑛 of the equation above. From the definition of{
𝑓𝑛𝑖}
, we get
𝑓1𝑖 = 𝑐1𝑓0𝑖+𝑐2𝑓−1𝑖 +⋅ ⋅ ⋅+𝑐𝑘𝑓1−𝑘𝑖 ...
𝑓𝑘−1𝑖 = 𝑐1𝑓𝑘−2𝑖 +𝑐2𝑓𝑘−3𝑖 +⋅ ⋅ ⋅+𝑐𝑘−1𝑓0𝑖+𝑐𝑘𝑓−1𝑖 ...
𝑓𝑛𝑖 = 𝑐1𝑓𝑛−1𝑖 +𝑐2𝑓𝑛−2𝑖 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘𝑖 .
and so
𝑓1𝑖−𝑐1𝑓0𝑖 = 𝑐2𝑓−1𝑖 +⋅ ⋅ ⋅+𝑐𝑘𝑓1−𝑘𝑖 𝑓2𝑖−𝑐1𝑓1𝑖−𝑐2𝑓0𝑖 = 𝑐3𝑓−1𝑖 +⋅ ⋅ ⋅+𝑐𝑘𝑓2−𝑘𝑖
... 𝑓𝑘−1𝑖 −𝑐1𝑓𝑘−2𝑖 −𝑐2𝑓𝑘−3𝑖 − ⋅ ⋅ ⋅ −𝑐𝑘−1𝑓0𝑖 = 𝑐𝑘𝑓−1𝑖 . Then for𝑛≥𝑘,by the definition of{
𝑓𝑛𝑖}
, the coefficients of𝑥𝑛 are all 0.
For example, for fixed𝑘 and 1≤𝑖≤𝑘, we take𝑖= 1. Thus 𝐺(1, 𝑥) =𝑓01𝑥0+𝑓11𝑥1+𝑓21𝑥2+⋅ ⋅ ⋅+𝑓𝑛1𝑥𝑛+⋅ ⋅ ⋅. From the definition of{
𝑓𝑛𝑖}
,the initial conditions of the recurrence{ 𝑓𝑛1}
are given by
𝑓𝑛1=
{ 1 if𝑛= 0,
0 otherwise, for 1−𝑘≤𝑛≤0, which implies
𝐺(1, 𝑥) = 1
1−𝑐1𝑥−𝑐2𝑥2− ⋅ ⋅ ⋅ −𝑐𝑘𝑥𝑘. (4.1) More generally, we derive the generating function of recurrence {
𝑡𝑖𝑛}
, namely 𝑔(𝑖, 𝑥) =∑
𝑘≥0𝑡𝑖𝑘𝑥𝑘.
Corollary 5. For1≤𝑖≤𝑘, 𝑔(𝑖, 𝑥) =
𝑡𝑖0+∑𝑘−1 𝑚=1
(∑𝑘
𝑣=𝑚+1𝑐𝑣𝑡𝑖𝑚−𝑣) 𝑥𝑚 1−𝑐1𝑥−𝑐2𝑥2− ⋅ ⋅ ⋅ −𝑐𝑘𝑥𝑘 .
As an example, if we take 𝑘=𝑖= 2,𝑐1=𝑐2= 1 and𝑟1 =−1, 𝑟2= 0,then the sequence{
𝑡2𝑛} is
1,3,4,7,11,18,29, . . .
which is the well known Lucas sequence{𝐿𝑛}. Then by Corollary 5, we obtain 𝑔(2, 𝑥) =
∞
∑
𝑛=0
𝑡2𝑛𝑥𝑛 =
∞
∑
𝑛=0
𝐿𝑛𝑥𝑛 =𝑡𝑖0−( 𝑡𝑖−1)
𝑥1 1−𝑥−𝑥2
where 𝑡20 =𝑟2 = 2 and𝑡2−1 =𝑟1 = 1. Thus we have the well known result for the Lucas numbers:
∞
∑
𝑛=0
𝐿𝑛𝑥𝑛= 2−𝑥 1−𝑥−𝑥2.
5. 𝑛th powers of a companion and 𝑘-superdiagonal determinants In [8], the author gave a relationship between determinants of certain 𝑛×𝑛 𝑘- superdiagonal matrices and the terms of the𝑛th power of matrix𝐴given by (1.2).
In this section, we derive some new relationships between some Hessenberg deter- minants and the terms of generalized recurrences{
𝑓𝑛𝑖}
for all 1≤𝑖≤𝑘.
12 EMRAH KILIC AND PANTELIMON ST ˘ANIC ˘A
Here, we recall a result of [8]. Define an𝑛×𝑛 𝑘-superdiagonal matrix𝑀𝑛in the following form:
𝑀𝑛 =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
𝑐1 𝑐2 . . . 𝑐𝑘 0
−1 𝑐1 𝑐2 . . . 𝑐𝑘
−1 𝑐1 𝑐2 . . . . .. . .. . . . ...
0 −1 𝑐1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦ .
Lemma 1. For𝑛 >0,
det𝑀𝑛=𝑓𝑛1.
Indeed, expanding det𝑀𝑛 by the elements of the first row gives us
det𝑀𝑛 = 𝑐1det𝑀𝑛−1+𝑐2det𝑀𝑛−2+⋅ ⋅ ⋅+𝑐𝑘det𝑀𝑛−𝑘, (5.1)
= 𝑓𝑛1=𝑐1𝑓𝑛−11 +𝑐2𝑓𝑛−21 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘1 . (5.2) Now we extend the above result for the generalized sequences {
𝑓𝑛𝑖}
for 1 ≤ 𝑖 ≤ 𝑘. For this purpose we introduce some new notations: For 1 ≤ 𝑡 ≤ 𝑘, let 𝑀𝑛(𝑡, 𝑡+ 1, . . . , 𝑘;𝑟) = [ ˆ𝑚𝑖𝑗] denote the matrix obtained from 𝑀𝑛 = [𝑚𝑖𝑗] with
ˆ
𝑚𝑖𝑗 = 0 for 𝑖 ≤ 𝑗 ≤ 𝑟, 𝑖 ∈ {𝑡, 𝑡+ 1, . . . , 𝑘} and otherwise ˆ𝑚𝑖𝑗 = 𝑚𝑖𝑗. Clearly 𝑀𝑛(1,2, . . . , 𝑘; 0) =𝑀𝑛.
Recalling that𝐺𝑛= [𝑔𝑖𝑗] =𝐴𝑛, we give the following theorem for the diagonal elements𝑔𝑗𝑗 =𝑓𝑛−𝑗(𝑗+1).
Theorem 7. For𝑛 > 𝑗 and1≤𝑗 ≤𝑘−1, det𝑀𝑛(1;𝑗) =𝑓𝑛−𝑗𝑗+1 wheredet𝑀𝑛(1; 0) =𝑓𝑛1.
Proof. First consider the case𝑗= 1.If we expand the det𝑀𝑛(1; 1) by the elements of the first row, then
det𝑀𝑛(1; 1) = 0 (det𝑀𝑛−1) +𝑐2det𝑀𝑛−2+⋅ ⋅ ⋅+𝑐𝑘det𝑀𝑛−𝑘
= 𝑐2det𝑀𝑛−2+⋅ ⋅ ⋅+𝑐𝑘det𝑀𝑛−𝑘. By (5.1) and (5.2),
det𝑀𝑛(1; 1) =𝑐2𝑓𝑛−21 +𝑐3𝑓𝑛−31 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘1
=𝑓𝑛1−𝑐1𝑓𝑛−11 =𝑓𝑛−12 . Thus the proof is complete for the case𝑗= 1.
Now, we take the general case for 1 ≤𝑗 ≤𝑘−1. By expanding det𝑀𝑛(1;𝑗) with respect to the first row, we get
det𝑀𝑛(1;𝑗) = det[
0 . . . 0 𝑐𝑗+1 𝑐𝑗+2 . . . 𝑐𝑘 0 . . . 0 ] , which, by (5.1) and (5.2), becomes
det𝑀𝑛(1;𝑗) =𝑐𝑗+1det𝑀𝑛−𝑗−1+𝑐𝑗+2det𝑀𝑛−𝑗−2+⋅ ⋅ ⋅+𝑐𝑘det𝑀𝑛−𝑘
=𝑐𝑗+1𝑓𝑛−𝑗−11 +𝑐𝑗+2𝑓𝑛−𝑗−21 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘1 .
From (5.2) and after repeating𝑗 times the identity (1.4), we get det𝑀𝑛(1;𝑗) =𝑐𝑗+1𝑓𝑛−𝑗−11 +𝑐𝑗+2𝑓𝑛−𝑗−21 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘1
=𝑓𝑛1−𝑐1𝑓𝑛−11 −𝑐2𝑓𝑛−21 − ⋅ ⋅ ⋅ −𝑐𝑗𝑓𝑛−𝑗1
=𝑓𝑛−12 −𝑐2𝑓𝑛−21 −𝑐3𝑓𝑛−31 − ⋅ ⋅ ⋅ −𝑐𝑗𝑓𝑛−𝑗1 . . .
=𝑓𝑛−𝑗+1𝑗 −𝑐𝑗𝑓𝑛−𝑗1 =𝑓𝑛−𝑗𝑗+1, and the proof is complete.
According to the definition of𝑀𝑛(𝑡, 𝑡+ 1, . . . , 𝑘;𝑟),the matrix𝑀𝑛(2,3;𝑛) can be expressed in the compact form
𝑀𝑛(2,3;𝑛) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
𝑐1 𝑐2 . . . 𝑐𝑘 0 . . . 0
−1 0 0 . . . 0 0 . . . 0
−1 0 0 . . . 0 0 . . . 0
−1 𝑐1 𝑐2 . . . 𝑐𝑘 0 . . . 0 . .. . .. . .. . . .. . .. ...
−1 𝑐1 𝑐2 . . . 𝑐𝑘 0
−1 𝑐1 𝑐2 . . . 𝑐𝑘 . .. . .. . . . ...
−1 𝑐1 𝑐2
0 −1 𝑐1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦ .
Theorem 8. For𝑛 > 𝑘+ 2,
det𝑀𝑛+1(2,3, . . . , 𝑘;𝑛) =𝑓𝑛−𝑘+2𝑘 .
Proof. First we consider the case of𝑘= 2,and det𝑀𝑛+1(2;𝑛).The matrix𝑀𝑛(2;𝑛) has the following form:
𝑀𝑛(2;𝑛) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
𝑐1 𝑐2 . . . 𝑐𝑘 0 . . . 0
−1 0 0 . . . 0 0 . . . 0
−1 𝑐1 𝑐2 . . . 𝑐𝑘 0 . . . 0 . .. . .. . .. . . .. . .. ...
−1 𝑐1 𝑐2 ⋅ ⋅ ⋅ 𝑐𝑘 0
−1 𝑐1 𝑐2 . . . 𝑐𝑘
. .. . .. . . . ...
−1 𝑐1 𝑐2
−1 𝑐1
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦ .
Expanding det𝑀𝑛+1(2;𝑛) with respect to the first row, we obtain
det𝑀𝑛+1(2;𝑛) =𝑐2det𝑀𝑛−1+𝑐3det𝑀𝑛−2+⋅ ⋅ ⋅+𝑐𝑘det𝑀𝑛−𝑘+1. Since the first principal subdeterminant include a zero row, by Lemma 1, we write
det𝑀𝑛+1(2;𝑛) =𝑐2𝑓𝑛−11 +𝑐3𝑓𝑛−31 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘+11
=−𝑐1𝑓𝑛1+𝑐1𝑓𝑛1+𝑐2𝑓𝑛−11 +𝑐3𝑓𝑛−31 +⋅ ⋅ ⋅+𝑐𝑘𝑓𝑛−𝑘+11
=−𝑐1𝑓𝑛1+𝑓𝑛+11 .
