Note on some representations of general solutions to homogeneous linear difference equations

Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 https://doi.org/10.1186/s13662-020-02944-y RESEARCH Open Access Note on some representations of general solutions to homogeneous linear difference equations Stevo Stevi´ c1,2,3*, Bratislav Iriˇ canin4,5, Witold Kosmala6and Zdenˇ ek Šmarda3 *Correspondence: [email protected] 1Mathematical Institute of the Serbian Academy of Sciences, Knez Mihailova 36/III, 11000 Beograd, Serbia 2Department of Medical Research, China Medical University Hospital, China Medical University, Taichung 40402, Taiwan, Republic of China Full list of author information is available at the end of the article Abstract It is known that every solution to the second-order difference equation xn=xn–1 +xn–2 =0,n≥2, can be written in the following form xn=x0fn–1 +x1fn,where fnis the Fibonacci sequence. Here we find all the homogeneous linear difference equations with constant coefficients of any order whose general solution have a representation of a related form. We also present an interesting elementary procedure for finding a representation of general solution to any homogeneous linear difference equation with constant coefficients in terms of the coefficients of the equation, initial values, and an extension of the Fibonacci sequence. This is done for the case when all the roots of the characteristic polynomial associated with the equation are mutually different, and then it is shown that such obtained representation also holds in other cases. It is also shown that during application of the procedure the extension of the Fibonacci sequence appears naturally. MSC: 39A10 Keywords: Homogeneous linear difference equation with constant coefficients; General solution; Representation of solutions; Fibonacci sequence 1 Introduction Let Ndenote the set of all positive integers, N0=N∪{0},andZbe the set of all integers. If p,q∈Zare such that p≤q,thenweusethenotationj=p,qfor the expression j= p,p+1,...,q. There has been some interest in difference equations and their applications for a long time (see, e.g., [1–37] and the references therein). Since the time of de Moivre it has been known that the homogeneous linear difference equations with constant coefficients are solvable (see [6–8], see also [4,9]). For some later presentations of the theory, see, e.g., [5,10,11,13,14,17,18]. For some recent results on solvability, invariants, and their applications, see, e.g., [2,3,19–22,24–36] and the related references therein. From a formula by de Moivre for solving homogeneous linear difference equations of second order [7,8], general solution to the following equation is specially obtained: xn–xn–1 –xn–2 =0, n≥2. (1) ©The Author(s) 2020. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 2 of 13 The Fibonacci sequence (fn)n≥0is the solution to equation (1)withx0=0andx1=1 (thesolutioncan be explicitlyfoundinD.Bernoulli’spaper [4],aswellasthemethodthat is usually used in solving homogeneous linear difference equations with constant coefficients nowadays). The sequence has been investigated for several centuries, and there are a lot of properties and relations which are satisfied by the sequence (see, for example, [1,12,16,37]). The sequence is usuallydefined on Nor N0,butitiseasytoseethatitcan be defined on any set of integers of the form n≥n0,wheren0∈Zisfixed,aswellason the whole Z(see also the end of this section). An interesting fact related to the Fibonacci sequence is that every solution to equation (1) can be written in the following form: xn=x0fn–1 +x1fn,n∈N0.(2) There are several ways to prove (2). One of the ways is by using known theory. It is well known that general solution to the equation Lk, a(xn):=xn–a1xn–1 –···–akxn–k=0, n∈N0,(3) where k∈N, a=(a1,...,ak), aj∈R,j=1,k,andak=0,isak-dimensional linear space [5,10,11,13,14,17,18]. Let Sol(Lk, a):={(xn)n≥–k:Lk, a(xn)≡0}(the space of all solutions to equation (3)). It is also known that there is a natural linear isomorphism Ikbetween the k-dimensional real vector space Rkand the space Sol(Lk, a). Namely, if ( ej)k j=1 ⊂Rkis thecanonical basis of Rk,i.e., ej=(0,...,0,1,0,...,0),j=1,k, where 1is the jthcoordinate in the vector, and ˜ x( v)=(xn( v))n≥–k∈Sol(Lk, a) is the solution corresponding to the vector  v∈Rk(the set of initial values), then for every  v=k j=1 vj ej∈Rkwe have ˜ x( v)=Ik( v)=Ikk  j=1 vj ej=k  j=1 vjIk( ej)= k  j=1 vj˜ x( ej). (4) If k=2,thenequation(3)becomes xn–a1xn–1 –a2xn–2 =0, n∈N0,(5) where a2=0,andwehave e1=(1,0) and  e2=(0,1). Since f–1 =1, f0=0 and f1=1, (6) we see that the solution to equation (1) corresponding to the vector  e1is (fn–1)n∈N0,while the one corresponding to the vector  e2is (fn)n∈N0.Sinceevery v∈R2has the form  v= v1 e1+v2 e2, by using the relations in (4), we have xn( v)n∈N0=I2( v)=v1I2( e1)+v2I2( e2)=v1(fn–1)n∈N0+v2(fn)n∈N0.(7) From (7)withn=0andn= 1, it follows respectively that x0( v)=v1f–1 +v2f0and x1( v)=v1f0+v2f1, from which along with (6) it follows that v1=x0( v)andv2=x1( v). Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 3 of 13 Hence xn( v)=x0( v)fn–1 +x1( v)fn,n∈N0,(8) which is a known theoretical way how relation (2)isobtained. Remark 1Relation(2) can bealso obtainedinaquitesimpleelementarywaybyusing the de Moivre formula (see, e.g., [30]). Representation formula (2) suggests the following natural and interesting question. Question Which homogeneous linear difference equations with constant coefficients have the general solution representation formula of the form in (2)? Some recent representations of general solutions to some solvable difference equations and systems can be found, e.g., in [26–31,33–36]. Here we give an answer to the question. Beside this we also explain an interesting elementary procedure for finding a representation of general solution to equation (3)in terms of the coefficients a1,a2,...,ak, initial values x0,x1,...,xk–1, and an extension of the Fibonaccisequence.Therepresentationandsomedetailsshouldbefolklore,butthewhole procedure leading to it could be new and is interesting. Before we state and prove the main results in this note, recall that since ak=0,every solution to equation (3) can be defined for all negative values of indices n,byusingthe following obvious consequence of the equation: xn–k=xn–k–1 j=1 ajxn–j ak. For example, for n=–1,weget x–(k+1) =x–1 –k–1 j=1 ajx–(j+1) ak, (this is, for example, used to get the value of f–1 in (6)). 2 Main results Thissectionformulatesandprovesthemainresultsinthispaper.First,wegivean answer to the above question. 2.1 Answer to the question Now we turn to the above question when k=2,a1∈R,anda2= 0, that is, to find all a1 and a2such that the following representation holds: xn( v)=x0( v)yn–1( v0)+x1( v)yn( v0), n∈N0,(9) for some  v0∈R2and for every solution to equation (5), as well as to the corresponding question for the case of equation (3) for arbitrary k∈N\{1}. The following theorem gives an answer to the question. Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 4 of 13 Theorem 1 Consider equation (3)with n≥k≥2, aj∈R,j=1,k,and ak=0.Then there is a vector  v0=(v1 0,...,vk 0)∈Rkand ˜ y( v0)∈Sol(Lk, a)such that yj( v0)=vj+1 0,j=0,k–1, and that xn( v)=x0( v)yn–1( v0)+x1( v)yn( v0)+···+xk–1( v)yn+k–2( v0) (10) for every n ∈N0,vector  v∈Rk,and solution ˜ x( v)to equation (3)if and only if k =2,a2=1, and  v0=(v1 0,v2 0)=(0,1). Proof Assume that representation (10) holds. Then for n=0wehave x0( v)=x0( v)y–1( v0)+x1( v)y0( v0)+···+xk–1( v)yk–2( v0) (11) for every  v∈Rk, i.e., the identity y–1( v0)–1x0+y0( v0)x1+···+yk–2( v0)xk–1 ≡0 (12) must hold for every (x0,x1,...,xk–1)∈Rk, from which it follows that y–1( v0)=1, yj( v0)=0, j=0,k–2. (13) From this and using the fact that ˜ y( v0)∈Sol(Lk, a), we get yk–1( v0)= k  j=1 ajyk–1–j( v0)=ak. (14) For n=1wehave x1( v)=x0( v)y0( v0)+x1( v)y1( v0)+···+xk–2( v)yk–2( v0)+xk–1( v)yk–1( v0) (15) for every  v∈Rk.From(13)–(15), it follows that the identity x1–akxk–1 ≡0 (16) mustholdforevery x1,xk–1 ∈R,whichisonlypossibleifk=2andak=a2=1,fromwhich along with (13)and(14) it follows that 0=y0( v0)=v1 0and 1=y1( v0)=v2 0. Now assume that k=2,a2=1and v0=(0,1). Then (3)becomes xn–a1xn–1 –xn–2 =0, n≥2. (17) An easy computation shows that yn( v0)=λn 1–λn 2 λ1–λ2=λn 1–λn 2 a2 1+4, (18) Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 5 of 13 where λ1=a1+a2 1+4 2and λ2=a1–a2 1+4 2. On the other hand, by calculating the solution to (17) with initial values x0( v)=v1and x1( v)=v2,using(18) and Viete’s formulas, we obtain xn( v)=(x0( v)λ2–x1( v))λn 1+(x1( v)–x0( v)λ1)λn 2 λ2–λ1 =–x0( v)λ1λ2λn–1 1–λn–1 2 λ1–λ2+x1( v)λn 1–λn 2 λ1–λ2 =x0( v)yn–1( v0)+x1( v)yn( v0) (19) for every  v=(v1,v2)=(x0( v),x1( v)), showing that representation (10)holdsinthiscase,as desired.  2.2 A representation of general solution to equation (3) Theorem 1shows that for the case k= 2 the solution to equation (3) satisfying the initial conditionsx0=0andx1=1 isofsomerepresentationimportanceforthegeneralsolution to the difference equation. It is interesting to find the solution to equation (3) which naturally generalizes the Fibonacci sequence and at the same time plays the corresponding role in representation of general solution to the equation. Here we present an analysis which naturally leads to the solution. The analysis will show that the solution satisfies the initial conditions xj=0, j=0,k–2, xk–1 =1. (20) The solution can be found also by using some other methods, but our aim is to get it in a direct and elementary way, that is, without using any non-elementary theorem. Togiveananswertotheproblem,weuseherethe procedurewhichsomereadersmight have seen rather in linear algebra (in finding nth powers of matrices) than in dealing with real or complex numbers. This time we will apply it to the nth powers of numbers. Since the roots λ1,2 =1±√5 2 of the characteristic polynomial P2(λ)=λ2–λ–1 associated with difference equation (1) are different, here we assume that the zeros λj, j=1,k, of the characteristic polynomial Pk(λ)=λk–k  i=1 aiλk–i(21) Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 6 of 13 associated with equation (3) are mutually different, that is, λi=λj,i=j,fori,j∈ {1,2,...,k}. In this case, general solution to equation (3) has the following form: xn=k  j=1 cjλn j,n∈N0, (22) (the result essentially known to D. Bernoulli yet, [4]). Note that λk j=k  i=1 aiλk–i j(23) for each j∈{1,2,...,k}. By multiplying equality (23)byλj, then usingagain the equality andsomesimplecalculations, we have λ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) where a(i) k+1 :=a1ai+ai+1,i=1,k–1, a(i) k+1 :=a1ak. (25) Hence, the quantity λk+1 jhas the same type of representation as λk j, but with different coefficients, which are given by the relations in (25). Assume that we have proved λn j=k  i=1 a(i) nλk–i j(26) for some n≥k+1. Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 7 of 13 Then, as above, by multiplying relation (26)byλj, suitable grouping of summands, and application of equality (23), after some simple calculations, it follows that λ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) where a(i) n+1 :=aia(1) n+a(i+1) n,i=1,k–1, a(k) n+1 :=aka(1) n.(28) Fromthe relationsin(23),(28),andthemethodof mathematicalinduction,itfollowsthat relation(26)holdsforeveryn≥k,wherethesequences(a(i) n)n≥0,i=1,k,satisfythesystem of difference equations (28) and the initial conditions a(i) k=ai,i=1,k. To define the sequences (a(i) n), i=1,k,foreveryn∈N0, we should choose the initial values in the following natural way: λn j=k  i=1 a(i) nλk–i j for n=0,k–1,sothat a(i) n=0, i=k–n,a(i) n=1, i=k–n. (29) From (28)wehave 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) for n≥k,whilefrom(29)wehave a(1) n=0, n=0,k–2, a(1) k–1 =1. (31) Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 8 of 13 Hence, the sequence (a(1) n)n∈N0is the solution to difference equation (3) satisfying initial conditions (20), and this is one of the ways how the solution appears naturally. From the relations in (28)wealsohave 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) for n≥k. Employing relation (32)in(26), we obtain the following representation of the sequence (λn j)n∈N0intermsofthepowersλl j,l=0,k–1,coefficientsofequation(3),andthesequence (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 the order of summation in formula (33) and using a change of variables of indices, we have λ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  t=1 λk–t jat+s–1. (34) Employing(34)in(22),itfollowsthatthegeneralsolutiontoequation(3)inthecasewhen all the roots λj,j=1,k, of the characteristic polynomial associated with the equation are mutually different has the following representation: xn=k  j=1 cj k  s=1 a(1) n–s k–s+1  t=1 λk–t jat+s–1,n∈N0. (35) By changing the order of summation in (35), we have xn=k  s=1 a(1) n–s k–s+1  t=1 at+s–1 k  j=1 cjλk–t j,n∈N0. (36) Now note that k  j=1 cjλk–t j=xk–t(37) (see (22)). Stevi´ cetal.Advances in Difference Equations (2020) 2020:486 Page 9 of 13 Combining (36)and(37), we have xn=k  s=1 a(1) n–s k–s+1  t=1 at+s–1xk–t,n∈N0. (38) Byusingthechange ofvariables j=k–t,relation(38)canbewritteninthefollowingway: xn=k  s=1 a(1) n–s k–1  j=s–1ak–j+s–1xj,n∈N0, (39) which is a formula for general solution to equation (3)intermsoftherootsλj,j=1,k,of the characteristic polynomial associated with the equation, coefficients of the equation, and the sequence a(1) n. By changing the order of summation in formula (39), we get xn=k–1  j=0 xj j  i=0 ak–j+ia(1) n–i–1,n∈N0, (40) or in the developed form, the following nice formula: 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 for n∈N0. Fromtheaboveconsiderationweseethatwehavegivenaninterestingelementaryproof of the following theorem, which should be folklore. Theorem2 Consider equation (3)with n≥k≥2, aj∈R,j=1,k,ak=0.Assume that the zeros λj,j=1,k,of the characteristic polynomial associated with the equation are mutually different.If (a(1) n)n∈N0is the solution to the equation satisfying the initial conditions in (20), then general solution to the equation can be written in the form (39), aswellasinthe equivalent form (40). Remark 2 In the case when all the zeros λj,j=1,k, of the characteristic polynomial associated with equation (3) are mutually different, then the solution (a(1) n)n∈N0in Theorem 2 has the following nice closed form formula: a(1) n=k  j=1 λn j i=j(λj–λi)=k  j=1 λn j P k(λj),n∈N0. (41) Formula (41) follows from the following relations: k  j=1 λl j P k(λj)=0 for l=0,k–2,and k  j=1 λk–1 j P k(λj)=1,