Recurrent numerical sequences: theory and applications

E. I. Deza ; L. V. Kotova

Čebyševskij sbornik, Tome 23 (2022) no. 3, pp. 77-101.

Résumé

The theory of recurrence relations is an important component of modern mathematical science. Many numerical sequences have a recurrent nature. Often they are naturally related to Number Theory (Fibonacci numbers, figurate numbers, Mersenne and Fermat numbers, amicable numbers, etc.) or have combinatorial “roots”(elements of the Pascal triangle, Stirling numbers, Bell numbers, Catalan numbers, etc.). The generating functions used for the study of recurrent sequences are considered in detail in Mathematical Analysis, providing a wide range of practical-oriented examples of the use of classical analytical constructions. Recursive functions play an important role in the Theory of Algorithms. Applications of the theory of recurrence relations are extremely in demand in Cryptography (generation of pseudo-random sequences over finite fields), digital signal processing (feedback modeling in a system where the output simultaneously becomes input for future time), Economy (models of various sectors of the economy - financial, commodity, etc., in which the current values of key variables (interest rate, real GDP, etc.) are analyzed in terms of past and current values of other variables), Biology (for example, models of growth dynamics of a particular population; recall Fibonacci numbers), etc. We consider several aspects of this topic, including: - history of the issue, place of recurrent numerical sequences in the development of mathematical science and mathematical education; - examples of using a recurrent approach when constructing various classes (and subclasses) of special numbers (figurate numbers, amicable numbers, etc.); - theoretical aspects of using of sequences of large periods over finite fields in radar-location and methods for generating pseudo-random sequences to provide cryptographic protection of information transmitted over long distances. In particular, the paper presents a recurrent scheme for constructing so-called centered $k$-pyramidal numbers $CS_k^3 (n) $, $ n = 1, 2, 3,\ldots $, which present configurations of points that form the $k$-gonal pyramid, at the base of which lies the centered $k$-gonal number $CS_k(n)$. Based on the definition, we get for the sequence $CS_k^3 (n) $, $ n = 1, 2, 3,\ldots $, recurrence formula $CS_k^3 (n + 1) = CS_k^3 (n) + CS_k (n + 1), CS_k^3 (1) = 1.$ Noting that $ CS _ k (n + 1) =\frac{kn^2+kn+2} {2} $, and using standard approaches, we prove that the generating function $ f (x) $ of the sequence $CS_k^3 (n) $, $ n = 1, 2, 3,\ldots $, has the form $ f (x) =\frac {x (1 + (k-2) x+x^2)} {(1-x) ^2}, | x | 1, $ while the closed formula for $CS_k^3 (n) $ has the form $ CS_k^3(n)=\frac{kn^3+n(6-k)}{6}.$

Détail

Keywords: Recurrence relation, recurrent numerical sequence, generating function of sequence, Pascal triangle, figurate numbers, amicable numbers, recurrent sequences over finite field.

Bibliographie

[1] Bukhshtab A.A., Teoriya chisel, RipolKlassik, M., 2013

[2] Grigoryan N.E., Lopatukhina T.A., “Fenomen rekurrentnosti kak sistemoobrazuyuschii pretsedentnyi priznak obrazovatelnogo diskursa”, Aktualnye issledovaniya, 2019, no. 3 (3)

[3] Deza E.I., Spetsialnye chisla naturalnogo ryada, URSS, M., 2010

[4] Deza E.I., Deza M.M., Figurate numbers, World Scientific Publishing Company, 2012 | MR | Zbl

[5] Deza E.I., Deza M.M., Figurnye chisla, MTsNMO, M., 2016

[6] Deza E.I., Mersenne and Fermat Numbers, World Scientific Publishing Company, 2021

[7] Deza E.I., Kotova L.V., Vvedenie v kriptografiyu, URSS, M., 2018

[8] Deza E.I., Model D.L., Osnovy diskretnoi matematiki, URSS, M., 2010

[9] Nechaev V.I., Osnovy zaschity informatsii, MGU, M., 1999

[10] Sloane N.J.A., Plouffe S., The Encyclopedia of Integer Sequences, Academic Press, San Diego, 1995 | MR | Zbl

[11] Yan S.Y. Perfect, Amicable and Sociable Numbers. A Computational Approach, World Scientific, 1996 | MR | Zbl