Direct solutions of linear non-homogeneous difference equations

Abstract

In this paper, the authors develop a direct method used to solve the initial value problems of a linear non-homogeneous time-invariant difference equation. In this method, the obtained general term of the solution sequence has an explicit formula, which includes coefficients, initial values, and right-side terms of the solved equation only. Furthermore, the authors find that when the solution sequence has a nonzero first term, it satisfies two adjoint linear recursive equations; this usually shows several new features of the solution sequence.

Pan and Pan Advances in Dierence Equations (2016) 2016:108 DOI 10.1186/s13662-016-0839-x

R E S E A R C H Open Access

Direct solutions of linear non-homogeneous difference equations

http://crossmark.crossref.org/dialog/?doi=10.1186/s13662-016-0839-x&domain=pdf

Web End = Shu-Wen Pan1* and Jia-Qiang Pan2

*Correspondence: mailto:[email protected]

Web End [email protected]

1Key Discipline of Automation, School of Information and Electrical Engineering, Zhejiang University City College, Hangzhou, ChinaFull list of author information is available at the end of the article

Abstract

In this paper, the authors develop a direct method used to solve the initial value problems of a linear non-homogeneous time-invariant dierence equation. In this method, the obtained general term of the solution sequence has an explicit formula, which includes coecients, initial values, and right-side terms of the solved equation only. Furthermore, the authors nd that when the solution sequence has a nonzero rst term, it satises two adjoint linear recursive equations; this usually shows several new features of the solution sequence.

MSC: Primary 39A06; secondary 34N05; 03D20

Keywords: backward-shifting matrix; linear non-homogeneous dierence equation; adjoint recursive relation

1 Introduction: backward-shifting matrices of sequences

Let a = {a(k)}k= = (a(), a(), a(), . . ., a(k), . . .) be an innite sequence. We also regard the sequence as a ( ) row vector. Two special sequences are the unit sequence e = {e(k)}k= = {k,}k= (k, is the Kronecker delta) and the null sequence o = {}k=.

For any sequence a, we always assume a(k) = if k < . Thus, we may express all of the backward-shifting (namely right-shifting) sequences of a as a() = {a(k )}k= =

(, a(), a(), a(), . . .), a() = {a(k )}k= = (, , a(), a(), a(), . . .), a() = {a(k )}k= = (, , , a(), a(), a(), . . .), and so on.

In this section, we give mainly attention to the convolution (Cauchy multiplication) of

two sequences. As we know, if the sequence c is a convolution of two sequences a and b, expressed as a b = b a = c, then the general term c(k) of the sequence c is []

c(k) =

k

i=

N. ()

For any sequence a, we have a e = e a = a, and a o = o a = o.

We may construct (dene) a matrix A associated with any sequence a, each row vector of which is corresponding backward-shifting sequence of a, as

2016 Pan and Pan. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

a(i)b(k i) =

k

i=

a(k i)b(i), k

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 2 of 10

N) are all upper triangular Toeplitz matrices.

We denote the sequence, the BS-matrix of which is A, a, and we call a the convolution inverse of a. The general term a(k) of the sequence a (e.g., see []) is the (, k)th entry of the matrix A or Ak. Hence, from the matrix theory we know that a(k) is the (, k)th entry of the adjoint matrix of Ak, which is the algebraic cofactor of the (k, )th entry of Ak, divided by the determinant of Ak. Thus, a() = /a(), and for k > ,

a(k) = ()k a() (k+)

(k

. ()

If the three BS-matrices A, B, and C satisfy AB = BA = C and A is reversible (a() = ), then B = AC = CA, at the same time we have b = a c = c a.

In the second section of this paper, based on these relationships between sequences and their BS-matrices as mentioned above, we develop a direct method used to solve the initial value problem of a linear, time-invariant, non-homogeneous dierence equation. In this method, the general term of solution sequence has an explicit formula, which includes coecients and initial values of the solved equation only. In the third section of this paper, the authors point out that the solution sequence of the initial value problem surely satises two adjoint linear recursive equations, which may give the solution sequence several new features.

2 Direct solutions of linear non-homogeneous difference equations

Linear dierence equations are ubiquitous in many engineering theories and mathematical branches. For example, they appear in the theory of discrete systems and control theory of discrete systems as basic models of the discrete systems [], and discrete-time

A =

a a()

a()

a()

...

=

a() a() a() a() a() a() a()

a() a() a()

...

, ()

and call the innite dimensional, upper triangular Toeplitz matrix the backward-shifting matrix of the sequence a, or simply, the BS-matrix of a []. Obviously, for a given sequence, there exists one and only one BS-matrix corresponding to the sequence.

We may see from () and () that, if a b = b a = c, then AB = BA = C, where A, B, and C are the corresponding BS-matrices; and vice versa.

In the case that the rst term a() of the sequence a is not zero, then the corresponding BS-matrix A is reversible, that is, there exists an inverse matrix A of A making AA = AA = E, where E is the unit matrix. Of course, E also is the BS-matrix of the unit sequence e. Furthermore, we may see that AkAk = AkAk = Ek, where Ak and Ak (k

N) both are the (k + ) (k + ) upper-left sub-matrices of the matrices A and A, respectively, and Ek (k

N) is the (k + ) (k + ) unit matrix. The matrices Ak, Ak

a() a() a(k ) a(k)

a() a() ... a(k ) a(k )

... ... ... ...

... a() a() a() a()

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 3 of 10

signal processing as basic recurrence relations of sampled signals []. In algebraic combinatorics, they are also one of main study topics, tying dierent special sequences in with their generating functions [, ]. For more details, the reader may refer to [].

In this section, by means of the BS-matrices of sequences we give a direct computational method used to solve the initial value problem of a linear, time-invariant, non-homogeneous dierence equation.

Let a = {a(k)}k= be the solution sequence of a non-homogeneous linear dierence equation of order p (p

N),

a(k) + ba(k ) + ba(k ) + + bpa(k p) = dk, k p, ()

which has p given initial values:

a() = a, a() = a, a() = a, . . . , a(p ) = ap, ()

where b (= ) and bk (p k ) are time-invariant coecients of the equation; dk (k p) are innite given (known) numbers.

Theorem . Let a = {a(k)}k= be a solution sequence of the linear dierence equation () with p initial values a(k) = ak (p > k ). Let b = {b(k)}k= be a coecient sequence of the equation, where

b(k) =

, k = ;bk, p k > ;

, k > p.

()

Let c = {c(k)}k= be the right-side term sequence of the equation, where

c(k) = ki= aibki, p > k ;

dk, k p.

()

Then the general term a(k) of a is

a(k) = ak, p > k ; ki= b(i)c(k i) = ki= b(k i)c(i), k p,

()

where b() = , and for k

b(k) = ()k

. ()

Proof We can rewrite equation () as a form of sequence convolution: a b = c, where the general terms of the sequences b and c are shown in () and (). Therefore, denoting the

b() b() b(k ) b(k)

b() ... b(k ) b(k )

... ... ... ...

... b() b()

b()

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 4 of 10

BS-matrices of a, b, and c by A, B and C, respectively, we have AB = C. For b() = , B is

reversible and thus A = CB. Hence, a = c b, that is, equation () holds.

Next, let us see several simple but enlightening examples, in which p is or only.

Example . The Fibonacci sequence f (OEIS A) [] is the solution sequence of a

linear dierence equation of order two: f (k) f (k ) f (k ) = (k ) with two initial values f () = and f () = . We may rewrite it as b f = c, where b = (, , , , , . . .)

and c = (, , , , , . . .). Thus, according to equation (), we have f (k) = i+j=k b(i)c(j) =

b(k )c() = b(k ). Hence the general term f (k) of the Fibonacci sequence when k has a determinant form:

f (k) = ()k

... ...

(k)(k)

. ()

For example, the sixth term and seventh term of the Fibonacci sequence are, respectively,

f () =

= , f () =

= .

Example . The sequences of Chebyshev polynomials, t(x) = {Tk(x)}k= and u(x) =

{Uk(x)}k=, are solution sequences of two identical linear time-invariant dierence equations of order : Tk(x) xTk(x) + Tk(x) = and Uk(x) xUk(x) + Uk(x) = (k )

with dierent initial values T(x) = , T(x) = x, and U(x) = , U(x) = x, respectively (see

[]). Thus, we may rewrite them as t b = ct and u b = cu, where b = (, x, , , , . . .), ct = (, x, , , . . .), and cu = (, , , , . . .) = e. According to (), we obtain U(x) = ,

U(x) = x, and for k ,

Uk(x) = ()k

x

x ...

... ... ... ...

x

x

kk

, ()

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 5 of 10

and T(x) = , T(x) = x, and for k ,

Tk(x) = ()k

x

x ... ... ... ... ...

x x

kk

+ x()k

x

x ... ... ... ... ...

x x

(k)(k)

. ()

Example . The tower of Hanoi puzzle (see []) is an initial value problem of a linear non-homogeneous dierence equation of order : a(k)a(k ) = for k and a() = .

The corresponding sequences b = (, , , , . . .) and c = (, , , , . . .). By using ()-(), we obtain a() = and for k ,

a(k) =

k

i= b

(k i)c(i) =

k

i=

()ki

... ...

(ki)(ki)

ki = k .

Example . Let us solve the non-homogeneous Fibonacci-type linear dierence equation r(k) r(k ) r(k ) = dk (k ) with two initial values r() = and r() = , where dk (k ) are innite given numbers. We may express this equation as a convolution form: b r = c, where b = (, , , , , , . . .) and c = (, , d, d, d, d, . . .). Hence, according to () we have r = c b. We see from Example . that b(k) = f (k + ), the (k + )th Fibonacci number. Thus, the general term of the solution sequence r is that r() = , r() = , and for k ,

r(k) =

k

i=

=

k

i=

c(i)f (k + i) = f (k) + df (k ) + + dkf ().

Remark As we know, traditional methods used for solving linear non-homogeneous dierence equations face several diculties in practical applications. Here, the traditional methods include the classical method (the discrete analogue of the technique of solving linear dierential equations, namely the solution of a non-homogeneous equation is the sum of the general solution of corresponding homogeneous equation and a particular solution of the non-homogeneous equation) [], and the generating function method []

c(i)b(k i) =

k

i=

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 6 of 10

or similar Z-transform method [, ] (usually, the former is used in mathematics, and the latter in engineering theories). Summarily, these methods are all unable to give explicit expressions of the general term of solution sequences by using coecients and the non-homogeneous right-side terms. This is because they always need to nd all complex roots of a polynomial (the characteristic polynomial of the equation). In general and higher order cases, that is very dicult. Besides, nding particular solutions of the non-homogeneous equations as in the classical method, or expanding rational fraction functions as a sum of simple fractions, or nding power series expansions or nding inverse Z-transforms as in the generating function method and Z-transform method, are also very dicult in general cases.

However, by using the direct method developed in this paper, we can directly solve the initial value problems of linear non-homogeneous dierence equations (recursive relation). We can explicitly express the general term of the solution sequence by using the coecients, initial values, and non-homogeneous right-side terms of the solved equation only. This is a distinct dierence of the direct method.

Remark Recently, Birmajer et al. gave another direct expression of the solution sequence for the homogeneous case [], as for k p,

a(k) =

where c(k) = k

i= aibki for p > k , and Bn,k(x, x, . . . ) is the (n, k)th partial Bell polynomial in the variables x, x, . . . , xnk+ (see () of []). Readers may compare it with equation () in the homogeneous case (dk = when k p).

3 Adjoint linear recursive equations

Let a be the solution sequence of the initial value problem of linear non-homogeneous difference equation (). We may nd that the sequence a satises an adjoint linear recursive relation, as shown in the following theorem.

Theorem . Let a be the solution sequence of linear non-homogeneous dierence equation () with initial values shown in (), in which a = . Then the sequence a satises the following so-called adjoint linear recursive equation of the rst kind:

c a = b, ()

that is,

c()a(k) + c()a(k ) + c()a(k ) + + c(k)a() = b(k), k

c() =

p

i=

c(i)

ki

j=

j!(k i)!Bki,j(!b, !b, . . . ),

N, ()

where the sequences b and c are shown in () and (), respectively; b and c are the rst row vectors of the BS-matrices B and C, respectively, that is, b() = , c() =

a , and

for k ,

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 7 of 10

b(k) = ()k

b() b() b(k ) b(k)

b() ... b(k ) b(k )... ... ... ...

... b() b() b()

()

and

c(k) =

()k ak+

c() c() c(k ) c(k)

a c() ... c(k ) c(k )... ... ... ...

... c() c() a c()

. ()

Proof For the initial value problem () and (), we have AB = C, where A, B, and C are BS-matrices of three sequences a, b, and c. The general terms of sequences b and c are shown in () and (). Because b() = and c() = a = , the matrices B and C both are reversible. Hence, we have CA = B, that is, c a = b.

Example . The Lucas sequence l (OEIS A) [] is the solution sequence of a

Fibonacci-type linear dierence equation: l(k) l(k ) l(k ) = (k ), with l() =

and l() = . In this case, b = (, , , , , , . . .) and c = (, , , , , , . . .). Thus, b() = and c() = , and for k ,

b(k) = ()k

... ...

kk

and

c(k) =

()k k+

...

... ... ... ...

kk

=

k+ .

We see from Example . that b(k) = f (k + ), the (k + )th Fibonacci number. Hence, the Lucas sequence satises the following linear recursive relation:

l() + l() + l() + + kl(k ) + kl(k) = k+f (k + ), k

N.

This is a well-known identity for the Lucas numbers.

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 8 of 10

N) of the

rst kind is the solution of linear homogeneous dierence equation of order two: Tk(x)

xTk(x) + Tk(x) = (k ) with T(x) = and T(x) = x. Hence b = (, x, , , , , . . .) and c = (, x, , , , , . . .). We see from Example . that b(k) = Uk(x), the kth Chebyshev polynomial of the second kind. c() = , and for k ,

c(k) = ()k

Example . The sequence t(x) of the Chebyshev polynomials Tk(x) (k

x

x ... ... ... ...

x x

Hence, the adjoint linear recursive relation of the Chebyshev polynomials Tk(x) of the rst

kind is

Tk(x) + xTk(x) + xTk(x) + + xkT(x) + xkT(x) = Uk(x), k

Thus, we get a new identity for the Chebyshev polynomials of the rst kind.

We may give another adjoint linear recursive equation in a similar way, as follows.

Theorem . Let a be the solution sequence of the non-homogeneous linear dierence equation () with initial values shown in (), in which a = . Then the sequence a satises the following so-called adjoint linear recursive equation of the second kind:

c b a = e, ()

that is,

k

i=

kk

= xk.

N.

i

j= c

(j)b(i j)a(k i) = , k > , ()

where the sequences b and c are shown in () and (), respectively; and c is shown in ().

Proof For the initial value problem () and (), we have AB = BA = C, where A, B and C are the BS-matrices of the three sequences a, b, and c. The general terms of sequences b and c are shown in () and (). Because c() = a = , the matrix C is reversible. Hence, we have CBA = E, that is, c b a = e.

Example . For the Lucas sequence l shown in Example ., l() = and l() = . We have the coecient sequences b = (, , , , , , . . .) and c = (, , , , , , . . .). Hence,

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 9 of 10

c() = , and for k ,

c(k) =

()k k+

... ... ... ... ...

kk

=

k+ .

Thus, according to equation () the Lucas sequence satises the following linear recursive relation: for k > ,

l() + l() + l() + + kl(k ) + kl(k ) kl(k) = .

This is a new identity for the Lucas numbers.

Example . For the sequence t(x) of the Chebyshev polynomials of the rst kind shown in Example ., T(x) = , T(x) = x, and we have the coecient sequences b = (, x, , , , , . . .) and c = (, x, , , , , . . .). We also see from Example . that c() = , and for k , c(k) = xk. Hence, denoting by t(x) = c b, we have t(x) = , t(x) = x, and for k > , tk(x) = ki= b(i)c(k i) = xk( x). Thus, the adjoint linear recursive equation of the second kind of the Chebyshev polynomials Tk(x) of the rst kind is that for k >

Tk(x) xTk(x) + x Tk(x) + + xk x T(x) + xk x T(x) = .

Here, we get another new identity for the Chebyshev polynomials Tk(x) of the rst kind.

4 Conclusions

In this paper, the authors develop a direct method used to solve the initial value problems of a linear non-homogeneous time-invariant dierence equation. In this method, the obtained general term of the solution sequence has an explicit formula, which includes coecients, initial values, and right-side terms of the solved equation only. Furthermore, when the solution sequence has a nonzero rst term, it satises two adjoint linear recursive equations; this usually shows several new features of the solution sequence.

Competing interests

The authors declare that they have no competing interests.

Authors contributions

The propositions and corresponding proofs shown in this paper are common contributions of the authors. On the other hand, the rst author deduces most of the examples listed in Section 2 and Section 3. All authors read and approved the nal manuscript.

Author details

1Key Discipline of Automation, School of Information and Electrical Engineering, Zhejiang University City College, Hangzhou, China. 2School of Biomedical Engineering and Instrumental Science, Zhejiang University, Hangzhou, China.

Acknowledgements

This research is partially funded by China Scholarship Council (201408330553), National Natural Science Foundation of China (61573314), Natural Science Foundation of Zhejiang Province, China (LY14F030002 LY14F030003), Hangzhou Returned Oversea Student Innovation Project, Hangzhou science and Technology Projects (20140432B08, 20142013A64), and Teacher Science Research Foundation of Zhejiang University City College (J-14023). The authors would like to thank

Pan and Pan Advances in Dierence Equations (2016) 2016:108 Page 10 of 10

Professor Jie Pan and The University of Western Australia for research facilities and the referees for their helpful comments and suggestions.

Received: 29 May 2015 Accepted: 11 April 2016

References

1. Sun, SL, Xu, YL: Introductory Combinatorics. USTC Press, Hefei (1999) (in Chinese) ISBN 7-312-01035-02. Iohvidov, IS: Hankel and Toeplitz Matrices and Forms (Article 13.9.2). Birhuser, Basel (1982)3. Chen, CT: Linear System Theory and Design, 3rd edn. Oxford University Press, New York (1999)4. Ljung, L: System Identication - Theory for the User, 2nd edn. Prentice Hall, Upper Saddle River (1999)5. Yoshifumi, O: Discrete Control Systems. Springer, London (2013)6. Oppenheim, AV, Schafer, RW, Buck, JR: Discrete-Time Signal Processing, 3rd edn. Prentice Hall, Upper Saddle River (1999)

7. Brualdi, RA: Introductory Combinatorics, 5th edn. Prentice Hall, Upper Saddle River (2009)8. Agarwal, RP: Dierence Equations and Inequalities: Theory, Methods, and Applications. CRC Press, Boca Raton (2000)9. Sloane, NJA: The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org/

Web End =http://oeis.org/ 10. Gradsbteyn, IS, Ryzbik, LM: Table of Integrals, Series, and Products, 6th edn. Elsevier, Singapore (2004)11. Bermajer, D, Gil, JB, Weiner, MD: Linear recurrence sequences and their convolutions via Bell polynomials. J. Integer Seq. 18, Article 15.1.2 (2015)

12. Mihoubi, M: Some congruences for the partial Bell polynomials. J. Integer Seq. 12, Article 09.4.1 (2009)