New approach to systems of polynomial recursions is developed based on the Carleman linearization procedure. The article is divided into two main sections: firstly, we focus on the case of uni-variable depth-one polynomial recurrences. Subsequently, the systems of depth-one polynomial recurrence relations are discussed. The corresponding transition matrix is constructed and upper triangularized. Furthermore, the powers of the transition matrix are calculated using the back substitution procedure. The explicit expression for a solution to a broad family of recurrence relations is obtained. We investigate to which recurrences the framework can be applied and construct sufficient conditions for the method to work. It is shown how introduction of auxiliary variables can be used to reduce arbitrary depth systems to the depth-one system of recurrences dealt with earlier. Finally, the limitations of the method are discussed, outlining possible directions for future research.
References
[1]
Borovkov, A.A. (2013) Probability Theory. Springer, London. https://doi.org/10.1007/978-1-4471-5201-9
[2]
Mladenović, P. (2019) Combinatorics: A Problem-Based Approach. Springer, Cham. https://doi.org/10.1007/978-3-030-00831-4
[3]
Andrica, D. and Bagdasar, O. (2020) Recurrent Sequences: Key Results, Applications, and Problems. Springer, Cham. https://doi.org/10.1007/978-3-030-51502-7
[4]
Everest, G., Poorten, A., Shparlinski, I. and Ward, T. (2003) Recurrence Sequences. American Mathematical Society, Providence. https://doi.org/10.1090/surv/104
[5]
Zhang, X., Shi, Y. and Chen, G. (2009) Constructing Chaotic Polynomial Maps. International Journal of Bifurcation and Chaos, 19, 531-543. https://doi.org/10.1142/S0218127409023172
[6]
Grosjean, N. and Huillet, T. (2016) Some Combinatorial Aspects of Discrete Non-Linear Population Dynamics. Chaos, Solitons & Fractals, 93, 71-79. https://doi.org/10.1016/j.chaos.2016.10.004
[7]
Han, D.D., Min, L.Q., Zang, H.Y. and Yang, X.P. (2019) Robust Chaos of Cubic Polynomial Discrete Maps with Application to Pseudorandom Number Generators. Mathematical Problems in Engineering, 2019, Article ID: 8250903. https://doi.org/10.1155/2019/8250903
[8]
Wang, C.F. and Ding, Q. (2019) A Class of Quadratic Polynomial Chaotic Maps and Their Fixed Points Analysis. Entropy, 21, 658-671. https://doi.org/10.3390/e21070658
[9]
Rabinovich, S., Berkolaiko, G. and Havlin, S. (1996) Solving Nonlinear Recursions. Journal of Mathematical Physics, 37, Article No. 5828. https://doi.org/10.1063/1.531702
[10]
Shang, Y. (2012) A Brief Note on an Exponential Recursive Sequence. International Journal of Open Problems in Computer Science and Mathematics, 5, 5 p. https://doi.org/10.12816/0006093
[11]
Cadilhac, M., Mazowiecki, F., Paperman, C., Pilipczuk, M. and Sénizergues, G. (2021) On Polynomial Recursive Sequences. Theory of Computing Systems. https://doi.org/10.1007/s00224-021-10046-9
[12]
Cull, P., Flahive, M. and Robson, R. (2005) Difference Equations: From Rabbits to Chaos. Springer, New York.
[13]
Hogben, L. (2014) Handbook of Linear Algebra. 2nd Edition, Chapman and Hall/CRC, New York. https://doi.org/10.1201/b16113
[14]
Berkolaiko, G., Rabinovich, S. and Havlin, S. (1998) Analysis of Carleman Representation of Analytical Recursions. Journal of Mathematical Analysis and Applications, 224, 81-90. https://doi.org/10.1006/jmaa.1998.5986
[15]
Kowalski, K. and Steeb, W.H. (1991) Nonlinear Dynamical Systems and Carleman Linearization. World Scientific, Singapore. https://doi.org/10.1142/1347
[16]
Gralewicz, P. and Kowalski, K. (2002) Continuous Time Evolution from Iterated Maps and Carleman Linearization. Chaos, Solitons & Fractals, 14, 563-572. https://doi.org/10.1016/S0960-0779(01)00222-3
[17]
Rabinovich, S., Berkolaiko, G., Buldyrev, S., Shehter, A. and Havlin, S. (1995) ‘Logistic Map’: An Analytical Solution. Physica A: Statistical Mechanics and its Applications, 218, 457-460. https://doi.org/10.1016/0378-4371(95)00163-2
[18]
Belozyorov, V.Y. and Volkova, S.A. (2016) Role of Logistic and Ricker’s Maps in Appearance of Chaos in Autonomous Quadratic Dynamical Systems. Nonlinear Dynamics, 83, 719-729. https://doi.org/10.1007/s11071-015-2360-2
[19]
Tauber, S. (1963) On Multinomial Coefficients. The American Mathematical Monthly, 70, 1058-1063. https://doi.org/10.1080/00029890.1963.11992172
[20]
Shang, Y. (2011) A Remark on the Chromatic Polynomials of Incomparability Graphs of Posets. International Journal of Pure and Applied Mathematics, 67, 159-164.
[21]
Basu, S. and Velleman, D.J. (2017) On Gauss’s First Proof of the Fundamental Theorem of Algebra. The American Mathematical Monthly, 124, 688-694. https://doi.org/10.4169/amer.math.monthly.124.8.688
[22]
Herrero, D.A. (1991) Triangular Operators. Bulletin of the London Mathematical Society, 23, 513-554. https://doi.org/10.1112/blms/23.6.513
[23]
Bronson, R. and Costa, G.B. (2020) Matrix Methods: Applied Linear Algebra and Sabermetrics. Academic Press, London.
[24]
Ford, W. (2015) Numerical Linear Algebra with Applications: Using MATLAB. Academic Press, London.
[25]
Baliarsingh, P. and Dutta, S. (2015) On an Explicit Formula for Inverse of Triangular Matrices. Journal of the Egyptian Mathematical Society, 23, 297-302. https://doi.org/10.1016/j.joems.2014.06.001
[26]
Strogatz, S.H. (2015) Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering. CRC Press, Boca Raton.
[27]
Comon, P., Golub, G., Lim, L. and Mourrain, B. (2008) Symmetric Tensors and Symmetric Tensor Rank. SIAM Journal on Matrix Analysis and Applications, 30, 1254-1279. https://doi.org/10.1137/060661569
