S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486
h ps://doi.o g/10.1186/s13662-020-02944-y
RESEARCH Open Access
No e on some ep esen a ions o gene al
solu ions o homogeneous linea di e ence
equa ions
S e o S e i´
c1,2,3*, B a isla I iˇ
canin4,5, Wi old Kosmala6and Zdenˇ
ek Šma da3
*Co espondence: [email p o ec ed]
1Ma hema ical Ins i u e o he
Se bian Academy o Sciences, Knez
Mihailo a 36/III, 11000 Beog ad,
Se bia
2Depa men o Medical Resea ch,
China Medical Uni e si y Hospi al,
China Medical Uni e si y, Taichung
40402, Taiwan, Republic o China
Full lis o au ho in o ma ion is
a ailable a he end o he a icle
Abs ac
I is known ha e e y solu ion o he second-o de diffe ence equa ion
xn=xn–1 +xn–2 =0,n≥2, can be w i en in he ollowing o m xn=x0 n–1 +x1 n,whe e
nis he Fibonacci sequence. He e we find all he homogeneous linea diffe ence
equa ions wi h cons an coefficien s o any o de whose gene al solu ion ha e a
ep esen a ion o a ela ed o m. We also p esen an in e es ing elemen a y
p ocedu e o finding a ep esen a ion o gene al solu ion o any homogeneous
linea diffe ence equa ion wi h cons an coefficien s in e ms o he coefficien s o he
equa ion, ini ial alues, and an ex ension o he Fibonacci sequence. This is done o
he case when all he oo s o he cha ac e is ic polynomial associa ed wi h he
equa ion a e mu ually diffe en , and hen i is shown ha such ob ained
ep esen a ion also holds in o he cases. I is also shown ha du ing applica ion o he
p ocedu e he ex ension o he Fibonacci sequence appea s na u ally.
MSC: 39A10
Keywo ds: Homogeneous linea diffe ence equa ion wi h cons an coefficien s;
Gene al solu ion; Rep esen a ion o solu ions; Fibonacci sequence
1 In oduc ion
Le Ndeno e he se o all posi i e in ege s, N0=N∪{0},andZbe he se o all in ege s.
I p,q∈Za e such ha p≤q, henweuse heno a ionj=p,q o he exp ession j=
p,p+1,...,q.
The e has been some in e es in diffe ence equa ions and hei applica ions o a long
ime (see, e.g., [1–37] and he e e ences he ein). Since he ime o de Moi e i has been
known ha he homogeneous linea diffe ence equa ions wi h cons an coefficien s a e
sol able (see [6–8], see also [4,9]). Fo some la e p esen a ions o he heo y, see, e.g.,
[5,10,11,13,14,17,18]. Fo some ecen esul s on sol abili y, in a ian s, and hei ap-
plica ions, see, e.g., [2,3,19–22,24–36] and he ela ed e e ences he ein.
F om a o mula by de Moi e o sol ing homogeneous linea diffe ence equa ions o
second o de [7,8], gene al solu ion o he ollowing equa ion is specially ob ained:
xn–xn–1 –xn–2 =0, n≥2. (1)
©The Au ho (s) 2020. This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which pe mi s use,
sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e app op ia e c edi o he o iginal
au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence, and indica e i changes we e made. The images o o he
hi d pa y ma e ial in his a icle a e included in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line
o he ma e ial. I ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed by
s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he copy igh holde . To iew a
copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 2 o 13
The Fibonacci sequence ( n)n≥0is he solu ion o equa ion (1)wi hx0=0andx1=1
( hesolu ioncan be explici ly oundinD.Be noulli’spape [4],aswellas heme hod ha
is usually used in sol ing homogeneous linea diffe ence equa ions wi h cons an coe -
ficien s nowadays). The sequence has been in es iga ed o se e al cen u ies, and he e
a e a lo o p ope ies and ela ions which a e sa isfied by he sequence (see, o example,
[1,12,16,37]). The sequence is usuallydefined on No N0,bu i iseasy osee ha i can
be defined on any se o in ege s o he o m n≥n0,whe en0∈Zisfixed,aswellason
he whole Z(see also he end o his sec ion).
An in e es ing ac ela ed o he Fibonacci sequence is ha e e y solu ion o equa ion
(1) can be w i en in he ollowing o m:
xn=x0 n–1 +x1 n,n∈N0.(2)
The e a e se e al ways o p o e (2). One o he ways is by using known heo y. I is well
known ha gene al solu ion o he equa ion
Lk,
a(xn):=xn–a1xn–1 –···–akxn–k=0, n∈N0,(3)
whe e k∈N,
a=(a1,...,ak), aj∈R,j=1,k,andak=0,isak-dimensional linea space
[5,10,11,13,14,17,18]. Le Sol(Lk,
a):={(xn)n≥–k:Lk,
a(xn)≡0}( he space o all solu ions
o equa ion (3)). I is also known ha he e is a na u al linea isomo phism Ikbe ween
he k-dimensional eal ec o space Rkand he space Sol(Lk,
a). Namely, i (
ej)k
j=1 ⊂Rkis
hecanonical basis o Rk,i.e.,
ej=(0,...,0,1,0,...,0),j=1,k, whe e 1is he j hcoo dina e
in he ec o , and ˜
x(
)=(xn(
))n≥–k∈Sol(Lk,
a) is he solu ion co esponding o he ec o

∈Rk( he se o ini ial alues), hen o e e y 
=k
j=1 j
ej∈Rkwe ha e
˜
x(
)=Ik(
)=Ikk

j=1 j
ej=k

j=1 jIk(
ej)= k

j=1 j˜
x(
ej). (4)
I k=2, henequa ion(3)becomes
xn–a1xn–1 –a2xn–2 =0, n∈N0,(5)
whe e a2=0,andweha e
e1=(1,0) and 
e2=(0,1). Since
–1 =1, 0=0 and 1=1, (6)
we see ha he solu ion o equa ion (1) co esponding o he ec o 
e1is ( n–1)n∈N0,while
he one co esponding o he ec o 
e2is ( n)n∈N0.Sincee e y
∈R2has he o m 
=
1
e1+ 2
e2, by using he ela ions in (4), we ha e
xn(
)n∈N0=I2(
)= 1I2(
e1)+ 2I2(
e2)= 1( n–1)n∈N0+ 2( n)n∈N0.(7)
F om (7)wi hn=0andn= 1, i ollows espec i ely ha x0(
)= 1 –1 + 2 0and
x1(
)= 1 0+ 2 1, om which along wi h (6) i ollows ha 1=x0(
)and 2=x1(
).
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 3 o 13
Hence
xn(
)=x0(
) n–1 +x1(
) n,n∈N0,(8)
which is a known heo e ical way how ela ion (2)isob ained.
Rema k 1Rela ion(2) can bealso ob ainedinaqui esimpleelemen a ywaybyusing he
de Moi e o mula (see, e.g., [30]).
Rep esen a ion o mula (2) sugges s he ollowing na u al and in e es ing ques ion.
Ques ion Which homogeneous linea diffe ence equa ions wi h cons an coefficien s
ha e he gene al solu ion ep esen a ion o mula o he o m in (2)?
Some ecen ep esen a ions o gene al solu ions o some sol able diffe ence equa ions
and sys ems can be ound, e.g., in [26–31,33–36].
He e we gi e an answe o he ques ion. Beside his we also explain an in e es ing el-
emen a y p ocedu e o finding a ep esen a ion o gene al solu ion o equa ion (3)in
e ms o he coefficien s a1,a2,...,ak, ini ial alues x0,x1,...,xk–1, and an ex ension o he
Fibonaccisequence.The ep esen a ionandsomede ailsshouldbe olklo e,bu hewhole
p ocedu e leading o i could be new and is in e es ing.
Be o e we s a e and p o e he main esul s in his no e, ecall ha since ak=0,e e y
solu ion o equa ion (3) can be defined o all nega i e alues o indices n,byusing he
ollowing ob ious consequence o he equa ion:
xn–k=xn–k–1
j=1 ajxn–j
ak.
Fo example, o n=–1,wege
x–(k+1) =x–1 –k–1
j=1 ajx–(j+1)
ak,
( his is, o example, used o ge he alue o –1 in (6)).
2 Main esul s
Thissec ion o mula esandp o es hemain esul sin hispape .Fi s ,wegi ean answe
o he abo e ques ion.
2.1 Answe o he ques ion
Now we u n o he abo e ques ion when k=2,a1∈R,anda2= 0, ha is, o find all a1
and a2such ha he ollowing ep esen a ion holds:
xn(
)=x0(
)yn–1(
0)+x1(
)yn(
0), n∈N0,(9)
o some 
0∈R2and o e e y solu ion o equa ion (5), as well as o he co esponding
ques ion o he case o equa ion (3) o a bi a y k∈N {1}.
The ollowing heo em gi es an answe o he ques ion.
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 4 o 13
Theo em 1 Conside equa ion (3)wi h n≥k≥2, aj∈R,j=1,k,and ak=0.Then he e
is a ec o 
0=( 1
0,..., k
0)∈Rkand ˜
y(
0)∈Sol(Lk,
a)such ha
yj(
0)= j+1
0,j=0,k–1,
and ha
xn(
)=x0(
)yn–1(
0)+x1(
)yn(
0)+···+xk–1(
)yn+k–2(
0) (10)
o e e y n ∈N0, ec o 
∈Rk,and solu ion ˜
x(
) o equa ion (3)i and only i k =2,a2=1,
and 
0=( 1
0, 2
0)=(0,1).
P oo Assume ha ep esen a ion (10) holds. Then o n=0weha e
x0(
)=x0(
)y–1(
0)+x1(
)y0(
0)+···+xk–1(
)yk–2(
0) (11)
o e e y 
∈Rk, i.e., he iden i y
y–1(
0)–1x0+y0(
0)x1+···+yk–2(
0)xk–1 ≡0 (12)
mus hold o e e y (x0,x1,...,xk–1)∈Rk, om which i ollows ha
y–1(
0)=1, yj(
0)=0, j=0,k–2. (13)
F om his and using he ac ha ˜
y(
0)∈Sol(Lk,
a), we ge
yk–1(
0)= k

j=1 ajyk–1–j(
0)=ak. (14)
Fo n=1weha e
x1(
)=x0(
)y0(
0)+x1(
)y1(
0)+···+xk–2(
)yk–2(
0)+xk–1(
)yk–1(
0) (15)
o e e y 
∈Rk.F om(13)–(15), i ollows ha he iden i y
x1–akxk–1 ≡0 (16)
mus hold o e e y x1,xk–1 ∈R,whichisonlypossiblei k=2andak=a2=1, omwhich
along wi h (13)and(14) i ollows ha 0=y0(
0)= 1
0and 1=y1(
0)= 2
0.
Now assume ha k=2,a2=1and
0=(0,1). Then (3)becomes
xn–a1xn–1 –xn–2 =0, n≥2. (17)
An easy compu a ion shows ha
yn(
0)=λn
1–λn
2
λ1–λ2=λn
1–λn
2
a2
1+4, (18)
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 5 o 13
whe e
λ1=a1+a2
1+4
2and λ2=a1–a2
1+4
2.
On he o he hand, by calcula ing he solu ion o (17) wi h ini ial alues x0(
)= 1and
x1(
)= 2,using(18) and Vie e’s o mulas, we ob ain
xn(
)=(x0(
)λ2–x1(
))λn
1+(x1(
)–x0(
)λ1)λn
2
λ2–λ1
=–x0(
)λ1λ2λn–1
1–λn–1
2
λ1–λ2+x1(
)λn
1–λn
2
λ1–λ2
=x0(
)yn–1(
0)+x1(
)yn(
0) (19)
o e e y 
=( 1, 2)=(x0(
),x1(
)), showing ha ep esen a ion (10)holdsin hiscase,as
desi ed. 
2.2 A ep esen a ion o gene al solu ion o equa ion (3)
Theo em 1shows ha o he case k= 2 he solu ion o equa ion (3) sa is ying he ini ial
condi ionsx0=0andx1=1 iso some ep esen a ionimpo ance o hegene alsolu ion
o he diffe ence equa ion.
I is in e es ing o find he solu ion o equa ion (3) which na u ally gene alizes he Fi-
bonacci sequence and a he same ime plays he co esponding ole in ep esen a ion o
gene al solu ion o he equa ion. He e we p esen an analysis which na u ally leads o he
solu ion. The analysis will show ha he solu ion sa isfies he ini ial condi ions
xj=0, j=0,k–2,
xk–1 =1. (20)
The solu ion can be ound also by using some o he me hods, bu ou aim is o ge i in a
di ec and elemen a y way, ha is, wi hou using any non-elemen a y heo em.
Togi eananswe o hep oblem,weusehe e he p ocedu ewhichsome eade smigh
ha e seen a he in linea algeb a (in finding n h powe s o ma ices) han in dealing wi h
eal o complex numbe s. This ime we will apply i o he n h powe s o numbe s.
Since he oo s
λ1,2 =1±√5
2
o he cha ac e is ic polynomial
P2(λ)=λ2–λ–1
associa ed wi h diffe ence equa ion (1) a e diffe en , he e we assume ha he ze os λj,
j=1,k, o he cha ac e is ic polynomial
Pk(λ)=λk–k

i=1 aiλk–i(21)

S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 6 o 13
associa ed wi h equa ion (3) a e mu ually diffe en , ha is, λi=λj,i=j, o i,j∈
{1,2,...,k}.
In his case, gene al solu ion o equa ion (3) has he ollowing o m:
xn=k

j=1 cjλn
j,n∈N0, (22)
( he esul essen ially known o D. Be noulli ye , [4]).
No e ha
λk
j=k

i=1 aiλk–i
j(23)
o each j∈{1,2,...,k}.
By mul iplying equali y (23)byλj, hen usingagain he equali y andsomesimplecalcu-
la ions, we ha e
λk+1
j=k

i=1 aiλk–i+1
j=a1λk
j+k

i=2 aiλk–i+1
j
=a1k

i=1 aiλk–i
j+k–1

i=1 ai+1λk–i
j
=a1akλ0
j+k–1

i=1 (a1ai+ai+1)λk–i
j
=k

i=1 a(1)
k+1λk–i
j, (24)
whe e
a(i)
k+1 :=a1ai+ai+1,i=1,k–1, a(i)
k+1 :=a1ak. (25)
Hence, he quan i y λk+1
jhas he same ype o ep esen a ion as λk
j, bu wi h diffe en
coefficien s, which a e gi en by he ela ions in (25).
Assume ha we ha e p o ed
λn
j=k

i=1 a(i)
nλk–i
j(26)
o some n≥k+1.
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 7 o 13
Then, as abo e, by mul iplying ela ion (26)byλj, sui able g ouping o summands, and
applica ion o equali y (23), a e some simple calcula ions, i ollows ha
λn+1
j=k

i=1 a(i)
nλk–i+1
j=a(1)
nλk
j+k

i=2 a(i)
nλk–i+1
j
=a(1)
nk

i=1 aiλk–i
j+k–1

i=1 a(i+1)
nλk–i
j
=aka(1)
nλ0
j+k–1

i=1 aia(1)
n+a(i+1)
nλk–i
j
=k

i=1 a(i)
n+1λk–i
j, (27)
whe e
a(i)
n+1 :=aia(1)
n+a(i+1)
n,i=1,k–1,
a(k)
n+1 :=aka(1)
n.(28)
F om he ela ionsin(23),(28),and heme hodo ma hema icalinduc ion,i ollows ha
ela ion(26)holds o e e yn≥k,whe e hesequences(a(i)
n)n≥0,i=1,k,sa is y hesys em
o diffe ence equa ions (28) and he ini ial condi ions
a(i)
k=ai,i=1,k.
To define he sequences (a(i)
n), i=1,k, o e e yn∈N0, we should choose he ini ial
alues in he ollowing na u al way:
λn
j=k

i=1 a(i)
nλk–i
j
o n=0,k–1,so ha
a(i)
n=0, i=k–n,a(i)
n=1, i=k–n. (29)
F om (28)weha e
a(1)
n=a1a(1)
n–1 +a(2)
n–1
=a1a(1)
n–1 +a2a(1)
n–2 +a(3)
n–2
···
=a1a(1)
n–1 +a2a(1)
n–2 +···+aka(1)
n–k(30)
o n≥k,while om(29)weha e
a(1)
n=0, n=0,k–2, a(1)
k–1 =1. (31)
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 8 o 13
Hence, he sequence (a(1)
n)n∈N0is he solu ion o diffe ence equa ion (3) sa is ying ini ial
condi ions (20), and his is one o he ways how he solu ion appea s na u ally.
F om he ela ions in (28)wealsoha e
a(i)
n=aia(1)
n–1 +a(i+1)
n–1
=aia(1)
n–1 +ai+1a(1)
n–2 +a(i+2)
n–2
···
=aia(1)
n–1 +ai+1a(1)
n–2 +···+aka(1)
n–k+i–1
=k

l=i
ala(1)
n–l+i–1 (32)
o n≥k.
Employing ela ion (32)in(26), we ob ain he ollowing ep esen a ion o he sequence
(λn
j)n∈N0in e mso hepowe sλl
j,l=0,k–1,coefficien so equa ion(3),and hesequence
(a(1)
n)n∈N0:
λn
j=k

i=1
λk–i
j
k

l=i
ala(1)
n–l+i–1,n∈N0. (33)
By changing he o de o summa ion in o mula (33) and using a change o a iables o
indices, we ha e
λn
j=k

i=1
λk–i
j
k

l=i
ala(1)
n–l+i–1 =k

l=1
l

i=1
λk–i
jala(1)
n–l+i–1
=k

s=1 a(1)
n–s
k–s+1

=1
λk–
ja +s–1. (34)
Employing(34)in(22),i ollows ha hegene alsolu ion oequa ion(3)in hecasewhen
all he oo s λj,j=1,k, o he cha ac e is ic polynomial associa ed wi h he equa ion a e
mu ually diffe en has he ollowing ep esen a ion:
xn=k

j=1 cj
k

s=1 a(1)
n–s
k–s+1

=1
λk–
ja +s–1,n∈N0. (35)
By changing he o de o summa ion in (35), we ha e
xn=k

s=1 a(1)
n–s
k–s+1

=1 a +s–1
k

j=1 cjλk–
j,n∈N0. (36)
Now no e ha
k

j=1 cjλk–
j=xk– (37)
(see (22)).
S e i´
ce al.Ad ances in Diffe ence Equa ions (2020) 2020:486 Page 9 o 13
Combining (36)and(37), we ha e
xn=k

s=1 a(1)
n–s
k–s+1

=1 a +s–1xk– ,n∈N0. (38)
Byusing hechange o a iables j=k– , ela ion(38)canbew i enin he ollowingway:
xn=k

s=1 a(1)
n–s
k–1

j=s–1ak–j+s–1xj,n∈N0, (39)
which is a o mula o gene al solu ion o equa ion (3)in e mso he oo sλj,j=1,k,o
he cha ac e is ic polynomial associa ed wi h he equa ion, coefficien s o he equa ion,
and he sequence a(1)
n.
By changing he o de o summa ion in o mula (39), we ge
xn=k–1

j=0 xj
j

i=0 ak–j+ia(1)
n–i–1,n∈N0, (40)
o in he de eloped o m, he ollowing nice o mula:
xn=x0aka(1)
n–1+x1ak–1a(1)
n–1 +aka(1)
n–2+···+xk–1a1a(1)
n–1 +···+aka(1)
n–k
o n∈N0.
F om heabo econside a ionwesee ha weha egi enanin e es ingelemen a yp oo
o he ollowing heo em, which should be olklo e.
Theo em2 Conside equa ion (3)wi h n≥k≥2, aj∈R,j=1,k,ak=0.Assume ha he
ze os λj,j=1,k,o he cha ac e is ic polynomial associa ed wi h he equa ion a e mu u-
ally diffe en .I (a(1)
n)n∈N0is he solu ion o he equa ion sa is ying he ini ial condi ions in
(20), hen gene al solu ion o he equa ion can be w i en in he o m (39), aswellasin he
equi alen o m (40).
Rema k 2 In he case when all he ze os λj,j=1,k, o he cha ac e is ic polynomial asso-
cia ed wi h equa ion (3) a e mu ually diffe en , hen he solu ion (a(1)
n)n∈N0in Theo em 2
has he ollowing nice closed o m o mula:
a(1)
n=k

j=1
λn
j
i=j(λj–λi)=k

j=1
λn
j
P
k(λj),n∈N0. (41)
Fo mula (41) ollows om he ollowing ela ions:
k

j=1
λl
j
P
k(λj)=0
o l=0,k–2,and
k

j=1
λk–1
j
P
k(λj)=1,