О задаче понижения порядка линейных рекуррентных уравнений с постоянными коэффициентами К.Л. Геут С.С. Титов geutkrl@yandex.ru stitov@usaaa.ru Уральский государственный университет путей сообщения (Екатеринбург) Аннотация В работе рассматриваются соотношения, задающие нелинейные ре- курсии первого порядка для общего линейного рекуррентного соот- ношения второго порядка с постоянными коэффициентами. Полу- чены условия существования таких соотношений. Приведены при- меры. Ключевые слова: линейное рекуррентное соотношение; нелиней- ное рекуррентное соотношение; числа Фибоначчи; уравнения в ко- нечных разностях. В работе [1] поставлена общая задача понижения порядка линейных рекуррентных уравнений с посто- янными коэффициентами, решение которой показано на примере чисел Фибоначчи. В [2] рассматривались также некоторые случаи понижения порядка конечно-разностных уравнений и наличия зависимостей, свя- занных с остатком номера члена рекуррентной последовательности по некоторому модулю. В общем виде эта задача ставится [2, 3] для однородного уравнения N -ого порядка fn+N + aN −1 fn+N −1 + . . . + a0 fn = 0. (1) относительно неизвестной последовательности fn с известными постоянными коэффициентами a0 , . . . , aN −1 как задача нахождения такой зависимости F , возможно нелинейной, что для любого решения f существует такая постоянная C = Const, что выполняется тождество F (fn , . . . , fn+N −1 ) = C. (2) для любого целого неотрицательного n [2, 3]. Эта задача аналогична проблеме поиска промежуточного интеграла для дифференциального уравнения второго порядка [4]. Пусть F (fn , . . . , fn+N −1 ) = am fn+1 m + am−1 fn+1 m−1 fn 1 + am−2 fn+1 m−2 fn 2 + . . . + a1 fn+1 1 fnm−1 + a0 fnm = C. (3) При N = 2 при помощи корней λ1 6= λ2 характеристического уравнения (1) находим последовательно ½ fn = C1 λn1 + C2 λn2 = u + v, (4) fn+1 = C1 λn+1 1 + C2 λn+1 2 = λ1 u + λ2 v, c by the paper’s authors. Copying permitted for private and academic purposes. Copyright ° In: G.A. Timofeeva, A.V. Martynenko (eds.): Proceedings of 3rd Russian Conference "Mathematical Modeling and Information Technologies" (MMIT 2016), Yekaterinburg, Russia, 16-Nov-2016, published at http://ceur-ws.org 142 где C1 , C2 = Const и введены обозначения ½ u = C1 λn1 , (5) v = C2 λn2 . Подставляя (4), (5) в (3) вычислим k P k P l m−k P P j j k k m−k ak fn+1 fnm−k = ak · C m−k ul v m−k−l = ak Ck λ1 λ2 − jul+j v k−j+m−k−l = j=0 l=0 j=0 l=0 m X k X m X k µ X ¶µ ¶ k m−k = ak us v m−s Ckj Cm−k s−j j k−j λ1 λ2 = a k us v m−s λ1 j λ2 k−j ; (6) j s−j s=0 j=0 s=0 j=0 следовательно, (2) получаем в виде m X m X k µ X ¶µ ¶ k m−k s m−s u v ak λj1 λk−j 2 = C = Const. (7) j s−j s=0 k=0 j=0 Итак, в случае полиномиального соотношения (2), (3) при degF = m в однородном случае находим P m F (fn , fn+1 ) = us v m−s As , где постоянные коэффициенты A равны s=0 m X k µ X ¶µ ¶ k m−k As = ak λj1 λk−j 2 . (8) j s−j k=0 j=0 µ ¶ p (считаем биномиальные коэффициенты = 0 при q < 0 или q < p). q При n = 0, 1, 2, . . . имеем m X m X n(m−s) F (fn , . . . , fn+1 ) = (C1 λn1 )s (C2 λn2 )m−s As = (C1s C2m−s As )λns 1 λ2 = C = Const (9) s=0 s=0 Если C1 = C2 = 0, то C = 0 и равенство (9) справедливо для любого n. Если C1 6= 0 = C2 , то C = 0 и равенство (9) сводится к равенству C1m Am λmn 1 = C = Const, из которого следует, что либо Am = 0 (и тогда C = 0), либо Am 6= 0 и (λm n m 1 ) = 1, т.е. λ1 = 1. Аналогично – если C1 = 0 6= C2 : при Am 6= 0 имеем (λm n m 2 ) = 1, т.е. λ2 = 1. Если же C1 6= 0 6= C2 , то из (6) вытекает соотношение F (fn+1 , fn+2 ) − F (fn , fn+1 ) = 0, и если As = 0 не для всех s ∈ 0, 1, . . . , m, то, рассматривая эти последовательные соот- ношения как однородную систему линейных алгебраических уравнений относительно неизвестных (C1 s C2 m−s As ), приходим к равенству нулю определителя матрицы этой системы, т.е. матрицы с элемен- (n+1)s (n+1)(m−s) n(m−s) n(m−s) тами λ1 λ2 − λns 1 λ2 = (λs1 λm−s 2 − 1)λns 1 λ2 для последовательных значений n, составленных из столбцов для значений s, соответствующих неравенствам As 6= 0:  n(m−s)  λns 1 λ2  (n+1)s (n+1)(m−s)   λ λ2  C1s C2m−s As (λs1 λm−s 2 − 1)  1  (10)  ...  (n+l)s (n+l)(m−s) λ1 λ2 где l – количество таких s, что As 6= 0. Таким образом, ¯ ¯ ¯ λns1 n(m−s1 ) λns l n(m−sl ) ¯ ¯ 1 λ2 ... 1 λ2 ¯ ¯ (n+1)s1 (n+1)(m−s1 ) (n+1)sl (n+1)(m−sl ) ¯ ¯ λ λ2 . . . λ1 λ2 ¯ 0=¯ 1 ¯= ¯ ... ... ... ¯ ¯ (n+l)s1 (n+l)(m−s1 ) (n+l)sl (n+l)(m−sl ) ¯¯ ¯ λ λ2 . . . λ1 λ2 1 143 ¯ ¯ ¯ 1 ... 1 ¯ ¯ s1 (m−s1 ) sl (m−sl ) ¯ ¯ n(m−s1 ) ¯ λ λ . . . λ 1 λ2 l n(m−sl ) ¯ ¯= = (λns 1 1 · λ2 · . . . · λns 1 λ2 )¯ 1 2 ¯ ¯ ... ... ... ¯ ¯ λls1 λl(m−s1 ) lsl l(m−sl ) ¯ . . . λ 1 λ2 1 2 ¯ ¯ ¯ 1 1 . . . 1 ¯¯ ¯ lm−(s1 +...+sl ) n ¯¯ u1 u2 . . . ul ¯¯ = (λs11 +...+sl λ2 ) ¯ , (11) ¯ . . .l ... . . . . . . ¯¯ ¯ u1 u2 l . . . ul l ¯ (m−s ) где ui = λs1i λ2 i (i = 1, . . . , l), так что этот определитель, как определитель Вандермонда, равен нулю только если ui = uj для некоторой пары i 6= j(i, j = 1, . . . , l), что равносильно наличию соотношения s −sj (m−si )−(m−sj ) λ1i λ2 = (λ−1 1 λ2 ) sj −si = 1, (12) т.е. отношение корней есть корень из единицы. Так в работе [2] на с. 215 дана ссылка на работу по определителям типа Вандермонда. Наконец, если l = 0, т.е. все As = 0(s ∈ 0, 1, . . . , m), то C = 0 при любых C1 , C2 . Значит, соотношение при fn 6= 0 принимает вид µ ¶ µ ¶ µ ¶ µ ¶ 1 fn+1 m fn+1 m−1 fn+1 m−2 fn+1 1 = am + am−1 + am−2 + . . . + a1 + a0 = 0, (13) fn m fn fn fn fn ³ ´ из которого следует, что отношение fn+1 fn при любых C1 , C2 (кроме возможности fn < 0) и любых n принимает не более m значений – корней уравнения (13). Ясно, что среди этих значений могут быть λ1 и λ2 (для этого достаточно взять C1 = 0 или C2 = 0). Это дает следствие уравнений A0 = 0 и Am = 0. Если же C1 6= 0 6= C2 , то ³ ´ ³ ´ C2 λ2 n+1 fn+1 C1 λ1n+1 [1 + C1 λ1 ] 1 + Dµn+1 = · ³ ´ ³ ´ = λ 1 · (14) fn C1 λn1 [1 + C2 λ2 n] 1 + Dµn C1 λ1 C2 (где D = C 1 , µ = λλ21 ). Записывая равенство нулю всех As = 0 (s = 0, 1, . . . , m) как систему линейных однородных уравне- ний относительно a0 , a1 , . . . , am вычислим определитель этой системы. Оказывается, он есть многочлен от µ = λ2 λ1 , равный степени многочлена (µ − 1), умноженный на некоторую степень λ1 . Следовательно, он может быть (при λ1 6= 0) равным нулю только при µ = 1, т.е. при λ1 = λ2 . Получаем итоговое Утверждение 1. Если λ1 6= λ2 , то линейное рекуррентное соотношение второго порядка с постоянными коэффициентами допускает нетривиальное однородное соотношение (СС) первого порядка тогда и только тогда, когда некоторое произведение целых степеней корней равно единице: λr1 λt2 = 1, (r, t ∈ Z). Для произвольного N задача поиска соотношения первого порядка ставится аналогично: существует ли P N P N связь fn = Di λni с fn+1 = Di λn+1 i (Di = Const, λi все различные, i = 1, . . . , N ), в виде i=1 i=1 N X −1 N −j j fn+1 fn = C (15) j=0 уравнения степени N с постоянными коэффициентами? Пусть ai = Di λni , тогда fn = a1 + . . . + aN , (16) fn+1 = λ1 a1 + . . . + λN aN , (17) 144 X s! fns = as1 . . . asNN , (18) s 1 ! . . . sN ! 1 X s! X s! f s n+1 = (λ1 a1 )s1 . . . (λN aN )sN = λs1 . . . λsNN as11 . . . asNN . (19) s1 +...+sN s 1 ! . . . sN ! s1 ! . . . s N ! = s 1 Поэтому выражение для fn+1 s fn t записывается в виде явной, но громоздкой формулы. Пример 1 N = 2, fn = D1 λn1 + D2 λn2 = a1 + a2 , fn+1 = D1 λn+1 1 + D2 λn+1 2 = λ1 a1 + λ2 a2 . fn+1 = λ1 a1 + 2λ1 λ1 a1 a2 λ22 a22 fn fn+1 = λ1 a21 + (λ1 + λ2 )a1 a2 + λ2 a22 fn2 = a21 + 2a1 a2 + a22 . 2 2 2 Поэтому     a21 2 fn+1 A ·  a2 a1  =  fn fn+1  (20) a22 fn2 , где матрица A имеет вид   λ21 2λ1 λ2 λ21  λ1 (λ1 + λ2 ) λ2  = A(λ1 , λ2 ). (21) 1 2 1 При этом ее определитель равен ∆ = |A| = λ21 (λ1 + λ2 ) + 2λ1 λ22 + 2λ1 λ22 − λ22 (λ1 + λ2 ) − 2λ21 λ2 − 2λ21 λ2 = = (λ21 − λ22 )(λ1 + λ2 ) + 4(λ1 λ22 − λ21 λ2 ) = (λ1 − λ2 )(λ1 + λ2 )2 − 4λ1 λ2 (λ1 − λ2 ) = (λ1 − λ2 )[(λ1 + λ2 )2 − 4λ1 λ2 ] = = (λ1 − λ2 )[λ21 − 2λ1 λ2 + λ22 ] = (λ1 − λ2 )3 6= 0 (22) при λ1 6= λ2 . Вычисляем определители: ¯ ¯ ¯ fn+1 2 2λ1 λ2 λ21 ¯¯ ¯ ¯ ∆a21 = ¯ fn fn+1 (λ1 + λ2 ) λ2 ¯¯ = fn+1 2 · (λ1 − λ2 ) − fn fn+1 · 2(λ1 − λ2 )λ2 + fn2 · (λ1 − λ2 )λ22 ; (23) ¯ fn2 2 1 ¯ ¯ 2 ¯ ¯ λ1 2 fn+1 λ21 ¯¯ ¯ ∆a1 a2 = ¯¯ λ1 fn fn+1 λ2 ¯¯ = −fn+1 2 · (λ1 − λ2 ) + fn fn+1 (λ1 − λ2 )(λ1 + λ2 ) − fn2 · (λ1 − λ2 )λ1 λ2 ; (24) ¯ 1 fn2 1 ¯ ¯ 2 ¯ ¯ λ1 2λ1 λ2 2 fn+1 ¯ ¯ ¯ ∆a22 = ¯¯ λ1 (λ1 + λ2 ) fn fn+1 ¯¯ = fn+1 2 · (λ1 − λ2 ) − fn fn+1 · 2λ1 (λ1 − λ2 ) + fn2 · λ21 (λ1 − λ2 ). (25) ¯ 1 2 fn2 ¯ Следовательно, по правилу Крамера,  ∆ 2   a21 = a1 = 1 2 2 2   ∆ (λ1 −λ2 )2 [1 · fn+1 − 2λ2 fn fn+1 + λ2 fn ], ∆ 1 2 2 a1 a2 = a∆1 a2 = (λ1 −λ 2) 2 [(−1) · f n+1 − (λ1 + λ2 )fn fn+1 + (−1)λ1 λ2 fn ], (26)    ∆  a2 = a22 = 1 2 2 ∆ 2 [1 · f (λ1 −λ2 ) − 2λ1 fn fn+1 + λ2 f 2 ]. n+1 1 n Поэтому: I. Если λ21 = 1, т.е. λ1 ∈ {+1, -1}, то a1 2 = (D1 λn1 )2 = D12 (λ21 )n = D12 1n = D12 = Const – не зависит от n; значит, для любой последовательности f0 , f1 , f2 , f3 , . . . , являющейся решением линей- ного рекуррентного (конечно-разностного) уравнения второго порядка fn+2 − σ1 fn+1 + σ2 fn = 0 (где 145 σ1 = λ1 + λ2 , σ2 = λ1 · λ2 ), найдется такая постоянная Const, что f удовлетворяет квадратичному 2 уравнению первого порядка fn+1 − 2λ2 fn fn+1 + λ22 fn2 = C (C = (λ2 − λ1 )2 D12 ). II. Если λ1 λ2 = 1, то a1 a2 = D1 D2 λ2n = D1 D2 = Const - не зависит от n, значит, для любой после- довательности fn , являющейся решением fn+2 − σ1 fn+1 + fn = 0 (здесь σ1 = λ1 + λ2 , σ2 = λ1 λ2 = 1), найдется такая постоянная C = Const, что f удовлетворяет квадратному уравнению первого порядка f 2 n+1 − (λ1 + λ2 )fn fn+1 + fn 2 = C f 2 n+1 − σ1 fn fn+1 + fn 2 = (λ1 − λ2 )2 D1 D2 . III. Случай λ22 = 1 симметричен первому случаю. Пример 2 Пример Маркова для λ = 1 ("артиллерийская вилка"), т.е. когда последующее значение есть среднее арифметическое значение двух предыдущих [3, 2]. При k = 2 получаем: fn+2 = fn +f2 n+1 . Отсюда fn+2 − 12 fn+1 − 12 fn . λ2 − 12 λ − 12 = 0. q q λ1,2 = 14 ± 16 1 + 12 = 14 ± 169 = 14 ± 34 . λ1 = 14 + 34 = 1; λ2 = 14 − 34 = − 12 . C2 fn = C1 λn1 + C2 λn2 = C1 + . (27) 2n Тогда решение в общем виде 1 { f 0 = C1 + C2 , f 1 = C1 − C2 . (28) 2 3 1 { f 0 − f1 = C2 , f1 = C1 − (f0 − f1 ). (29) 2 3 2 f0 + 2f1 {C2 = (f0 − f1 ), C1 = . (30) 3 3 Из λ = 1 имеем квадратическую зависимость 2 fn+1 − 2λ2 fn+1 fn + λ22 fn2 = 0, (31) т.е., т.к. λ2 = − 21 , 2 1 fn+1 + fn+1 fn + fn2 = Const. (32) 4 Взяв f (0) = 1, f (1) = 2 [3], найдем при n = 0 : 22 + 2 + 14 = 4 + 2 + 14 = 25 4 , и поэтому 2 1 25 fn+1 + fn+1 fn + fn2 = , (33) 4 4 т.е. fn+1 находится через fn как решение квадратного уравнения 2 1 fn+1 + fn+1 fn + (fn2 − 25) = 0, (34) 4 r 1 1 2 1 2 24 1 5 fn+1 = − fn ± f − f + = − fn ± . (35) 2 4 n 4 n 4 2 2 Результаты расчетов представим в таблице 1. Все значения fn имеют знак +, т.к. fn > 0. Получим линейное неоднородное уравнение первого порядка 1 5 fn+1 = − fn + , (36) 2 2 что завершает рассмотрение примера. 146 Таблица 1: Зависимость fn от n n fn 0 1 1 2 = - 12 + 25 3 5 2 2 = -1 + 2 7 3 5 3 4 = -4 + 2 13 7 5 4 8 = -8 + 3 В общем случае вид F (fn , . . . , fn+N ) может зависеть от четности n или, более общо, от остатка деления на некоторое число. В работах [5, 6] рассмотрены некоторые случаи уравнений второго порядка. В данной работе получены некоторые условия построения такой зависимости для уравнений высших порядков как аналога нахождения промежуточного интеграла [4]. Ясно, что такие условия должны формулироваться в терминах свойств корней характеристического уравнения, которые мы на данном этапе считаем различными. Тривиальный случай наличия нулевого корня не рассматривается. Например, очевидно, из предыдущего вытекает Утверждение 2. Зависимость F будет линейной с постоянными коэффициентами тогда и только тогда, когда один из корней характеристического уравнения равен единице. Получено общее Утверждение 3. Пусть произведение N чисел, каждое из которых является корнем характеристиче- ского уравнения, равно единице. Тогда существует искомая зависимость в виде однородного многочлена F степени N . Рекуррентное соотношение можно рассматривать не только над числовыми, но и над конечными полями. На с. 249 [2] Марков в конце главы VI пишет: одно из применений выводов этого параграфа можно найти в моей статье "Распространение предельных теорем исчисления вероятностей на сумму величин, связанных в цепь"(Зап. Акад. Наук, VII серия, том XX). Одним из практических примеров использования рекуррентных последовательностей являются гене- раторы псевдослучайных чисел, которые нашли широкое применение в различных областях, например, криптографии. Помимо генераторов линейной последовательности используются генераторы на регистрах сдвига с нелинейной функцией обратной связи. Эти генераторы порождают нелинейные рекуррентные по- следовательности, которые по своим диагностическим свойствам отличаются от линейных. В частности, в n-разрядном нелинейном генераторе достаточно просто порождается двоичная последовательность де Брейна. Она представляет собой нелинейную двоичную последовательность xi периода T = 2n , в которой всевозможные векторы (xj , xj+1 , . . . xj+n−1 ) длины n при любом j встречается только один раз. Исклю- чение запрещенного нулевого состояния всех триггеров генератора позволяет увеличить период формиру- емой последовательности и сделать его максимально возможным, равным 2m , повысить ее качество, так как вероятности появления 0 и 1 становятся равными 0,5. Последовательности длиной 2m называются последовательностями де Брейна. Последовательность де Брёйна — последовательность a1 , . . . , at , элементы которой принадлежат задан- ному конечному множеству, обычно рассматривают множество 0, 1, . . . , k − 1 и все подпоследовательности ai+1 , . . . , ai+n заданной длины n различны. При k = 2 существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка n: так, при n = 3 соотношение xn = xn−2 + xn−3 (mod2) порождает последовательности с периодом 7, например, 0010111001011100. . . (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32(EDB88320). Так на с. 250 [2] Марков в начале главы VII "Связь линейных уравнений в конечных разностях вто- рого порядка с непрерывными дробями"пишет: в настоящее время область исследований о которых мы предполагаем сказать несколько слов, принадлежит к числу заброшенных, что отчасти можно объяснить трудностью получить в ней новые результаты. Итак, получены условия возможности понижения порядка линейного разностного уравнения, для урав- нения второго порядка являющиеся необходимыми и достаточными. 147 Список литературы [1] V. N. Ushakov. Egyptian triangles and the Fibonacci numbers. Empire of mathematics, 11:21–60, 2001. (in Russian) = В. Н. Ушаков. Египетские треугольники и числа Фибоначчи. Империя математики, 11:21–60, 2001. [2] A. A. Markov. Calculus of finite differences. Odessa, Printing House Of Joint South-Russian Society Of Printing, 1910. (in Russian) = А. А. Марков. Исчисление конечных разностей. Одесса, Типография Акционерного Южно-Русского Общества Печатного Дела, 1910. [3] A. O. Gelfond Calculus of finite differences. Moscow, Nauka, 1967. (in Russian) = А. О. Гельфонд. Исчисление конечных разностей. Москва, Наука, 1967. [4] A. F. Sidorov, V. P. Shapeev, N. N. Yanenko The method of differential relations and its applications in gas dynamics. Novosibirsk, Nauka. Sib. otd-nie, 1984. (in Russian) = А. Ф. Сидоров, В. П.Шапеев, Н. Н. Яненко. Метод дифференциальных связей и его приложения в газовой динамике. Новоси- бирск: Наука. Сиб. отд-ние, 1984. [5] K. L. Geut, S. S. Titov On the problem of constructing a nonlinear recurrent sequences. IV interdisciplinary young scientists ’ conference, Ural branch of RAS Information school of young scientists / collection of scientific works of the Central scientific library UB RAS., Ekaterinburg, 203–208. 2013. (in Russian) = К. Л. Геут, С. С. Титов. О задаче построения нелинейных рекуррентных последователь- ностей. IV междисциплинарная молодежная научная конференция УрО РАН Информационная школа молодого ученого / сб. научных трудов ЦНБ УрО РАН. Екатеринбург, 203–208, 2013. [6] K. L. Geut, S. S. Titov On the construction of nonlinear recurrence relations. Problems of theoretical and applied mathematics and its applications / Proceedings of the 46th national youth conference., Ekaterinburg, UB RAS, 3–6. 2015. (in Russian) = К. Л. Геут, С. С. Титов. О построении нели- нейных рекуррентных соотношений. Проблемы теоретической и прикладной математики и ее приложений / Труды 46-й Всероссийской молодежной конференции., Екатеринбург, УрО РАН, 3–6, 2015. 148 On the problem of reducing the order of linear recurrence equations with constant coefficients Kristina L. Geut Ural State University of Railway Transport (Yekaterinburg, Russia) Sergei S. Titov Ural State University of Railway Transport (Yekaterinburg, Russia) Abstract. The paper deals with the relations that define non-linear recursion of the first order for a general linear recurrence relation of the second order with constant coefficients. The conditions of the existence of such relations are found. Examples are given. Keywords: linear recurrence relation, nonlinear recurrence relation; Fibonacci numbers, difference equations. 149