Determinantal Representations of Some Classical Recurrent Sequences
Full text
#A97 INTEGERS 25 (2025) DETERMINANTAL REPRESENTATIONS OF SOME CLASSICAL RECURRENT SEQUENCES Taras Goy Faculty of Mathematics and Computer Science, Vasyl Stefanyk Carpathian National University, Ivano-Frankivsk, Ukraine [email protected] Mark Shattuck Department of Mathematics, University of Tennessee, Knoxville, Tennessee [email protected] Received: 10/8/24, Accepted: 10/5/25, Published: 11/5/25 Abstract In this paper, we find multi-sum expressions for several second-order recurrent sequences including the Fibonacci, Lucas, Pell, and Jacobsthal numbers. These expressions may also be written equivalently as Toeplitz–Hessenberg determinant identities involving the Oresme numbers. We obtain these formulas as special cases of more general results for the Horadam numbers involving a class of determinants and their associated generating functions. We also find a criterion for determining when a generic Horadam sequence can be expressed explicitly as a determinant of a Toeplitz–Hessenberg matrix with associated sequence ai= (bi +c)difor i≥1. Finally, we provide combinatorial proofs of several of our identities for the Fibonacci numbers and others, wherein we enumerate certain structures featuring (m+r)-color compositions of nfor various r. 1. Introduction We first recall some well-known combinatorial sequences. The Fibonacci, Lucas, Pell, Pell–Lucas, and Jacobsthal number sequences are denoted by Fn,Ln,Pn,Qn, and Jnand are given, respectively, as follows for n≥0: Fn:F0= 0, F1= 1 and Fn=Fn−1+Fn−2, Ln:L0= 2, L1= 1 and Ln=Ln−1+Ln−2, Pn:P0= 0, P1= 1 and Pn= 2Pn−1+Pn−2, Qn:Q0=Q1= 2 and Qn= 2Qn−1+Qn−2, DOI: 10.5281/zenodo.17535257
INTEGERS: 25 (2025) 2 Jn:J0= 0, J1= 1 and Jn=Jn−1+ 2Jn−2, where each recurrence applies for all n≥2. See, respectively, entries A000045, A000032, A000129, A002203, and A001045 in the OEIS [16] for further information on these sequences. In [11], the following multi-sum expressions were obtained for the Fibonacci and Pell numbers. Proposition 1. For n≥1, the following formulas hold: F2n=X s1,...,sn≥0 s1+2s2+···+nsn=n mn(s) 1s12s2···nsn,(1) F3n−1= 2n−1·X s1,...,sn≥0 s1+2s2+···+nsn=n mn(s)1 1s13 2s2 ···2n−1 2n−1sn ,(2) Pn−1= 2n−1·X s1,...,sn−1≥0 2s1+3s2+···+nsn−1=n mn−1(s)1 2s12 4s2 ···n−1 2n−1sn−1 ,(3) where mn(s) = s1+···+sn s1,...,sn=(s1+···+sn)! s1!···sn!. In this paper, we extend these results by finding some further identities involving Fnand Pnas well as formulas for Ln,Qn, and Jn. We remark that these formulas can be obtained as special cases of more general results involving the Horadam sequence. Let On=n 2n,n≥0, denote the n-th Oresme number, which is given recursively by On=On−1−1 4On−2,n≥2, with O0= 0 and O1=1 2. We refer the reader to [6, 13] for further properties of On. It will be seen that our multi-sum formulas for the sequences above may be expressed as determinants of certain Toeplitz–Hessenberg matrices with Oresme number entries (see Corollary 4 below). Other recent results have been given for Toeplitz–Hessenberg matrices whose nonzero entries are derived from various combinatorial sequences, among them, the Catalan [7], Fibonacci [8], Motzkin [9], and Leonardo [10] numbers. Let vn=vn(p, q, r, s) denote the n-th Horadam number (see, e.g., [12]) defined recursively by vn=rvn−1+svn−2for n≥2, with v0=pand v1=q, where p, q, r, s are variables. We will determine a general explicit formula (Theorem 1) in terms of determinants for vnwhose parameters satisfy a certain restriction. We consider further the special case of vnwhen r=s= 1, known as the Gibonacci numbers, which will be denoted here by Gnas in [4]. That is, the numbers Gnsatisfy the recursion Gn=Gn−1+Gn−2for n≥2, with G0=pand G1=q. Note that Gn reduces to Fnand Lnwhen (p, q) = (0,1) and (2,1), respectively. The organization of this paper is as follows. In the next section, we find explicit determinantal expressions for several specific second-order recurrent sequences as
INTEGERS: 25 (2025) 3 well as a general formula for a class of Horadam sequences. Formulas in these specific cases are subsequently expressed equivalently as Oresme number determinant identities. In the third section, we establish a determinantal expression for the sequence kGn+mfor n≥1, where kis a constant (dependent upon m,G0, and G1) and m≥0 is fixed, which is subsequently generalized (Theorems 2 and 3). Further, it is shown that among all sequences of the form Fℓn+mfor n≥0, where ℓ≥1 and m≥0 are fixed, only the sequences Fn+3 and F2nadmit an expression as a determinant of a Toeplitz–Hessenberg matrix with associated sequence ai= (bi +c)di for i≥1 (see Proposition 2). In the final section, we provide combinatorial arguments of several of our multisum formulas utilizing structures that incorporate (m+r)-color compositions as well as certain types of square-and-domino tilings. We prove our results by direct enumeration, either in establishing a defining recurrence relation or providing a bijection between some pertinent discrete structures. In one case, a result is proven by first defining a suitable sign-changing involution and then enumerating the set of survivors of the involution. Recall that the number of (m+ 1)- and (m+3)-color compositions of nare given by A003480(n) and A010908(n−1), respectively. As a consequence of our arguments for (11) and (14) in the last section, we obtain, via combinatorial proofs, new formulas for these sequences as follows: A003480(n) = (2(n−1)/2Pn+1, n odd; 2(n−4)/2Qn+1, n even, and A010908(n)=2n−1F2n+6 for n≥1. We remark that different expressions for these sequences were found in [5] which involve a double summation. 2. Determinantal Representations of Recurrent Sequences An n×nmatrix Anof the form An:= An(a0;a1, . . . , an) = a1a00··· 0 0 a2a1a0··· 0 0 ··· ··· ··· ...··· ··· an−1an−2an−3··· a1a0 anan−1an−2··· a2a1 ,(4) where a0= 0, is said to be Toeplitz–Hessenberg (see, e.g., [15]). The determinant of Anis given explicitly in terms of the aias follows. Lemma 1. If n≥1, then det(An) = X eα=n (−a0)n−|α|mn(α)aα1 1aα2 2···aαn n,(5)
INTEGERS: 25 (2025) 4 where the sum is over all n-tuples α= (α1, . . . , αn)of non-negative integers such that eα=α1+ 2α2+···+nαn=n, with |α|=α1+···+αnand mn(α) = |α|! α1!···αn!. The preceding result is known as Trudi’s formula [14, Theorem 1], the a0= 1 case of which has been attributed to Brioschi [15]. Define the generating functions f(x) = X n≥1 det(An)xnand g(x) = X i≥1 aixi, where Anis of the form in (4). Using (5), one can show the following relation between f(x) and g(x), see [10]. Lemma 2. We have f(x) = −1 a0g(−a0x) 1 + 1 a0g(−a0x).(6) Given n≥1 and indeterminates a,b,c, and d, let Un=Un(a, b, c, d) be the n×nToeplitz–Hessenberg matrix wherein a0=aand ai= (bi +c)difor i≥1. Let un=un(a, b, c, d) denote the determinant of the matrix Unfor n≥1. Remark 1. Even though one may take d= 1 in unwithout loss of generality, due to the easily verified relation un(a, b, c, d) = un(ad, bd, cd, 1) for n≥1, it will often be convenient to retain the dparameter. For example, this often leads to nicer determinantal expressions for recurrent sequences as well as allowing one to see certain special cases more readily (see, e.g., the proofs of Corollaries 1 and 2 below). Further, since we also have un(a, b, c, d) = un(1, b/a, c/a, ad) = permUn(1,−b/a, −c/a, −ad), one can obtain formulas if desired for the recurrent sequences below as determinants or permanents, respectively, of Toeplitz–Hessenberg matrices with unit superdiagonal entries. Define the generating function u(x) = P n≥1 unxn. Then u(x) has the following explicit formula. Lemma 3. We have u(x) = dx(b+c+acdx) 1 + d(2a−b−c)x+ad2(a−c)x2.(7) Proof. Note first that X i≥1 aixi=X i≥1 (bi +c)dixi=bdx (1 −dx)2+cdx 1−dx =dx(b+c−cdx) (1 −dx)2.
INTEGERS: 25 (2025) 5 By (6), we then have u(x) = dx(b+c+acdx) (1+adx)2 1−dx(b+c+acdx) (1+adx)2 =dx(b+c+acdx) 1 + d(2a−b−c)x+ad2(a−c)x2, as desired. Using (7), we obtain the following explicit formula involving the Fibonacci and Lucas numbers. Corollary 1. If n≥1, then X eα=n mn(α)1α13α2···((n+ 1)2n−2)αn=(5(n−1)/2Fn+1, n odd; 5(n−2)/2Ln+1, n even.(8) Proof. Note first that (8) may be written equivalently as X eα=n mn(α)1 √5α13 5α2 ···(n+ 1)2n−2 √5nαn =(1 √5Fn+1, n odd; 1 5Ln+1, n even, (9) since α1+2α2+···+nαn=nfor all n-tuples α= (α1, . . . , αn) under consideration in the sum. By Lemma 1, the left side of (9) is given by un−1,1/4,1/4,2/√5 for each n≥1. Taking a=−1, b=c= 1/4, and d= 2/√5 in Lemma 3, the left side of (9) then has generating function α(x) := x(√5−x) 5(1 −√5x+x2). Considering the odd and even parts of α(x), and computing α(x)∓α(−x) 2, we have α(x) = x √5(1 −3x2+x4)+x2(4 −x2) 5(1 −3x2+x4)=1 √5X n≥1 F2nx2n−1+1 5X n≥1 L2n+1x2n, where in the second equality we have made use of the facts X n≥1 F2nxn=x 1−3x+x2and X n≥1 L2n+1xn=x(4 −x) 1−3x+x2. This implies (9) and hence (8). We have the following comparable formulas involving the Pell and Pell–Lucas numbers.
INTEGERS: 25 (2025) 6 Corollary 2. If n≥1, then X β∗=n mn−1(β)1β1(2√2)β2···((n−1)√2n−2)βn−1=(√2Pn−1, n odd; 1 2Qn−1, n even,(10) X eα=n mn(α)(√2)α13 2α2 ···n+ 1 √2nαn =(1 √2Pn+1, n odd; 1 4Qn+1, n even,(11) where the first sum is over all (n−1)-tuples β= (β1, . . . , βn−1)of non-negative integers such that β∗= 2β1+ 3β2+···+nβn−1=n. Proof. Note first that the left side of (10) may be written as X eα=n mn(α)0α11α2(2√2)α3···((n−1)√2n−2)αn, and hence, by (5), is given by un(−1,1/2,−1/2,√2) for n≥1. By (7), we have δ(x) := X n≥1 un−1,1/2,−1/2,√2xn=x2 1−2√2x+x2. Considering the odd and even parts of δ(x) yields δ(x) = 2√2x3 1−6x2+x4+x2(1 + x2) 1−6x2+x4=√2X n≥1 P2n−2x2n−1+1 2X n≥1 Q2n−1x2n, which implies (10), where we have used the facts X n≥1 P2nxn=2x 1−6x+x2and X n≥1 Q2n−1xn=2x(1 + x) 1−6x+x2. A comparable proof may be given for (11), upon observing that the left side of (11) is given by un(−1,1,1,1/√2) for n≥1, and hence has generating function x(2√2−x) 2(1−2√2x+x2). Let vn=vn(p, q, r, s) denote the Horadam sequence given by vn=rvn−1+svn−2 for n≥2, with v0=pand v1=q. Then we have the following general representation of vn. Theorem 1. Let p,q,r,sbe complex numbers with (q−r)2= 4s(p−1) = 0. If vn=vn(p, q, r, s)denotes the corresponding Horadam sequence, then vn=X eα=nr−q 2n−|α|mn(α) n Y i=1 q+2ps r−qi−2ps r−qαi , n ≥1.(12) Conversely, the sequence vndefined by (12) for all n≥1satisfies vn=rvn−1+svn−2 for n≥3.
INTEGERS: 25 (2025) 7 Proof. To show (12), we first seek a,b,c,dsuch that vn=un(a, b, c, d) for all n≥1. In order for this to hold, we need the corresponding equality of generating functions, i.e., v(x) = u(x), where v(x) = X n≥1 vnxn=x(q+psx) 1−rx −sx2 and u(x) is given by (7). This leads to the following system of equations in the unknowns a,b,c,d: (i)d(b+c) = q, (ii)acd2=ps, (iii)d(b+c−2a) = r, (iv)ad2(c−a) = s, where p,q,r,sare fixed. Subtracting equation (iii) from (i), and also (iv) from (ii), gives 2ad =q−rand (ad)2=ps −s. Since (q−r)2= 4s(p−1), by assumption, these last two equations are equivalent to one another. From ad =q−r 2= 0, we then get cd =ps ad =2ps q−rand bd =q−cd =q2−rq −2ps q−r. Note that once d= 0 is specified, then a, b, c are uniquely determined. That is, for d= 0, we have vn=un(a, b, c, d) = unq−r 2d,q2−rq −2ps d(q−r),2ps d(q−r), d, n ≥1. Hence, by (5), we get vn=X eα=n (−a)n−|α|mn(α) n Y i=1 (bi +c)diαi =dnX eα=nr−q 2dn−|α|mn(α) n Y i=1 q2−rq −2ps d(q−r)i+2ps d(q−r)αi =X eα=nr−q 2n−|α|mn(α) n Y i=1 q+2ps r−qi−2ps r−qαi , which yields (12). Conversely, suppose vnfor n≥1 is the sequence defined by (12), where p,q,r,s are as stated above. By (5), we have vn=un(a, b, c, d), where a=q−r 2,b=q−2ps q−r, c=2ps q−r, and d= 1. Applying (7) yields X n≥1 vnxn=x(q+psx) 1−rx +q−r 2q−r 2−2ps q−rx2=x(q+psx) 1−rx −sx2, upon making use of the assumption (q−r)2= 4s(p−1). The last equality above implies vn=rvn−1+svn−2for n≥3, which completes the proof.
INTEGERS: 25 (2025) 8 Taking specific cases of Theorem 1 yields determinantal representations of several second-order recurrent sequences. Corollary 3. If n≥1, then X eα=n mn(α)3α1(−4)α2···((−1)n−1(n+ 2))αn=Fn+3,(13) X eα=n mn(α)2α15 4α2 ···n+ 3 2nαn =1 4F2n+4,(14) X eα=n mn(α)6α1(−10)α2···((−1)n−1(4n+ 2))αn= 2F3n+1,(15) X eα=n mn(α)5α1(−14)α2···((−2)n−1(2n+ 3))αn=Jn+3,(16) X eα=n mn(α)1α14α2···(n2n−1)αn=J2n,(17) X eα=n mn(α)4α18α2···(4n)αn= 2P2n.(18) Proof. To show (13)–(18), we apply (12) to vn=vn(p, q, r, s), where (p, q, r, s) = (2,3,1,1),(3/4,2,3,−1),(2,6,4,1),(3,5,1,2),(0,1,5,−4),(0,4,6,−1). Note that (q−r)2= 4s(p−1) = 0 for each quadruple (p, q, r, s). Applying (12) in each case then yields (13)–(18), respectively. Remark 2. If (q−r)2= 4s(p−1), then the proof of Theorem 1 shows that the Horadam sequence vn(p, q, r, s) does not have the representation (12) for n≥1 as the system of equations (i)–(iv) is not consistent in this case. On the other hand, if (q−r)2= 4s(p−1) = 0 with s= 0, then one must have ad = 0 in the system (i)–(iv) above. But a= 0 is not possible since vnsatisfies a recurrence of second, but not first, order as s= 0. Also, d= 0, for otherwise vn= 0 for all n≥1. Thus, vnfails to have the form in (12) if (q−r)2= 4s(p−1) = 0 with s= 0 (note that if s= 0 and q=r, then trivially one has vn=un(0,0, q, 1) for n≥1). For additional examples of Theorem 1, note that vn=F2n, 21−nF3n−1, and 21−nPn−1 are Horadam sequences with (p, q, r, s) = (0,1,3,−1), (2,1,2,1/4), and (2,0,1,1/4), respectively, where in each case, we have (q−r)2= 4s(p−1) = 0. Applying (12) then yields (1)–(3) above, which were shown in [11] by a different method. One can also express the identities in the corollaries of this section equivalently as Toeplitz–Hessenberg determinant formulas involving the Oresme numbers. For other Oresme determinant formulas, see [11].
INTEGERS: 25 (2025) 9 Corollary 4. If n≥1, then det(−2; O2, O3, . . . , On+1) = (5(n−1)/2 2nFn+1, n odd; 5(n−2)/2 2nLn+1, n even,(19) det(−4; O0, O1, . . . , On−1) = (2(n+1/2)Pn−1, n odd; 2(n−2/2)Qn−1, n even,(20) det(−1/2; O2, O3, . . . , On+1) = (2−(3n+1)/2Pn+1, n odd; 2−(3n+4)/2Qn+1, n even,(21) det(1/4; O3, O4, . . . , On+2)=2−3nFn+3,(22) det(−1/8; O4, O5, . . . , On+3)=2−(3n+2)F2n+4,(23) det(1/4; O3, O5, . . . , O2n+1) = 2−(4n−1)F3n+1,(24) det(1/4; O5, O7, . . . , O2n+3) = 2−5nJn+3,(25) det(−2; O1, O2, . . . , On)=2−nJ2n,(26) det(−1/4; O1, O2, . . . , On)=2−(3n−1)P2n.(27) Proof. We provide proofs of (19) and (22). Similar arguments may be given for the others using (10), (11), and (14)–(18), respectively. Dividing both sides of (8) by 2n, rearranging factors somewhat, and noting α1+ 2α2+···+nαn=nfor all n-tuples αunder consideration in the sum yields X eα=n 2n−|α|mn(α) n Y i=1 i+ 1 2i+1 αi =(5(n−1)/2 2nFn+1, n odd; 5(n−2)/2 2nLn+1, n even. The left side of the last identity is det(−2; O2, . . . , On+1), by (5), which gives (19). Dividing both sides of (13) by 23nyields X eα=n−1 4n−|α|mn(α) n Y i=1 i+ 2 2i+2 αi = 2−3nFn+3, whose left side is given by det(1/4; O3, . . . , On+2), which implies (22). 3. Further Results We start this section with the following general representation for translates of the Gibonacci sequence. Theorem 2. Let Gndenote the Gibonacci sequence with y=G0and z=G1, where yand zare non-negative integers, not both zero. Let m≥3be fixed. Then we have
INTEGERS: 25 (2025) 16 Thus, we have that kGℓn+mis a good Horadam sequence if and only if kis given by (39), in which case kGℓn+m=vn(p, q, r, s), with (p, q, r, s) =Gm(LℓGℓ+m−2(−1)ℓGm±2E) G2 ℓ+m ,LℓGℓ+m−2(−1)ℓGm±2E Gℓ+m , Lℓ,(−1)ℓ+1. Substituting now into (12), and proceeding as before in the simplification, yields (35). We now show that if m≥ℓ+ 2, then both choices of sign yield a valid identity in (35). First of all, we must have Gℓ+m= 0; otherwise, one could not apply the quadratic formula in ascertaining kand the expressions in (35) and (39) would contain a discontinuity. In order for Gℓ+mto be zero, where y, z are non-negative and not both zero, with ℓ≥1 and m≥0, we must have ℓ= 1, m= 0, and z= 0. Note that this case would technically not apply for m≥ℓ+ 2, i.e., the factor Gℓ+m would always be nonzero for such ℓand m. From Theorem 1, in order to apply (12) to kGℓn+min deriving (35), we have that the common value of both sides of the equality must be nonzero in the necessary (and sufficient) condition for kgiven by (kGℓ+m−Lℓ)2= 4(−1)ℓ+1(kGm−1). Thus, in order to demonstrate that both choices of sign yield a valid identity in (35) when m≥ℓ+ 2, it suffices to show that for both of the possibilities for kin (39), we have k=Lℓ/Gℓ+m. Note that k=Lℓ/Gℓ+mif and only if (−1)ℓ+1Gm±E= 0, which is seen to introduce division by zero in (35). So it is enough to show that the equality (−1)ℓ+1Gm=±E(40) cannot hold if m≥ℓ+ 2. To do so, first note that if the radicand in Eis negative, then (40) clearly cannot hold, so we assume that the radicand is non-negative. Thus, it is enough to show G2 m> E2,(41) for m≥ℓ+ 2 when Eis a (non-negative) real number. We consider cases on the parity of ℓ, first assuming ℓis odd. If mis odd, by the stated formula for E, we have that (41) holds if and only if G2 m−z2> Gℓ+1(zLℓ−Gℓ+1). Since yand z are non-negative, it follows that Gmis increasing in mfor fixed values of yand z. Therefore, to demonstrate the last inequality for all odd m≥ℓ+ 2, we only need to consider the case where m=ℓ+ 2. Then we must establish (Gℓ+2 +z)(Gℓ+2 −z)> Gℓ+1(zLℓ−Gℓ+1).(42) Note (42) clearly holds if z= 0 since y > 0 in this case, and hence we may assume z > 0. Further, we have zLℓ−Gℓ+1 =z(Fℓ+1 +Fℓ−1)−(yFℓ+zFℓ+1) = zFℓ−1−yFℓ, ℓ ≥1.
INTEGERS: 25 (2025) 17 Then z > 0 implies Gℓ+2 +z > Gℓ+1 >0 and Gℓ+2 −z=yFℓ+1 +z(Fℓ+2 −1) >|zFℓ−1−yFℓ|, ℓ ≥1. Thus, upon comparing the respective left and right factors of the two sides, one obtains (42). If mis even, then (41) is equivalent to G2 m−y2> Gℓ(yLℓ−Gℓ). Then m≥ℓ+ 2 and meven implies in fact m≥ℓ+ 3, and it is enough to show the last inequality when m=ℓ+ 3, which can be done in a similar manner as before. A comparable proof, which we omit, based on cases with regard to the parity of m may be given for (41) when ℓis even, which completes the proof of (41). Thus, we have that (40) cannot hold for all ℓ≥1 and m≥ℓ+ 2, as desired. Further, if ℓ≥2, then one can show that LℓGℓ+m+ 2(−1)ℓ+1Gm±2E > 0 in all cases when Eis real, and hence this factor is always nonzero in (35) for such ℓ. If ℓ= 1, then this factor is zero only when m=z= 0 and minus is chosen, but this case is already covered by the prior considerations given for the Gℓ+mfactor. Thus, division by zero in (35) can only occur when 0 ≤m≤ℓ+ 1 in certain cases where yand zare such that Gℓ+m((−1)ℓ+1Gm±E) is zero. This implies the final statement in Theorem 3 and completes the proof. The second statement in Theorem 3 is also seen to apply to the identities in (35) for fixed ℓand m, where there is only a single identity of the stated form in cases where a choice of one of the signs leads to division by zero. Taking ℓ= 1 in (35) is seen to yield (28). Taking ℓ= 2 in (35) gives the following explicit formulas for the Gibonacci half-sequences G2n+mfor a fixed m. Corollary 6. For each m≥4fixed, there is the following pair of identities for all n≥1: G2n+m=(Gm+3 +Gm+1 ±2F)n−1 Gn−2 m+2(−Gm±F)n ×X eα=n−(−Gm±F)2 Gm+3 +Gm+1 ±2Fn−|α|mn(α) n Y i=1 (±Fi −Gm)αi, (43) where F=p(−1)m+1(y2+yz −z2)with y=G0,z=G1. Further, if 0≤m≤3, then both identities in (43) hold except in the following cases where only the negative choice of sign leads to a valid expression: (i)m= 0 and 2y=z, (ii)m= 1 and y=z, (iii)m= 2 and y= 0, or (iv)m= 3 and z= 0. Taking (y, z) = (0,1) or (2,1) in (43) gives analogues of the formulas from Corollary 5 for the Fibonacci and Lucas half-sequences.
INTEGERS: 25 (2025) 18 4. Combinatorial Proofs In this section, we provide combinatorial arguments for most of the formulas from Corollaries 2 and 3 above as well as for the prior identity (3), which was shown in [11] by an algebraic argument. To do so, we will enumerate several structures involving (m+r)-color compositions of n. Recall that a composition of a positive integer nis a sequence of positive integers, called parts, whose sum is n. Given a non-negative integer r, an (m+r)-color composition of nis one in which a part of size afor each a≥1 is assigned one of a+rcolors. This color is often denoted by a subscript on the part in question. Thus, an (m+r)-color composition πmay be represented as π= ((a1)b1,...,(ak)bk) for some k≥1, where ai≥1 for 1 ≤i≤k with Pk i=1 ai=nand bi∈[ai+r] for each i. The notion of an m-color composition was introduced in [1] and has been an ongoing object of study. See [5], where (am +b)-color compositions were studied for fixed aand b. Let Cndenote the set of m-color compositions of n. A fundamental result (see, e.g., [1]) states that the cardinality of Cnis given by F2nfor all n≥1. We will also make use of linear tiling structures in several of our proofs below. By a tile, we mean a 1 ×mrectangular piece for some m≥1 capable of covering mconsecutive positions. Squares and dominos correspond to 1 ×1 and 1 ×2 tiles, which will be denoted by sand d, respectively. A covering of the numbers 1,2, . . . , n, written in a row, by non-overlapping squares and dominos is referred to as a square-and-domino tiling of length n, the set of which will be denoted here by Fn. Recall that |Fn|=Fn+1 for all n≥0; see, e.g., [4, Chapter 1]. Note that members of Fnmay be viewed as sequences of n−2msquares and mdominos for some 0 ≤m≤ ⌊n/2⌋, or equivalently as compositions of nwhose parts belong to {1,2}. We start with a combinatorial argument for the first identity in Corollary 2. Proof of (10).We first consider the even case of (10), which may be written equivalently as Qn−1=X β∗=n 2n+2 2−|β|mn−1(β)1β12β2···(n−1)βn−1, n ≥2 even,(44) where the sum is over all β= (β1, . . . , βn−1) such that β∗= 2β1+···+nβn−1=n. One may verify (44) in the cases when n= 2 or 4, so assume n≥6. Let dkdenote the right-hand side of (44) where n= 2kfor k≥1. To establish (44), it suffices to show dk= 6dk−1−dk−2for k≥3, as the two sides agree when k= 1,2. Let C′ n denote the set of m-color compositions of nin which no parts with subscript one are allowed. Given λ∈ C′ n, suppose that the vector recording the multiplicities of the part sizes of λis given by βfor some βsuch that β∗=n. That is, for each i∈[n−1], there are exactly βiparts of size i+ 1 in the composition λ. For each λ, define Sλto be the set of binary words of length n+2 2−Pn−1 i=1 βi. Let Dkdenote
INTEGERS: 25 (2025) 19 the set of all ordered pairs (λ, ω), where λ∈ C′ 2kand ω∈Sλ. Then it is seen that dk=|Dk|for all k≥1. Using this combinatorial interpretation for dk, we will establish the recurrence stated above for dk. To do so, first consider appending the (colored) part 22to λ′in x′= (λ′, ω′)∈ Dk−1to obtain x= (λ, ω)∈ Dkwherein λends in 22. Note that we take ω=ω′ since the difference k−Pi≥1βiis maintained in going from λ′to λ, as both kand Pi≥1βiare increased by one in this case. This yields dk−1possibilities for such x. Now consider adding two to the final part of λ′, but not its subscript, and then appending 0 or 1 to ω′to obtain xfrom x′. Note that adding 0 or 1 to ω′is required in this case since the difference k−Pi≥1βiwith regard to x′is increased by one by such an operation on λ′, as kincreases by one (i.e., nincreases by two), but the number of parts remains the same. This then yields 2dk−1members x∈ Dk wherein the final part of λexceeds its subscript by at least two. Now suppose λwithin x= (λ, ω)∈ Dkhas final part ab, where a≥3 and b=a or a−1. We must show that such members xwithin Dknumber 3dk−1−dk−2. To do so, first let Jand Ldenote two copies of the set Dk−1. Let x′= (λ′, ω′)∈J. If the final part of λ′is at least 3, and not aafor some a, then reduce the final part, but not its subscript, by one and append 32to λ′. On the other hand, if the final part is aafor some a≥2, then replace the final part of λ′with (a+ 2)a+2. In the latter case, we also add 0 to the end of ω′to obtain xfrom x′. If x′∈K, then we perform comparable operations as before, but append 33to λ′, instead of 32, if the final part of λ′is not aa, and add 1 to the end of ω′, instead of 0, in cases when it is. Let Sdenote the subset of Dkconsisting of those (λ, ω) wherein the final part absatisfies a≥4 with b=a−1. At this point, all the members of Dk−Shave been enumerated, and are seen to have cardinality 5dk−1, so to complete the proof of the recurrence for dk, we must show |S|=dk−1−dk−2. To do so, first note that there are dk−1−2dk−2members (λ′, ω′)∈ Dk−1in which the final part of λ′ is cd, where c=d= 2 or c≥3 with d=cor c−1, by subtraction. To see this, take any (ρ, α)∈ Dk−2, increase the final part of ρby two, leaving its subscript unchanged, and then append 0 or 1 to αto obtain the excluded members of Dk−1 accounted for by the subtracted term. To each (λ′, ω′)∈ Dk−1as described, we replace the final part cdof λ′with (c+ 2)c+1 and either append 1 to ω′if c≥3 with d=c−1 or append 0 to ω′if c=d≥2. Note that this yields uniquely all members of S−S′, where S′consists of those (λ, ω)∈Ssuch that λhas final part 43and ωends in 1, and hence |S−S′|=dk−1−2dk−2. Further, |S′|=dk−2, upon considering an arbitrary (ρ, α)∈ Dk−2and appending 43to ρand 1 to α. This implies |S|=dk−1−dk−2, and hence uk= 6uk−1−uk−2for k≥3, as desired, which completes the proof of (44). A similar proof may be given for the odd case
INTEGERS: 25 (2025) 20 of (10), rewritten as Pn−1=X β∗=n 2n−1 2−|β|mn−1(β)1β12β2···(n−1)βn−1, n ≥1 odd, where βis as before. Proof of (11).We first prove the odd case of (11), written equivalently as 2(n−1)/2Pn+1 =X eα=n mn(α)2α13α2···(n+ 1)αn, n ≥1 odd,(45) where the sum is over all α= (α1, . . . , αn) such that eα=α1+ 2α2+···+nαn=n. One may verify (45) when n= 1 or 3, so assume n≥5. Note that bn=P2nimplies bn= 6bn−1−bn−2for n≥3, and hence 2n−1bn= 12(2n−2bn−1)−4(2n−3bn−2). We denote the right-hand side of (45) by ekwhere n= 2k−1 for k≥1. To establish (45), it thus suffices to show ek= 12ek−1−4ek−2for k≥3. Let Endenote the set of (m+1)-color compositions of n. Then it is seen that the right side of (45) equals |En|. Using the combinatorial interpretation ek=|E2k−1|for k≥1, we will show that eksatisfies the recurrence stated above. First, note that there are clearly 4ek−1members of Enwhose last two parts are 1a,1a′, where a, a′∈ {1,2}, and also 3ek−1members ending in 2b, where b∈ {1,2,3}. Further, upon increasing the final part of an arbitrary member of En−2by one, but not its subscript, and subsequently appending 1a, we have that there are 2ek−1members of Enwhose last two parts are (c+1)d,1a, where c≥1 and d∈[c+1]. Note that this misses compositions with endings of the form (c+ 1)c+2,1a, which will be accounted for below. Finally, upon increasing the last part of a member of En−2by two, and leaving the subscript unchanged, we have that there are ek−1 members of Enwhose last part is of the form (x+ 2)y, where x≥1 and y∈[x+ 1]. At this point, we have found |En−T|= 10ek−1, where Tis the subset of En whose members have final part zzor zz+1 for some z≥3 or whose final two parts are (c+ 1)c+2,1a, where c≥1. Thus, to complete the proof of the recurrence for ek, we must show |T|= 2ek−1−4ek−2for k≥3. To do so, let Rdenote the subset of En−2whose members have final part xxor xx+1 for some x≥1. Note that |R|=ek−1−2ek−2, by subtraction, upon excluding members of En−2ending in 21 or (x+ 2)y, where y∈[x+ 1]. We thus need to show |T|= 2|R|. To do so, let Jand Kdenote two copies of the set R. Let δdenote the final part of a member of Jor K. In members of J, we increase both δand its subscript by two to obtain all members of Tending in zzor zz+1 for some z≥3. In members of K, if δ=xx, then we replace δwith the two parts (x+1)x+2,11, whereas if δ=xx+1, then we replace δwith (x+1)x+2,12. One then obtains the remaining members of Tin this way, which establishes the desired formula for |T|. This completes the proof of the recurrence for ek, and hence of
INTEGERS: 25 (2025) 21 (45) as well. Rewriting the even case of (11) as 2(n−4)/2Qn+1 =X eα=n mn(α)2α13α2···(n+ 1)αn, n ≥2 even, and proceeding as before, we complete the proof of (11). Proof of (13).Let Gndenote the set of (m+ 2)-color compositions of n. Let µ(λ) denote the number of parts of λ∈ Gnand define the sign of λas (−1)n−µ(λ). Then it is seen that (13) may be written equivalently as Fn+3 =X λ∈Gn (−1)n−µ(λ), n ≥1.(46) To show (46), we define a sign-changing involution on Gnwhose set of survivors has sum of signs given by Fn+3. In order to do so, let π∈ Gnbe represented sequentially and consider occurrences of one of the following four types involving a part or pair of parts of the stated form, where a≥2 and c≥1: (i)ab,with b∈[a+ 1],(ii)cd,11,with d∈[c+ 2],(iii)aa+2,or (iv)cc+2,13. First, suppose πcontains (i) or (ii) and consider the rightmost occurrence of (i) or (ii) within π. If this rightmost occurrence is a case of (i), then replace the part ab, where a≥2 and b∈[a+ 1], with the two parts (a−1)b,11, and vice versa if (ii), merging the two parts in question into a single part of the form (i). Note that both operations just described reverse the sign since the number of parts of a member of Gnchanges by one in each case. Now suppose πfails to contain (i) or (ii), but contains at least one occurrence of (iii) or (iv). If the rightmost occurrence of either (iii) or (iv) corresponds to a case of (iii), then replace aa+2 where a≥2 with (a−1)a+1,13, and vice versa, merging the two parts in question, if the occurrence corresponds to (iv). Again, these operations reverse the sign for all πfor which they are defined. Combining the two preceding pairs of operations then defines a sign-reversing involution θon all members of Gnwhich witness at least one of (i)–(iv). In particular, note that applying the second pair of operations to members of Gnwhich are free of (i) and (ii) does not introduce an occurrence of (i) or (ii). Let G′ ndenote the subset of Gnfor which θis not defined. One may verify that members of G′ nconsist exclusively of parts of size 1 subject to the following restrictions: (i) the part 11can only occur at the very beginning, if at all, and (ii) each part 13must be preceded by 11or 12,or occur at the very beginning. Note that each member of G′ nhas positive sign, consisting only of parts of size one, and thus we seek |G′ n|. To determine |G′ n|, first suppose ρ∈ G′ ndoes not start
INTEGERS: 25 (2025) 22 with 11. Then ρis a sequence of length nconsisting of the parts 12and 13such that no two parts 13are adjacent. Such sequences are seen to be in one-to-one correspondence with subsets of [n] containing no two adjacent elements. It follows then from [17, p. 46, Exercise 14a] that there are Fn+2 members of G′ nnot starting with 11. On the other hand, if ρdoes start with 11, then we have that there are Fn+1 possibilities, by the same reasoning. Combining the two preceding cases on ρ implies |G′ n|=Fn+2 +Fn+1 =Fn+3, which establishes (46) and completes the proof. Proof of (14).Note first that (14) may be written in the more suggestive form 2n−2F2n+4 =|Hn|, n ≥1,(47) where Hndenotes the set of (m+ 3)-color compositions of n. Equation (47) holds for n= 1 or 2, as there are 4 and 21 members of H1and H2, respectively, and hence we may assume n≥3. Recall that the sequence bn=F2n+4 satisfies the recurrence bn= 3bn−1−bn−2, and hence cn= 2n−2bnsatisfies cn= 6cn−1−4cn−2. Let hn=|Hn|for n≥1. To establish (47), it thus suffices to show hn= 6hn−1−4hn−2 for n≥3. To do so, first note that there are clearly 4hn−1members of Hnwhose last part is 1bfor some b∈[4]. Further, there are hn−1members of Hnwhose last part is (a+ 1)bfor some a≥1 and b∈[a+ 3], upon adding one to the final part of an arbitrary member of Hn−1, but not its subscript. It remains to enumerate the subset Sof Hnconsisting of those compositions having last part aa+3 for some a≥2. To do so, consider the subset H′ nof Hn consisting of those compositions that do not have last part 11, 12, 13, or cdfor some c≥2 and d∈[c+ 2]. Note that adding one to both the last part of a member of H′ n−1and its subscript defines a bijection between H′ n−1and S. Thus, we have |S|=|H′ n−1|=hn−1−4hn−2, n ≥3, where the second equality follows from a straightforward subtraction argument. Combining this case with the prior ones yields the desired recurrence for hn, which establishes (47) and completes the proof. Proof of (17).Let Jndenote the set of m2m−1-color compositions of n. We represent a part of size awithin a member of Jnas ab, where a≥1, b∈[a], and members of [2, a] may be marked. Note that a separate independent marking of the members of [2, a] is to be made for each part of size afor all a(which may be viewed as a tile composed of aunit squares, all but the first of which may be marked). Then the left-hand side of (17) is seen to give |Jn|, and we seek to show |Jn|=J2nfor all n≥1. By a Jacobsthal tiling, we mean a square-and-domino tiling in which dominos may be marked. Using its recurrence and initial values, one
INTEGERS: 25 (2025) 23 can show that Jnfor n≥1 enumerates the Jacobsthal tilings of length n−1. Let Lndenote the set of Jacobsthal tilings of length 2n−1. To show |Jn|=J2n, it then suffices to define a bijection between Jnand Ln. In order to do so, we consider an intermediate structure Knconsisting of all 5-ary words of length n−1 in which neither a 4 nor 5 can follow a 2 or 3. Below, we construct bijections (i)f:Kn→ Jnand (ii)g:Kn→ Ln, whence the desired bijection between Jnand Lnis obtained by taking g◦f−1. (i)Bijection between Knand Jn. To define f, let π∈ Kn, where we henceforth may assume n≥2. We decompose πas π=π(0)π(1) ···π(r)for some r≥0, where the section π(i)for each i∈[r] is nonempty, starts with 1, and contains no other 1’s, with π(0) possibly empty and containing no 1’s. We further decompose each π(i) for i∈[r] as π(i)= 1α(i)β(i), where α(i)and β(i)if nonempty contain only letters in {4,5}and {2,3}, respectively, and likewise decompose π(0) as π(0) =α(0)β(0). Note that these decompositions for the π(i)follow from the requirement that no 4 or 5 can follow a 2 or 3 within π. Using this decomposition for π, one can create a member of Jnas follows. Let ai=|α(i)|and bi=|β(i)|for each i. Define f(π) = ((a0+b0+ 1)a0+1,(a1+b1+ 1)a1+1,...,(ar+br+ 1)ar+1), wherein for each 0 ≤i≤r, the p-th member, where 1 ≤p≤ai, of [2, ai+ 1] is marked if and only if the p-th letter of the section α(i)is a 4, and likewise the p-th member, where 1 ≤p≤bi, of [ai+ 2, ai+bi+ 1] is marked if and only if the p-th letter of β(i)is a 2. One may verify that f(π)∈ Jnfor all π∈ Knsuch that the number of parts in f(π) is one more than the number of 1’s in π. The mapping f is seen to be reversible, and constructing its inverse is straightforward. Hence, f provides the desired bijection between Knand Jn. (ii)Bijection between Knand Ln. To define the mapping g, we represent π∈ Kn as π=π(0)π(1) ···π(r)like before. Let g(π) = da0sdb0sda1sdb1···sdarsdbr, where djdenotes a run of dominos of length j≥0 and the p-th domino in the run daior dbifor each 0 ≤i≤ris marked if and only if the p-th letter of α(i)or β(i)is 4 or 2, respectively. One may verify that g(π) has length 2(n−1)+ 1 = 2n−1, and hence belongs to Lnfor each π. Further, note that πcontaining rletters 1 for some r≥0 implies g(π) contains 2r+ 1 squares. To reverse g, consider decomposing an arbitrary member of Lnaccording to its runs of dominos and noting which, if any, dominos within a particular run are marked. The mapping gthen provides the desired bijection between Knand Ln, which completes the proof. Proof of (18).Let Qndenote the set of m-color compositions of nwherein each part of a composition is marked in one of four ways (indicated by an element of
INTEGERS: 25 (2025) 24 [4]). Then the left-hand side of (18) is seen to give |Qn|, and we seek to show |Qn|= 2P2nfor n≥1. It is well-known (see, e.g., [3]) that Pnfor n≥1 enumerates the set of Pell tilings of length n−1, which are square-and-domino tilings where squares come in one of two colors. Let Tndenote the set of Pell tilings of length 2nending in a square. Then |Tn|= 2P2n, and thus to establish (18), it suffices to define a bijection between Qnand Tnfor n≥1. To aid in doing so, we consider an intermediate structure Rnconsisting of 6-ary words of length nstarting with a letter in [4] such that no 6 can follow a 5. Below, we define bijections (i)f:Rn→ Qnand (ii)g:Rn→ Tn, whence the desired bijection between Qnand Tnis obtained by taking g◦f−1. (i)Bijection between Rnand Qn. To define f, we decompose π∈ Rnas π=y1π(1) ···ysπ(s), s ≥1,(48) where yi∈[4] and π(i)= 6pi5qifor each i∈[s], with pi, qi≥0 for all i. Note that the requirements that πstarts with a letter in [4] and that no 6 follows a 5 in π allow us to decompose πas in (48). Let f(π) be the member of Qnwhose i-th part for each i∈[s] is given by (pi+qi+ 1)pi+1, with this part being marked according to yi∈[4]. Then fcan be reversed upon considering the number of parts in an arbitrary member of Qnas well as how each part is marked. Thus, the mapping f provides the desired bijection between Rnand Qn. (ii)Bijection between Rnand Tn. Let ρ∈ Rn, where we may assume n≥2. In order to define g, we decompose ρas ρ=x0ρ(0)x1ρ(1) ···xrρ(r) for some r≥0, where xi∈[4] for each 0 ≤i≤rand the section ρ(i)for i∈[r] is given by ρ(i)= 6jia(i) 1a(i) 2···a(i) ki, ji≥1, ki≥0,(49) with the letters a(i) 1, a(i) 2, . . . , a(i) kieach belonging to [5]. The section ρ(0) is of the same form except that j0= 0 is also allowed. One may verify that ρmay be decomposed as described above since it must start with a letter in [4], with no 6 following a 5. Let us represent the two kinds of colored squares in a Pell tiling by band w standing for black and white, respectively. Define the function δ: [5] → P2by δ(1) = b2,δ(2) = bw,δ(3) = wb,δ(4) = w2, and δ(5) = d. Consider replacing each section xiρ(i)of ρ, where ρ(i)is given by (49), with the tiling Tidefined by Ti=djiδ(a(i) 1)δ(a(i) 2)···δ(a(i) ki),0≤i≤r, where the two blank positions are to be filled by the first and second squares, respectively, of δ(xi). Let g(ρ) = T0T1···Tr, where it is understood that the tilings Tiare concatenated.
INTEGERS: 25 (2025) 25 One may verify g(ρ)∈ Qnfor all ρ∈ Rn. To reverse g, suppose λ∈ Tncan be written as λ=λ′dλ′′, where λ′is of even length and contains at least one square and dis the leftmost domino for which λcan be decomposed in this manner. If no such d exists, then we take λ′=λ. Note that λ′may then be written as λ′=dℓsy1···yms′ for some ℓ, m ≥0, where each yiis a sequence of two (colored) squares or a single domino and s, s′denote squares (color unspecified). We then reconstruct the initial section x0ρ(0) of g−1(λ) by letting x0=δ−1(ss′) and putting j0=ℓ,k0=m, and a(0) j=δ−1(yj) for each 1 ≤j≤min the decomposition of ρ(0) given in (49). If λ′=λ, then we are done. Otherwise, we repeat the above procedure using the subtiling dλ′′ in place of λ. This yields a second section of g−1(λ) of the form in (49) which contains at least one 6 (i.e., j1≥1). We then repeat the procedure until no tiles of λremain. Note that each section, which we will denote by xiρ(i)as before, that is obtained from an iteration of the procedure contains at least one 6, except for possibly the first. Let ρ=g−1(λ) be the 6-ary word obtained by concatenating these various sections from left to right in the order they arose. One may verify ρ∈ Rnfor all λand that this procedure defined on λis indeed the inverse of g. Hence, the mapping gprovides the desired bijection between Rnand Tn, which completes the proof of (18). Further, it is seen that the number of runs of din λ wherein the first din the run starts at an odd position, excluding a possible initial run of d, is always one less than the number of sections xiρ(i)in ρ. Note that (1) follows from the well-known fact |Cn|=F2nfor n≥1, as the right-hand side is seen to enumerate the members of Cnby considering all possible sequences of multiplicities of the various part sizes. For a bijective proof of an equivalent statement of (1), written as a sum over the compositions of n, see [17, p. 46, Exercise 14f]. We conclude by extending our arguments above to provide a combinatorial explanation of (3). Proof of (3).Note first that (3) may be written equivalently as 2Pn−1=X β∗=n 2|β|mn−1(β)1β12β2···(n−1)βn−1, n ≥1,(50) where the sum is over all β= (β1, . . . , βn−1) such that β∗= 2β1+···+nβn−1=n. Equation (50) holds trivially for n= 1, so we may assume n≥2. Recall that C′ n denotes the subset of Cnin whose members no part with subscript one is allowed. Let Unbe the set of ordered pairs (λ, ω), where λ∈ C′ nand ωis a binary word whose length is the number of parts of λ. Then we have that the right side of (50) gives |Un|and we seek to show |Un|= 2Pn−1for n≥2. To do so, we describe a recursive construction for obtaining the members of Un for n > 2 starting with those in U2={(22,0),(22,1)}. Consider an (n−2)-step procedure where, in each step, one of the following five operations is applied to the