Determinantal Representations of Some Classical Recurrent Sequences

#A97 INTEGERS 25 (2025)
DETERMINANTAL REPRESENTATIONS OF SOME CLASSICAL
RECURRENT SEQUENCES
Ta as Goy
Facul y o Ma hema ics and Compu e Science, Vasyl S e anyk Ca pa hian
Na ional Uni e si y, I ano-F anki sk, Uk aine
[email p o ec ed]
Ma k Sha uck
Depa men o Ma hema ics, Uni e si y o Tennessee, Knox ille, Tennessee
[email p o ec ed]
Recei ed: 10/8/24, Accep ed: 10/5/25, Published: 11/5/25
Abs ac
In his pape , we ind mul i-sum exp essions o se e al second-o de ecu en
sequences including he Fibonacci, Lucas, Pell, and Jacobs hal numbe s. These
exp essions may also be w i en equi alen ly as Toepli z–Hessenbe g de e minan
iden i ies in ol ing he O esme numbe s. We ob ain hese o mulas as special cases
o mo e gene al esul s o he Ho adam numbe s in ol ing a class o de e minan s
and hei associa ed gene a ing unc ions. We also ind a c i e ion o de e mining
when a gene ic Ho adam sequence can be exp essed explici ly as a de e minan o
a Toepli z–Hessenbe g ma ix wi h associa ed sequence ai= (bi +c)di o i≥1.
Finally, we p o ide combina o ial p oo s o se e al o ou iden i ies o he Fibonacci
numbe s and o he s, whe ein we enume a e ce ain s uc u es ea u ing (m+ )-colo
composi ions o n o a ious .
1. In oduc ion
We i s ecall some well-known combina o ial sequences. The Fibonacci, Lucas,
Pell, Pell–Lucas, and Jacobs hal numbe sequences a e deno ed by Fn,Ln,Pn,Qn,
and Jnand a e gi en, espec i ely, as ollows o 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,
whe e each ecu ence applies o all n≥2. See, espec i ely, en ies A000045,
A000032, A000129, A002203, and A001045 in he OEIS [16] o u he in o ma ion
on hese sequences.
In [11], he ollowing mul i-sum exp essions we e ob ained o he Fibonacci and
Pell numbe s.
P oposi ion 1. Fo n≥1, he ollowing o mulas 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
1s13
2s2
···2n−1
2n−1sn
,(2)
Pn−1= 2n−1·X
s1,...,sn−1≥0
2s1+3s2+···+nsn−1=n
mn−1(s)1
2s12
4s2
···n−1
2n−1sn−1
,(3)
whe e mn(s) = s1+···+sn
s1,...,sn=(s1+···+sn)!
s1!···sn!.
In his pape , we ex end hese esul s by inding some u he iden i ies in ol ing
Fnand Pnas well as o mulas o Ln,Qn, and Jn. We ema k ha hese o mulas
can be ob ained as special cases o mo e gene al esul s in ol ing he Ho adam
sequence. Le On=n
2n,n≥0, deno e he n- h O esme numbe , which is gi en
ecu si ely by On=On−1−1
4On−2,n≥2, wi h O0= 0 and O1=1
2. We
e e he eade o [6, 13] o u he p ope ies o On. I will be seen ha ou
mul i-sum o mulas o he sequences abo e may be exp essed as de e minan s o
ce ain Toepli z–Hessenbe g ma ices wi h O esme numbe en ies (see Co olla y
4 below). O he ecen esul s ha e been gi en o Toepli z–Hessenbe g ma ices
whose nonze o en ies a e de i ed om a ious combina o ial sequences, among
hem, he Ca alan [7], Fibonacci [8], Mo zkin [9], and Leona do [10] numbe s.
Le n= n(p, q, , s) deno e he n- h Ho adam numbe (see, e.g., [12]) de ined
ecu si ely by n= n−1+s n−2 o n≥2, wi h 0=pand 1=q, whe e p, q, , s
a e a iables. We will de e mine a gene al explici o mula (Theo em 1) in e ms
o de e minan s o nwhose pa ame e s sa is y a ce ain es ic ion. We conside
u he he special case o nwhen =s= 1, known as he Gibonacci numbe s,
which will be deno ed he e by Gnas in [4]. Tha is, he numbe s Gnsa is y he
ecu sion Gn=Gn−1+Gn−2 o n≥2, wi h G0=pand G1=q. No e ha Gn
educes o Fnand Lnwhen (p, q) = (0,1) and (2,1), espec i ely.
The o ganiza ion o his pape is as ollows. In he nex sec ion, we ind explici
de e minan al exp essions o se e al speci ic second-o de ecu en sequences as
INTEGERS: 25 (2025) 3
well as a gene al o mula o a class o Ho adam sequences. Fo mulas in hese spe-
ci ic cases a e subsequen ly exp essed equi alen ly as O esme numbe de e minan
iden i ies. In he hi d sec ion, we es ablish a de e minan al exp ession o he se-
quence kGn+m o n≥1, whe e kis a cons an (dependen upon m,G0, and G1)
and m≥0 is ixed, which is subsequen ly gene alized (Theo ems 2 and 3). Fu he ,
i is shown ha among all sequences o he o m Fℓn+m o n≥0, whe e ℓ≥1 and
m≥0 a e ixed, only he sequences Fn+3 and F2nadmi an exp ession as a de e -
minan o a Toepli z–Hessenbe g ma ix wi h associa ed sequence ai= (bi +c)di
o i≥1 (see P oposi ion 2).
In he inal sec ion, we p o ide combina o ial a gumen s o se e al o ou mul i-
sum o mulas u ilizing s uc u es ha inco po a e (m+ )-colo composi ions as
well as ce ain ypes o squa e-and-domino ilings. We p o e ou esul s by di ec
enume a ion, ei he in es ablishing a de ining ecu ence ela ion o p o iding a
bijec ion be ween some pe inen disc e e s uc u es. In one case, a esul is p o en
by i s de ining a sui able sign-changing in olu ion and hen enume a ing he se
o su i o s o he in olu ion. Recall ha he numbe o (m+ 1)- and (m+3)-colo
composi ions o na e gi en by A003480(n) and A010908(n−1), espec i ely. As a
consequence o ou a gumen s o (11) and (14) in he las sec ion, we ob ain, ia
combina o ial p oo s, new o mulas o hese sequences as ollows:
A003480(n) = (2(n−1)/2Pn+1, n odd;
2(n−4)/2Qn+1, n e en,
and A010908(n)=2n−1F2n+6 o n≥1. We ema k ha di e en exp essions o
hese sequences we e ound in [5] which in ol e a double summa ion.
2. De e minan al Rep esen a ions o Recu en Sequences
An n×nma ix Ano he o m
An:= An(a0;a1, . . . , an) = 






a1a00··· 0 0
a2a1a0··· 0 0
··· ··· ··· ...··· ···
an−1an−2an−3··· a1a0
anan−1an−2··· a2a1







,(4)
whe e a0= 0, is said o be Toepli z–Hessenbe g (see, e.g., [15]). The de e minan
o Anis gi en explici ly in e ms o he aias ollows.
Lemma 1. I n≥1, hen
de (An) = X
eα=n
(−a0)n−|α|mn(α)aα1
1aα2
2···aαn
n,(5)
INTEGERS: 25 (2025) 4
whe e he sum is o e all n- uples α= (α1, . . . , αn)o non-nega i e in ege s such
ha eα=α1+ 2α2+···+nαn=n, wi h |α|=α1+···+αnand mn(α) = |α|!
α1!···αn!.
The p eceding esul is known as T udi’s o mula [14, Theo em 1], he a0= 1
case o which has been a ibu ed o B ioschi [15].
De ine he gene a ing unc ions
(x) = X
n≥1
de (An)xnand g(x) = X
i≥1
aixi,
whe e Anis o he o m in (4). Using (5), one can show he ollowing ela ion
be ween (x) and g(x), see [10].
Lemma 2. We ha e
(x) = −1
a0g(−a0x)
1 + 1
a0g(−a0x).(6)
Gi en n≥1 and inde e mina es a,b,c, and d, le Un=Un(a, b, c, d) be he
n×nToepli z–Hessenbe g ma ix whe ein a0=aand ai= (bi +c)di o i≥1. Le
un=un(a, b, c, d) deno e he de e minan o he ma ix Un o n≥1.
Rema k 1. E en hough one may ake d= 1 in unwi hou loss o gene ali y,
due o he easily e i ied ela ion un(a, b, c, d) = un(ad, bd, cd, 1) o n≥1, i will
o en be con enien o e ain he dpa ame e . Fo example, his o en leads o
nice de e minan al exp essions o ecu en sequences as well as allowing one o
see ce ain special cases mo e eadily (see, e.g., he p oo s o Co olla ies 1 and 2
below). Fu he , since we also ha e
un(a, b, c, d) = un(1, b/a, c/a, ad) = pe mUn(1,−b/a, −c/a, −ad),
one can ob ain o mulas i desi ed o he ecu en sequences below as de e minan s
o pe manen s, espec i ely, o Toepli z–Hessenbe g ma ices wi h uni supe diag-
onal en ies.
De ine he gene a ing unc ion u(x) = P
n≥1
unxn. Then u(x) has he ollowing
explici o mula.
Lemma 3. We ha e
u(x) = dx(b+c+acdx)
1 + d(2a−b−c)x+ad2(a−c)x2.(7)
P oo . No e i s ha
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 hen ha e
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 desi ed.
Using (7), we ob ain he ollowing explici o mula in ol ing he Fibonacci and
Lucas numbe s.
Co olla y 1. I n≥1, hen
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 e en.(8)
P oo . No e i s ha (8) may be w i en equi alen ly as
X
eα=n
mn(α)1
√5α13
5α2
···(n+ 1)2n−2
√5nαn
=(1
√5Fn+1, n odd;
1
5Ln+1, n e en, (9)
since α1+2α2+···+nαn=n o all n- uples α= (α1, . . . , αn) unde conside a ion
in he sum. By Lemma 1, he le side o (9) is gi en by un−1,1/4,1/4,2/√5
o each n≥1. Taking a=−1, b=c= 1/4, and d= 2/√5 in Lemma 3, he le
side o (9) hen has gene a ing unc ion
α(x) := x(√5−x)
5(1 −√5x+x2).
Conside ing he odd and e en pa s o α(x), and compu ing α(x)∓α(−x)
2, we ha e
α(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,
whe e in he second equali y we ha e made use o he ac s
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 ha e he ollowing compa able o mulas in ol ing he Pell and Pell–Lucas
numbe s.

INTEGERS: 25 (2025) 6
Co olla y 2. I n≥1, hen
X
β∗=n
mn−1(β)1β1(2√2)β2···((n−1)√2n−2)βn−1=(√2Pn−1, n odd;
1
2Qn−1, n e en,(10)
X
eα=n
mn(α)(√2)α13
2α2
···n+ 1
√2nαn
=(1
√2Pn+1, n odd;
1
4Qn+1, n e en,(11)
whe e he i s sum is o e all (n−1)- uples β= (β1, . . . , βn−1)o non-nega i e
in ege s such ha β∗= 2β1+ 3β2+···+nβn−1=n.
P oo . No e i s ha he le side o (10) may be w i en as
X
eα=n
mn(α)0α11α2(2√2)α3···((n−1)√2n−2)αn,
and hence, by (5), is gi en by un(−1,1/2,−1/2,√2) o n≥1. By (7), we ha e
δ(x) := X
n≥1
un−1,1/2,−1/2,√2xn=x2
1−2√2x+x2.
Conside ing he odd and e en pa s o δ(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), whe e we ha e used he ac s
X
n≥1
P2nxn=2x
1−6x+x2and X
n≥1
Q2n−1xn=2x(1 + x)
1−6x+x2.
A compa able p oo may be gi en o (11), upon obse ing ha he le side o
(11) is gi en by un(−1,1,1,1/√2) o n≥1, and hence has gene a ing unc ion
x(2√2−x)
2(1−2√2x+x2).
Le n= n(p, q, , s) deno e he Ho adam sequence gi en by n= n−1+s n−2
o n≥2, wi h 0=pand 1=q. Then we ha e he ollowing gene al ep esen a ion
o n.
Theo em 1. Le p,q, ,sbe complex numbe s wi h (q− )2= 4s(p−1) = 0. I
n= n(p, q, , s)deno es he co esponding Ho adam sequence, hen
n=X
eα=n −q
2n−|α|mn(α)
n
Y
i=1 q+2ps
−qi−2ps
−qαi
, n ≥1.(12)
Con e sely, he sequence nde ined by (12) o all n≥1sa is ies n= n−1+s n−2
o n≥3.
INTEGERS: 25 (2025) 7
P oo . To show (12), we i s seek a,b,c,dsuch ha n=un(a, b, c, d) o all
n≥1. In o de o his o hold, we need he co esponding equali y o gene a ing
unc ions, i.e., (x) = u(x), whe e
(x) = X
n≥1
nxn=x(q+psx)
1− x −sx2
and u(x) is gi en by (7). This leads o he ollowing sys em o equa ions in he
unknowns a,b,c,d:
(i)d(b+c) = q, (ii)acd2=ps, (iii)d(b+c−2a) = , (i )ad2(c−a) = s,
whe e p,q, ,sa e ixed.
Sub ac ing equa ion (iii) om (i), and also (i ) om (ii), gi es 2ad =q− and
(ad)2=ps −s. Since (q− )2= 4s(p−1), by assump ion, hese las wo equa ions
a e equi alen o one ano he . F om ad =q−
2= 0, we hen ge
cd =ps
ad =2ps
q− and bd =q−cd =q2− q −2ps
q− .
No e ha once d= 0 is speci ied, hen a, b, c a e uniquely de e mined. Tha is, o
d= 0, we ha e
n=un(a, b, c, d) = unq−
2d,q2− q −2ps
d(q− ),2ps
d(q− ), d, n ≥1.
Hence, by (5), we ge
n=X
eα=n
(−a)n−|α|mn(α)
n
Y
i=1 (bi +c)diαi
=dnX
eα=n −q
2dn−|α|mn(α)
n
Y
i=1 q2− q −2ps
d(q− )i+2ps
d(q− )αi
=X
eα=n −q
2n−|α|mn(α)
n
Y
i=1 q+2ps
−qi−2ps
−qαi
,
which yields (12).
Con e sely, suppose n o n≥1 is he sequence de ined by (12), whe e p,q, ,s
a e as s a ed abo e. By (5), we ha e n=un(a, b, c, d), whe e a=q−
2,b=q−2ps
q− ,
c=2ps
q− , and d= 1. Applying (7) yields
X
n≥1
nxn=x(q+psx)
1− x +q−
2q−
2−2ps
q− x2=x(q+psx)
1− x −sx2,
upon making use o he assump ion (q− )2= 4s(p−1). The las equali y abo e
implies n= n−1+s n−2 o n≥3, which comple es he p oo .
INTEGERS: 25 (2025) 8
Taking speci ic cases o Theo em 1 yields de e minan al ep esen a ions o se e al
second-o de ecu en sequences.
Co olla y 3. I n≥1, hen
X
eα=n
mn(α)3α1(−4)α2···((−1)n−1(n+ 2))αn=Fn+3,(13)
X
eα=n
mn(α)2α15
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)
P oo . To show (13)–(18), we apply (12) o n= n(p, q, , s), whe e
(p, q, , 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).
No e ha (q− )2= 4s(p−1) = 0 o each quad uple (p, q, , s). Applying (12) in
each case hen yields (13)–(18), espec i ely.
Rema k 2. I (q− )2= 4s(p−1), hen he p oo o Theo em 1 shows ha he
Ho adam sequence n(p, q, , s) does no ha e he ep esen a ion (12) o n≥1 as
he sys em o equa ions (i)–(i ) is no consis en in his case. On he o he hand,
i (q− )2= 4s(p−1) = 0 wi h s= 0, hen one mus ha e ad = 0 in he sys em
(i)–(i ) abo e. Bu a= 0 is no possible since nsa is ies a ecu ence o second,
bu no i s , o de as s= 0. Also, d= 0, o o he wise n= 0 o all n≥1.
Thus, n ails o ha e he o m in (12) i (q− )2= 4s(p−1) = 0 wi h s= 0 (no e
ha i s= 0 and q= , hen i ially one has n=un(0,0, q, 1) o n≥1). Fo
addi ional examples o Theo em 1, no e ha n=F2n, 21−nF3n−1, and 21−nPn−1
a e Ho adam sequences wi h (p, q, , s) = (0,1,3,−1), (2,1,2,1/4), and (2,0,1,1/4),
espec i ely, whe e in each case, we ha e (q− )2= 4s(p−1) = 0. Applying (12)
hen yields (1)–(3) abo e, which we e shown in [11] by a di e en me hod.
One can also exp ess he iden i ies in he co olla ies o his sec ion equi alen ly
as Toepli z–Hessenbe g de e minan o mulas in ol ing he O esme numbe s. Fo
o he O esme de e minan o mulas, see [11].
INTEGERS: 25 (2025) 9
Co olla y 4. I n≥1, hen
de (−2; O2, O3, . . . , On+1) = (5(n−1)/2
2nFn+1, n odd;
5(n−2)/2
2nLn+1, n e en,(19)
de (−4; O0, O1, . . . , On−1) = (2(n+1/2)Pn−1, n odd;
2(n−2/2)Qn−1, n e en,(20)
de (−1/2; O2, O3, . . . , On+1) = (2−(3n+1)/2Pn+1, n odd;
2−(3n+4)/2Qn+1, n e en,(21)
de (1/4; O3, O4, . . . , On+2)=2−3nFn+3,(22)
de (−1/8; O4, O5, . . . , On+3)=2−(3n+2)F2n+4,(23)
de (1/4; O3, O5, . . . , O2n+1) = 2−(4n−1)F3n+1,(24)
de (1/4; O5, O7, . . . , O2n+3) = 2−5nJn+3,(25)
de (−2; O1, O2, . . . , On)=2−nJ2n,(26)
de (−1/4; O1, O2, . . . , On)=2−(3n−1)P2n.(27)
P oo . We p o ide p oo s o (19) and (22). Simila a gumen s may be gi en o
he o he s using (10), (11), and (14)–(18), espec i ely. Di iding bo h sides o (8)
by 2n, ea anging ac o s somewha , and no ing α1+ 2α2+···+nαn=n o all
n- uples αunde conside a ion in he 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 e en.
The le side o he las iden i y is de (−2; O2, . . . , On+1), by (5), which gi es (19).
Di iding bo h sides o (13) by 23nyields
X
eα=n−1
4n−|α|mn(α)
n
Y
i=1 i+ 2
2i+2 αi
= 2−3nFn+3,
whose le side is gi en by de (1/4; O3, . . . , On+2), which implies (22).
3. Fu he Resul s
We s a his sec ion wi h he ollowing gene al ep esen a ion o ansla es o he
Gibonacci sequence.
Theo em 2. Le Gndeno e he Gibonacci sequence wi h y=G0and z=G1, whe e
yand za e non-nega i e in ege s, no bo h ze o. Le m≥3be ixed. Then we ha e
INTEGERS: 25 (2025) 16
Thus, we ha e ha kGℓn+mis a good Ho adam sequence i and only i kis gi en
by (39), in which case kGℓn+m= n(p, q, , s), wi h
(p, q, , s)
=Gm(LℓGℓ+m−2(−1)ℓGm±2E)
G2
ℓ+m
,LℓGℓ+m−2(−1)ℓGm±2E
Gℓ+m
, Lℓ,(−1)ℓ+1.
Subs i u ing now in o (12), and p oceeding as be o e in he simpli ica ion, yields
(35).
We now show ha i m≥ℓ+ 2, hen bo h choices o sign yield a alid iden i y
in (35). Fi s o all, we mus ha e Gℓ+m= 0; o he wise, one could no apply he
quad a ic o mula in asce aining kand he exp essions in (35) and (39) would
con ain a discon inui y. In o de o Gℓ+m o be ze o, whe e y, z a e non-nega i e
and no bo h ze o, wi h ℓ≥1 and m≥0, we mus ha e ℓ= 1, m= 0, and z= 0.
No e ha his case would echnically no apply o m≥ℓ+ 2, i.e., he ac o Gℓ+m
would always be nonze o o such ℓand m.
F om Theo em 1, in o de o apply (12) o kGℓn+min de i ing (35), we ha e ha
he common alue o bo h sides o he equali y mus be nonze o in he necessa y
(and su icien ) condi ion o kgi en by (kGℓ+m−Lℓ)2= 4(−1)ℓ+1(kGm−1). Thus,
in o de o demons a e ha bo h choices o sign yield a alid iden i y in (35) when
m≥ℓ+ 2, i su ices o show ha o bo h o he possibili ies o kin (39), we ha e
k=Lℓ/Gℓ+m. No e ha k=Lℓ/Gℓ+mi and only i (−1)ℓ+1Gm±E= 0, which is
seen o in oduce di ision by ze o in (35). So i is enough o show ha he equali y
(−1)ℓ+1Gm=±E(40)
canno hold i m≥ℓ+ 2.
To do so, i s no e ha i he adicand in Eis nega i e, hen (40) clea ly canno
hold, so we assume ha he adicand is non-nega i e. Thus, i is enough o show
G2
m> E2,(41)
o m≥ℓ+ 2 when Eis a (non-nega i e) eal numbe . We conside cases on he
pa i y o ℓ, i s assuming ℓis odd. I mis odd, by he s a ed o mula o E, we
ha e ha (41) holds i and only i G2
m−z2> Gℓ+1(zLℓ−Gℓ+1). Since yand z
a e non-nega i e, i ollows ha Gmis inc easing in m o ixed alues o yand z.
The e o e, o demons a e he las inequali y o all odd m≥ℓ+ 2, we only need
o conside he case whe e m=ℓ+ 2.
Then we mus es ablish
(Gℓ+2 +z)(Gℓ+2 −z)> Gℓ+1(zLℓ−Gℓ+1).(42)
No e (42) clea ly holds i z= 0 since y > 0 in his case, and hence we may assume
z > 0. Fu he , we ha e
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 compa ing he espec i e le and igh ac o s o he wo sides, one
ob ains (42). I mis e en, hen (41) is equi alen o G2
m−y2> Gℓ(yLℓ−Gℓ).
Then m≥ℓ+ 2 and me en implies in ac m≥ℓ+ 3, and i is enough o show he
las inequali y when m=ℓ+ 3, which can be done in a simila manne as be o e.
A compa able p oo , which we omi , based on cases wi h ega d o he pa i y o m
may be gi en o (41) when ℓis e en, which comple es he p oo o (41). Thus, we
ha e ha (40) canno hold o all ℓ≥1 and m≥ℓ+ 2, as desi ed.
Fu he , i ℓ≥2, hen one can show ha LℓGℓ+m+ 2(−1)ℓ+1Gm±2E > 0 in
all cases when Eis eal, and hence his ac o is always nonze o in (35) o such ℓ.
I ℓ= 1, hen his ac o is ze o only when m=z= 0 and minus is chosen, bu
his case is al eady co e ed by he p io conside a ions gi en o he Gℓ+m ac o .
Thus, di ision by ze o in (35) can only occu when 0 ≤m≤ℓ+ 1 in ce ain cases
whe e yand za e such ha Gℓ+m((−1)ℓ+1Gm±E) is ze o. This implies he inal
s a emen in Theo em 3 and comple es he p oo .
The second s a emen in Theo em 3 is also seen o apply o he iden i ies in (35)
o ixed ℓand m, whe e he e is only a single iden i y o he s a ed o m in cases
whe e a choice o one o he signs leads o di ision by ze o. Taking ℓ= 1 in (35) is
seen o yield (28). Taking ℓ= 2 in (35) gi es he ollowing explici o mulas o he
Gibonacci hal -sequences G2n+m o a ixed m.
Co olla y 6. Fo each m≥4 ixed, he e is he ollowing pai o iden i ies o 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 ±2Fn−|α|mn(α)
n
Y
i=1
(±Fi −Gm)αi,
(43)
whe e F=p(−1)m+1(y2+yz −z2)wi h y=G0,z=G1. Fu he , i 0≤m≤3,
hen bo h iden i ies in (43) hold excep in he ollowing cases whe e only he nega i e
choice o sign leads o a alid exp ession: (i)m= 0 and 2y=z, (ii)m= 1 and
y=z, (iii)m= 2 and y= 0, o (i )m= 3 and z= 0.
Taking (y, z) = (0,1) o (2,1) in (43) gi es analogues o he o mulas om Co ol-
la y 5 o he Fibonacci and Lucas hal -sequences.
INTEGERS: 25 (2025) 18
4. Combina o ial P oo s
In his sec ion, we p o ide combina o ial a gumen s o mos o he o mulas om
Co olla ies 2 and 3 abo e as well as o he p io iden i y (3), which was shown
in [11] by an algeb aic a gumen . To do so, we will enume a e se e al s uc u es
in ol ing (m+ )-colo composi ions o n. Recall ha a composi ion o a posi i e
in ege nis a sequence o posi i e in ege s, called pa s, whose sum is n. Gi en a
non-nega i e in ege , an (m+ )-colo composi ion o nis one in which a pa o
size a o each a≥1 is assigned one o a+ colo s. This colo is o en deno ed by
a subsc ip on he pa in ques ion. Thus, an (m+ )-colo composi ion πmay be
ep esen ed as π= ((a1)b1,...,(ak)bk) o some k≥1, whe e ai≥1 o 1 ≤i≤k
wi h Pk
i=1 ai=nand bi∈[ai+ ] o each i. The no ion o an m-colo composi ion
was in oduced in [1] and has been an ongoing objec o s udy. See [5], whe e
(am +b)-colo composi ions we e s udied o ixed aand b. Le Cndeno e he se
o m-colo composi ions o n. A undamen al esul (see, e.g., [1]) s a es ha he
ca dinali y o Cnis gi en by F2n o all n≥1.
We will also make use o linea iling s uc u es in se e al o ou p oo s below.
By a ile, we mean a 1 ×m ec angula piece o some m≥1 capable o co e ing
mconsecu i e posi ions. Squa es and dominos co espond o 1 ×1 and 1 ×2
iles, which will be deno ed by sand d, espec i ely. A co e ing o he numbe s
1,2, . . . , n, w i en in a ow, by non-o e lapping squa es and dominos is e e ed o
as a squa e-and-domino iling o leng h n, he se o which will be deno ed he e
by Fn. Recall ha |Fn|=Fn+1 o all n≥0; see, e.g., [4, Chap e 1]. No e ha
membe s o Fnmay be iewed as sequences o n−2msqua es and mdominos o
some 0 ≤m≤ ⌊n/2⌋, o equi alen ly as composi ions o nwhose pa s belong o
{1,2}.
We s a wi h a combina o ial a gumen o he i s iden i y in Co olla y 2.
P oo o (10).We i s conside he e en case o (10), which may be w i en equi -
alen ly as
Qn−1=X
β∗=n
2n+2
2−|β|mn−1(β)1β12β2···(n−1)βn−1, n ≥2 e en,(44)
whe e he sum is o e all β= (β1, . . . , βn−1) such ha β∗= 2β1+···+nβn−1=n.
One may e i y (44) in he cases when n= 2 o 4, so assume n≥6. Le dkdeno e
he igh -hand side o (44) whe e n= 2k o k≥1. To es ablish (44), i su ices o
show dk= 6dk−1−dk−2 o k≥3, as he wo sides ag ee when k= 1,2. Le C′
n
deno e he se o m-colo composi ions o nin which no pa s wi h subsc ip one
a e allowed. Gi en λ∈ C′
n, suppose ha he ec o eco ding he mul iplici ies o
he pa sizes o λis gi en by β o some βsuch ha β∗=n. Tha is, o each
i∈[n−1], he e a e exac ly βipa s o size i+ 1 in he composi ion λ. Fo each
λ, de ine Sλ o be he se o bina y wo ds o leng h n+2
2−Pn−1
i=1 βi. Le Dkdeno e
INTEGERS: 25 (2025) 19
he se o all o de ed pai s (λ, ω), whe e λ∈ C′
2kand ω∈Sλ. Then i is seen ha
dk=|Dk| o all k≥1. Using his combina o ial in e p e a ion o dk, we will
es ablish he ecu ence s a ed abo e o dk.
To do so, i s conside appending he (colo ed) pa 22 o λ′in x′= (λ′, ω′)∈
Dk−1 o ob ain x= (λ, ω)∈ Dkwhe ein λends in 22. No e ha we ake ω=ω′
since he di e ence k−Pi≥1βiis main ained in going om λ′ o λ, as bo h kand
Pi≥1βia e inc eased by one in his case. This yields dk−1possibili ies o such
x. Now conside adding wo o he inal pa o λ′, bu no i s subsc ip , and hen
appending 0 o 1 o ω′ o ob ain x om x′. No e ha adding 0 o 1 o ω′is equi ed
in his case since he di e ence k−Pi≥1βiwi h ega d o x′is inc eased by one
by such an ope a ion on λ′, as kinc eases by one (i.e., ninc eases by wo), bu
he numbe o pa s emains he same. This hen yields 2dk−1membe s x∈ Dk
whe ein he inal pa o λexceeds i s subsc ip by a leas wo.
Now suppose λwi hin x= (λ, ω)∈ Dkhas inal pa ab, whe e a≥3 and b=a
o a−1. We mus show ha such membe s xwi hin Dknumbe 3dk−1−dk−2. To
do so, i s le Jand Ldeno e wo copies o he se Dk−1. Le x′= (λ′, ω′)∈J. I
he inal pa o λ′is a leas 3, and no aa o some a, hen educe he inal pa ,
bu no i s subsc ip , by one and append 32 o λ′. On he o he hand, i he inal
pa is aa o some a≥2, hen eplace he inal pa o λ′wi h (a+ 2)a+2. In he
la e case, we also add 0 o he end o ω′ o ob ain x om x′. I x′∈K, hen we
pe o m compa able ope a ions as be o e, bu append 33 o λ′, ins ead o 32, i he
inal pa o λ′is no aa, and add 1 o he end o ω′, ins ead o 0, in cases when i
is.
Le Sdeno e he subse o Dkconsis ing o hose (λ, ω) whe ein he inal pa
absa is ies a≥4 wi h b=a−1. A his poin , all he membe s o Dk−Sha e
been enume a ed, and a e seen o ha e ca dinali y 5dk−1, so o comple e he p oo
o he ecu ence o dk, we mus show |S|=dk−1−dk−2. To do so, i s no e
ha he e a e dk−1−2dk−2membe s (λ′, ω′)∈ Dk−1in which he inal pa o λ′
is cd, whe e c=d= 2 o c≥3 wi h d=co c−1, by sub ac ion. To see his,
ake any (ρ, α)∈ Dk−2, inc ease he inal pa o ρby wo, lea ing i s subsc ip
unchanged, and hen append 0 o 1 o α o ob ain he excluded membe s o Dk−1
accoun ed o by he sub ac ed e m. To each (λ′, ω′)∈ Dk−1as desc ibed, we
eplace he inal pa cdo λ′wi h (c+ 2)c+1 and ei he append 1 o ω′i c≥3
wi h d=c−1 o append 0 o ω′i c=d≥2. No e ha his yields uniquely all
membe s o S−S′, whe e S′consis s o hose (λ, ω)∈Ssuch ha λhas inal pa
43and ωends in 1, and hence |S−S′|=dk−1−2dk−2. Fu he , |S′|=dk−2, upon
conside ing an a bi a y (ρ, α)∈ Dk−2and appending 43 o ρand 1 o α. This
implies |S|=dk−1−dk−2, and hence uk= 6uk−1−uk−2 o k≥3, as desi ed,
which comple es he p oo o (44). A simila p oo may be gi en o he odd case
INTEGERS: 25 (2025) 20
o (10), ew i en as
Pn−1=X
β∗=n
2n−1
2−|β|mn−1(β)1β12β2···(n−1)βn−1, n ≥1 odd,
whe e βis as be o e.
P oo o (11).We i s p o e he odd case o (11), w i en equi alen ly as
2(n−1)/2Pn+1 =X
eα=n
mn(α)2α13α2···(n+ 1)αn, n ≥1 odd,(45)
whe e he sum is o e all α= (α1, . . . , αn) such ha eα=α1+ 2α2+···+nαn=n.
One may e i y (45) when n= 1 o 3, so assume n≥5. No e ha bn=P2nimplies
bn= 6bn−1−bn−2 o n≥3, and hence 2n−1bn= 12(2n−2bn−1)−4(2n−3bn−2). We
deno e he igh -hand side o (45) by ekwhe e n= 2k−1 o k≥1. To es ablish
(45), i hus su ices o show ek= 12ek−1−4ek−2 o k≥3. Le Endeno e he se
o (m+1)-colo composi ions o n. Then i is seen ha he igh side o (45) equals
|En|. Using he combina o ial in e p e a ion ek=|E2k−1| o k≥1, we will show
ha eksa is ies he ecu ence s a ed abo e.
Fi s , no e ha he e a e clea ly 4ek−1membe s o Enwhose las wo pa s
a e 1a,1a′, whe e a, a′∈ {1,2}, and also 3ek−1membe s ending in 2b, whe e b∈
{1,2,3}. Fu he , upon inc easing he inal pa o an a bi a y membe o En−2by
one, bu no i s subsc ip , and subsequen ly appending 1a, we ha e ha he e a e
2ek−1membe s o Enwhose las wo pa s a e (c+1)d,1a, whe e c≥1 and d∈[c+1].
No e ha his misses composi ions wi h endings o he o m (c+ 1)c+2,1a, which
will be accoun ed o below. Finally, upon inc easing he las pa o a membe
o En−2by wo, and lea ing he subsc ip unchanged, we ha e ha he e a e ek−1
membe s o Enwhose las pa is o he o m (x+ 2)y, whe e x≥1 and y∈[x+ 1].
A his poin , we ha e ound |En−T|= 10ek−1, whe e Tis he subse o En
whose membe s ha e inal pa zzo zz+1 o some z≥3 o whose inal wo pa s
a e (c+ 1)c+2,1a, whe e c≥1. Thus, o comple e he p oo o he ecu ence o
ek, we mus show |T|= 2ek−1−4ek−2 o k≥3. To do so, le Rdeno e he subse
o En−2whose membe s ha e inal pa xxo xx+1 o some x≥1. No e ha
|R|=ek−1−2ek−2, by sub ac ion, upon excluding membe s o En−2ending in 21
o (x+ 2)y, whe e y∈[x+ 1].
We hus need o show |T|= 2|R|. To do so, le Jand Kdeno e wo copies o
he se R. Le δdeno e he inal pa o a membe o Jo K. In membe s o J, we
inc ease bo h δand i s subsc ip by wo o ob ain all membe s o Tending in zzo
zz+1 o some z≥3. In membe s o K, i δ=xx, hen we eplace δwi h he wo
pa s (x+1)x+2,11, whe eas i δ=xx+1, hen we eplace δwi h (x+1)x+2,12. One
hen ob ains he emaining membe s o Tin his way, which es ablishes he desi ed
o mula o |T|. This comple es he p oo o he ecu ence o ek, and hence o
INTEGERS: 25 (2025) 21
(45) as well. Rew i ing he e en case o (11) as
2(n−4)/2Qn+1 =X
eα=n
mn(α)2α13α2···(n+ 1)αn, n ≥2 e en,
and p oceeding as be o e, we comple e he p oo o (11).
P oo o (13).Le Gndeno e he se o (m+ 2)-colo composi ions o n. Le µ(λ)
deno e he numbe o pa s o λ∈ Gnand de ine he sign o λas (−1)n−µ(λ). Then
i is seen ha (13) may be w i en equi alen ly as
Fn+3 =X
λ∈Gn
(−1)n−µ(λ), n ≥1.(46)
To show (46), we de ine a sign-changing in olu ion on Gnwhose se o su i o s has
sum o signs gi en by Fn+3. In o de o do so, le π∈ Gnbe ep esen ed sequen ially
and conside occu ences o one o he ollowing ou ypes in ol ing a pa o pai
o pa s o he s a ed o m, whe e a≥2 and c≥1:
(i)ab,wi h b∈[a+ 1],(ii)cd,11,wi h d∈[c+ 2],(iii)aa+2,o (i )cc+2,13.
Fi s , suppose πcon ains (i) o (ii) and conside he igh mos occu ence o
(i) o (ii) wi hin π. I his igh mos occu ence is a case o (i), hen eplace he
pa ab, whe e a≥2 and b∈[a+ 1], wi h he wo pa s (a−1)b,11, and ice
e sa i (ii), me ging he wo pa s in ques ion in o a single pa o he o m (i).
No e ha bo h ope a ions jus desc ibed e e se he sign since he numbe o pa s
o a membe o Gnchanges by one in each case. Now suppose π ails o con ain
(i) o (ii), bu con ains a leas one occu ence o (iii) o (i ). I he igh mos
occu ence o ei he (iii) o (i ) co esponds o a case o (iii), hen eplace aa+2
whe e a≥2 wi h (a−1)a+1,13, and ice e sa, me ging he wo pa s in ques ion,
i he occu ence co esponds o (i ). Again, hese ope a ions e e se he sign o
all π o which hey a e de ined. Combining he wo p eceding pai s o ope a ions
hen de ines a sign- e e sing in olu ion θon all membe s o Gnwhich wi ness a
leas one o (i)–(i ). In pa icula , no e ha applying he second pai o ope a ions
o membe s o Gnwhich a e ee o (i) and (ii) does no in oduce an occu ence o
(i) o (ii).
Le G′
ndeno e he subse o Gn o which θis no de ined. One may e i y
ha membe s o G′
nconsis exclusi ely o pa s o size 1 subjec o he ollowing
es ic ions:
(i) he pa 11can only occu a he e y beginning, i a all, and
(ii) each pa 13mus be p eceded by 11o 12,o occu a he e y beginning.
No e ha each membe o G′
nhas posi i e sign, consis ing only o pa s o size
one, and hus we seek |G′
n|. To de e mine |G′
n|, i s suppose ρ∈ G′
ndoes no s a

INTEGERS: 25 (2025) 22
wi h 11. Then ρis a sequence o leng h nconsis ing o he pa s 12and 13such
ha no wo pa s 13a e adjacen . Such sequences a e seen o be in one- o-one
co espondence wi h subse s o [n] con aining no wo adjacen elemen s. I ollows
hen om [17, p. 46, Exe cise 14a] ha he e a e Fn+2 membe s o G′
nno s a ing
wi h 11. On he o he hand, i ρdoes s a wi h 11, hen we ha e ha he e a e
Fn+1 possibili ies, by he same easoning. Combining he wo p eceding cases on ρ
implies
|G′
n|=Fn+2 +Fn+1 =Fn+3,
which es ablishes (46) and comple es he p oo .
P oo o (14).No e i s ha (14) may be w i en in he mo e sugges i e o m
2n−2F2n+4 =|Hn|, n ≥1,(47)
whe e Hndeno es he se o (m+ 3)-colo composi ions o n. Equa ion (47) holds
o n= 1 o 2, as he e a e 4 and 21 membe s o H1and H2, espec i ely, and hence
we may assume n≥3. Recall ha he sequence bn=F2n+4 sa is ies he ecu ence
bn= 3bn−1−bn−2, and hence cn= 2n−2bnsa is ies cn= 6cn−1−4cn−2. Le
hn=|Hn| o n≥1. To es ablish (47), i hus su ices o show hn= 6hn−1−4hn−2
o n≥3. To do so, i s no e ha he e a e clea ly 4hn−1membe s o Hnwhose
las pa is 1b o some b∈[4]. Fu he , he e a e hn−1membe s o Hnwhose las
pa is (a+ 1)b o some a≥1 and b∈[a+ 3], upon adding one o he inal pa o
an a bi a y membe o Hn−1, bu no i s subsc ip .
I emains o enume a e he subse So Hnconsis ing o hose composi ions
ha ing las pa aa+3 o some a≥2. To do so, conside he subse H′
no Hn
consis ing o hose composi ions ha do no ha e las pa 11, 12, 13, o cd o some
c≥2 and d∈[c+ 2]. No e ha adding one o bo h he las pa o a membe o
H′
n−1and i s subsc ip de ines a bijec ion be ween H′
n−1and S. Thus, we ha e
|S|=|H′
n−1|=hn−1−4hn−2, n ≥3,
whe e he second equali y ollows om a s aigh o wa d sub ac ion a gumen .
Combining his case wi h he p io ones yields he desi ed ecu ence o hn, which
es ablishes (47) and comple es he p oo .
P oo o (17).Le Jndeno e he se o m2m−1-colo composi ions o n. We ep-
esen a pa o size awi hin a membe o Jnas ab, whe e a≥1, b∈[a], and
membe s o [2, a] may be ma ked. No e ha a sepa a e independen ma king o
he membe s o [2, a] is o be made o each pa o size a o all a(which may
be iewed as a ile composed o auni squa es, all bu he i s o which may be
ma ked). Then he le -hand side o (17) is seen o gi e |Jn|, and we seek o show
|Jn|=J2n o all n≥1. By a Jacobs hal iling, we mean a squa e-and-domino
iling in which dominos may be ma ked. Using i s ecu ence and ini ial alues, one
INTEGERS: 25 (2025) 23
can show ha Jn o n≥1 enume a es he Jacobs hal ilings o leng h n−1. Le
Lndeno e he se o Jacobs hal ilings o leng h 2n−1. To show |Jn|=J2n, i hen
su ices o de ine a bijec ion be ween Jnand Ln. In o de o do so, we conside
an in e media e s uc u e Knconsis ing o all 5-a y wo ds o leng h n−1 in which
nei he a 4 no 5 can ollow a 2 o 3.
Below, we cons uc bijec ions (i) :Kn→ Jnand (ii)g:Kn→ Ln, whence
he desi ed bijec ion be ween Jnand Lnis ob ained by aking g◦ −1.
(i)Bijec ion be ween Knand Jn. To de ine , le π∈ Kn, whe e we hence o h may
assume n≥2. We decompose πas π=π(0)π(1) ···π( ) o some ≥0, whe e he
sec ion π(i) o each i∈[ ] is nonemp y, s a s wi h 1, and con ains no o he 1’s,
wi h π(0) possibly emp y and con aining no 1’s. We u he decompose each π(i)
o i∈[ ] as π(i)= 1α(i)β(i), whe e α(i)and β(i)i nonemp y con ain only le e s
in {4,5}and {2,3}, espec i ely, and likewise decompose π(0) as π(0) =α(0)β(0).
No e ha hese decomposi ions o he π(i) ollow om he equi emen ha no 4
o 5 can ollow a 2 o 3 wi hin π.
Using his decomposi ion o π, one can c ea e a membe o Jnas ollows. Le
ai=|α(i)|and bi=|β(i)| o each i. De ine
(π) = ((a0+b0+ 1)a0+1,(a1+b1+ 1)a1+1,...,(a +b + 1)a +1),
whe ein o each 0 ≤i≤ , he p- h membe , whe e 1 ≤p≤ai, o [2, ai+ 1] is
ma ked i and only i he p- h le e o he sec ion α(i)is a 4, and likewise he p- h
membe , whe e 1 ≤p≤bi, o [ai+ 2, ai+bi+ 1] is ma ked i and only i he p- h
le e o β(i)is a 2. One may e i y ha (π)∈ Jn o all π∈ Knsuch ha he
numbe o pa s in (π) is one mo e han he numbe o 1’s in π. The mapping
is seen o be e e sible, and cons uc ing i s in e se is s aigh o wa d. Hence,
p o ides he desi ed bijec ion be ween Knand Jn.
(ii)Bijec ion be ween Knand Ln. To de ine he mapping g, we ep esen π∈ Kn
as π=π(0)π(1) ···π( )like be o e. Le
g(π) = da0sdb0sda1sdb1···sda sdb ,
whe e djdeno es a un o dominos o leng h j≥0 and he p- h domino in he un
daio dbi o each 0 ≤i≤ is ma ked i and only i he p- h le e o α(i)o β(i)is
4 o 2, espec i ely. One may e i y ha g(π) has leng h 2(n−1)+ 1 = 2n−1, and
hence belongs o Ln o each π. Fu he , no e ha πcon aining le e s 1 o some
≥0 implies g(π) con ains 2 + 1 squa es. To e e se g, conside decomposing
an a bi a y membe o Lnacco ding o i s uns o dominos and no ing which, i
any, dominos wi hin a pa icula un a e ma ked. The mapping g hen p o ides he
desi ed bijec ion be ween Knand Ln, which comple es he p oo .
P oo o (18).Le Qndeno e he se o m-colo composi ions o nwhe ein each
pa o a composi ion is ma ked in one o ou ways (indica ed by an elemen o
INTEGERS: 25 (2025) 24
[4]). Then he le -hand side o (18) is seen o gi e |Qn|, and we seek o show
|Qn|= 2P2n o n≥1. I is well-known (see, e.g., [3]) ha Pn o n≥1 enume a es
he se o Pell ilings o leng h n−1, which a e squa e-and-domino ilings whe e
squa es come in one o wo colo s. Le Tndeno e he se o Pell ilings o leng h
2nending in a squa e. Then |Tn|= 2P2n, and hus o es ablish (18), i su ices o
de ine a bijec ion be ween Qnand Tn o n≥1. To aid in doing so, we conside
an in e media e s uc u e Rnconsis ing o 6-a y wo ds o leng h ns a ing wi h a
le e in [4] such ha no 6 can ollow a 5.
Below, we de ine bijec ions (i) :Rn→ Qnand (ii)g:Rn→ Tn, whence he
desi ed bijec ion be ween Qnand Tnis ob ained by aking g◦ −1.
(i)Bijec ion be ween Rnand Qn. To de ine , we decompose π∈ Rnas
π=y1π(1) ···ysπ(s), s ≥1,(48)
whe e yi∈[4] and π(i)= 6pi5qi o each i∈[s], wi h pi, qi≥0 o all i. No e ha
he equi emen s ha πs a s wi h a le e in [4] and ha no 6 ollows a 5 in π
allow us o decompose πas in (48). Le (π) be he membe o Qnwhose i- h pa
o each i∈[s] is gi en by (pi+qi+ 1)pi+1, wi h his pa being ma ked acco ding
o yi∈[4]. Then can be e e sed upon conside ing he numbe o pa s in an
a bi a y membe o Qnas well as how each pa is ma ked. Thus, he mapping
p o ides he desi ed bijec ion be ween Rnand Qn.
(ii)Bijec ion be ween Rnand Tn. Le ρ∈ Rn, whe e we may assume n≥2. In
o de o de ine g, we decompose ρas
ρ=x0ρ(0)x1ρ(1) ···x ρ( )
o some ≥0, whe e xi∈[4] o each 0 ≤i≤ and he sec ion ρ(i) o i∈[ ] is
gi en by
ρ(i)= 6jia(i)
1a(i)
2···a(i)
ki, ji≥1, ki≥0,(49)
wi h he le e s a(i)
1, a(i)
2, . . . , a(i)
kieach belonging o [5]. The sec ion ρ(0) is o he
same o m excep ha j0= 0 is also allowed. One may e i y ha ρmay be
decomposed as desc ibed abo e since i mus s a wi h a le e in [4], wi h no 6
ollowing a 5.
Le us ep esen he wo kinds o colo ed squa es in a Pell iling by band w
s anding o black and whi e, espec i ely. De ine he unc ion δ: [5] → P2by
δ(1) = b2,δ(2) = bw,δ(3) = wb,δ(4) = w2, and δ(5) = d. Conside eplacing each
sec ion xiρ(i)o ρ, whe e ρ(i)is gi en by (49), wi h he iling Tide ined by
Ti=djiδ(a(i)
1)δ(a(i)
2)···δ(a(i)
ki),0≤i≤ ,
whe e he wo blank posi ions a e o be illed by he i s and second squa es,
espec i ely, o δ(xi). Le g(ρ) = T0T1···T , whe e i is unde s ood ha he ilings
Tia e conca ena ed.
INTEGERS: 25 (2025) 25
One may e i y g(ρ)∈ Qn o all ρ∈ Rn. To e e se g, suppose λ∈ Tncan be
w i en as λ=λ′dλ′′, whe e λ′is o e en leng h and con ains a leas one squa e and
dis he le mos domino o which λcan be decomposed in his manne . I no such d
exis s, hen we ake λ′=λ. No e ha λ′may hen be w i en as λ′=dℓsy1···yms′
o some ℓ, m ≥0, whe e each yiis a sequence o wo (colo ed) squa es o a single
domino and s, s′deno e squa es (colo unspeci ied). We hen econs uc he ini ial
sec ion x0ρ(0) o g−1(λ) by le ing x0=δ−1(ss′) and pu ing j0=ℓ,k0=m, and
a(0)
j=δ−1(yj) o each 1 ≤j≤min he decomposi ion o ρ(0) gi en in (49).
I λ′=λ, hen we a e done. O he wise, we epea he abo e p ocedu e using he
sub iling dλ′′ in place o λ. This yields a second sec ion o g−1(λ) o he o m in (49)
which con ains a leas one 6 (i.e., j1≥1). We hen epea he p ocedu e un il no
iles o λ emain. No e ha each sec ion, which we will deno e by xiρ(i)as be o e,
ha is ob ained om an i e a ion o he p ocedu e con ains a leas one 6, excep
o possibly he i s . Le ρ=g−1(λ) be he 6-a y wo d ob ained by conca ena ing
hese a ious sec ions om le o igh in he o de hey a ose. One may e i y
ρ∈ Rn o all λand ha his p ocedu e de ined on λis indeed he in e se o g.
Hence, he mapping gp o ides he desi ed bijec ion be ween Rnand Tn, which
comple es he p oo o (18). Fu he , i is seen ha he numbe o uns o din λ
whe ein he i s din he un s a s a an odd posi ion, excluding a possible ini ial
un o d, is always one less han he numbe o sec ions xiρ(i)in ρ.
No e ha (1) ollows om he well-known ac |Cn|=F2n o n≥1, as he
igh -hand side is seen o enume a e he membe s o Cnby conside ing all possible
sequences o mul iplici ies o he a ious pa sizes. Fo a bijec i e p oo o an
equi alen s a emen o (1), w i en as a sum o e he composi ions o n, see [17,
p. 46, Exe cise 14 ]. We conclude by ex ending ou a gumen s abo e o p o ide a
combina o ial explana ion o (3).
P oo o (3).No e i s ha (3) may be w i en equi alen ly as
2Pn−1=X
β∗=n
2|β|mn−1(β)1β12β2···(n−1)βn−1, n ≥1,(50)
whe e he sum is o e all β= (β1, . . . , βn−1) such ha β∗= 2β1+···+nβn−1=n.
Equa ion (50) holds i ially o n= 1, so we may assume n≥2. Recall ha C′
n
deno es he subse o Cnin whose membe s no pa wi h subsc ip one is allowed.
Le Unbe he se o o de ed pai s (λ, ω), whe e λ∈ C′
nand ωis a bina y wo d
whose leng h is he numbe o pa s o λ. Then we ha e ha he igh side o (50)
gi es |Un|and we seek o show |Un|= 2Pn−1 o n≥2.
To do so, we desc ibe a ecu si e cons uc ion o ob aining he membe s o Un
o n > 2 s a ing wi h hose in U2={(22,0),(22,1)}. Conside an (n−2)-s ep
p ocedu e whe e, in each s ep, one o he ollowing i e ope a ions is applied o he