Уральский государственный университет путей сообщения (Екатеринбург) В работе рассматриваются соотношения, задающие нелинейные рекурсии первого порядка для общего линейного рекуррентного соотношения второго порядка с постоянными коэффициентами. Получены условия существования таких соотношений. Приведены примеры. Ключевые слова: линейное рекуррентное соотношение; нелинейное рекуррентное соотношение; числа Фибоначчи; уравнения в конечных разностях.
В работе [1] поставлена общая задача понижения порядка линейных рекуррентных уравнений с постоянными коэффициентами, решение которой показано на примере чисел Фибоначчи. В [2] рассматривались также некоторые случаи понижения порядка конечно-разностных уравнений и наличия зависимостей, связанных с остатком номера члена рекуррентной последовательности по некоторому модулю. В общем виде эта задача ставится [2, 3] для однородного уравнения N -ого порядка относительно неизвестной последовательности fn с известными постоянными коэффициентами a0; : : : ; aN¡1 как задача нахождения такой зависимости F , возможно нелинейной, что для любого решения f существует такая постоянная C = Const, что выполняется тождество
F (fn; : : : ; fn+N¡1) = C:
(
v = C2¸2n:
Подставляя (
k m¡k Ckj¸j1¸2k ¡ jul+jvk¡j+m¡k¡l = akfnk+1fnm¡k = ak P ¢ P Clm¡kulvm¡k¡l = ak P P
j=0 l=0 j=0 l=0
= ak X usvm¡s X CkjCms¡¡jk¸j1¸2k¡j = ak X usvm¡s Xk µ k ¶ µ m ¡ k ¶ ¸1j¸2k¡j;
m k m
s=0 j=0 s=0 j=0 j s ¡ j
следовательно, (
X usvm¡s X ak Xk µ k ¶ µ m ¡ k ¶ ¸j1¸2k¡j = C = Const:
m m
s=0 k=0 j=0 j s ¡ j
Итак, в случае полиномиального соотношения (
As = X ak Xk µ k ¶ µ m ¡ k ¶ ¸j1¸2k¡j: m k=0 j=0 j s ¡ j µ p ¶ q
= 0 при q < 0 или q < p). (считаем биномиальные коэффициенты При n = 0; 1; 2; : : : имеем
m m F (fn; : : : ; fn+1) = X(C1¸1n)s(C2¸2n)m¡sAs = X(C1sC2m¡sAs)¸1ns¸n(m¡s) = C = Const 2 s=0 s=0 Если C1 = C2 = 0, то C = 0 и равенство (9) справедливо для любого n.
Если C1 6= 0 = C2, то C = 0 и равенство (9) сводится к равенству C1mAm¸1mn = C = Const, из которого следует, что либо Am = 0 (и тогда C = 0), либо Am 6= 0 и (¸1m)n = 1, т.е. ¸1m = 1.
Аналогично – если C1 = 0 6= C2: при Am 6= 0 имеем (¸2m)n = 1, т.е. ¸2m = 1.
Если же C1 6= 0 6= C2, то из (6) вытекает соотношение
F (fn+1; fn+2) ¡ F (fn; fn+1) = 0;
и если As = 0 не для всех s 2 0; 1; : : : ; m, то, рассматривая эти последовательные
соотношения как однородную систему линейных алгебраических уравнений относительно неизвестных
(C1sC2m¡sAs), приходим к равенству нулю определителя матрицы этой системы, т.е. матрицы с
элементами ¸(1n+1)s¸(2n+1)(m¡s) ¡ ¸1ns¸2n(m¡s) = (¸s1¸2m¡s ¡ 1)¸1ns¸2n(m¡s) для последовательных значений n,
составленных из столбцов для значений s, соответствующих неравенствам As 6= 0:
где l – количество таких s, что As 6= 0.
Таким образом,
¯¯ ¸1ns1¸2n(m¡s1) : : : ¸1nsl¸2n(m¡sl) ¯¯
0 = ¯¯¯ ¸(1n+1)s1¸(n+1)(m¡s1) : : : ¸(n+1)sl¸(n+1)(m¡sl) ¯¯
¯¯ :2: : : : : 1 :2: : ¯¯ =
¯¯ ¸(1n+l)s1¸(n+l)(m¡s1) : : : ¸(n+l)sl¸(n+l)(m¡sl) ¯¯
2 1 2 ¯
(
¯¯ ¸l1s1 ¸l2(m¡s1) : : : ¸l1sl ¸l2(m¡sl) ¯¯ = (¸s11+:::+sl ¸l2m¡(s1+:::+sl))n ¯¯¯¯ :u:1: ¯¯ 1 ¯¯ u1l 1 : : : 1 ¯¯ :u:2: :: :: :: :u:l: ¯¯¯¯ ; u2l : : : ull ¯¯ уравнения степени N с постоянными коэффициентами? Пусть ai = Di¸in, тогда
N¡1 X fnN+¡1jfnj = C j=0 fn = a1 + : : : + aN ; fn+1 = ¸1a1 + : : : + ¸N aN ; где ui = ¸s1i ¸(2m¡si)(i = 1; : : : ; l), так что этот определитель, как определитель Вандермонда, равен нулю только если ui = uj для некоторой пары i 6= j(i; j = 1; : : : ; l), что равносильно наличию соотношения ¸si¡sj ¸(2m¡si)¡(m¡sj) = (¸1¡1¸2)sj¡si = 1;
1 т.е. отношение корней есть корень из единицы. Так в работе [2] на с. 215 дана ссылка на работу по определителям типа Вандермонда.
Наконец, если l = 0, т.е. все As = 0(s 2 0; 1; : : : ; m), то C = 0 при любых C1; C2. Значит, соотношение при fn 6= 0 принимает вид
1 fnm = am µ fn+1 ¶ m + am¡1 µ fn+1 ¶ m¡1 + am¡2 µ fn+1 ¶ m¡2 + : : : + a1 µ fn+1 ¶ 1 + a0 = 0; (13) fn fn fn fn из которого следует, что отношение ³ fnfn+1 ´ при любых C1; C2 (кроме возможности fn < 0) и любых n принимает не более m значений – корней уравнения (13). Ясно, что среди этих значений могут быть ¸1 и ¸2 (для этого достаточно взять C1 = 0 или C2 = 0). Это дает следствие уравнений A0 = 0 и Am = 0. Если же C1 6= 0 6= C2, то fn+1 = C1¸1n+1 [1 + fn ³ C2 ´ ³ ¸2 ´ n+1]
C1 ¸1 C1¸1n ¢ [1 + ³ CC12 ´ ³ ¸¸21 ´ n]
1 + D¹n+1 = ¸1 ¢ 1 + D¹n (где D = CC21 ; ¹ = ¸¸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 2 Z). Для произвольного N задача поиска соотношения первого порядка ставится аналогично: существует ли
N N связь fn = P Di¸in с fn+1 = P Di¸in+1 (Di = Const; ¸i все различные, i = 1; : : : ; N ), в виде i=1 i=1 (11) (12) (14) (15) (16) (17) fns = X s1! : s:!: sN ! as11 : : : asNN ; f sn+1 = s1+X:::+sN s1! : s:!: sN ! (¸1a1)s1 : : : (¸N aN )sN = X s1! : : :ss!N ! = s ¸s11 : : : ¸sNN as11 : : : asNN : При этом ее определитель равен ¢ = j j = ¸21(¸1 + ¸2) + 2¸1¸22 + 2¸1¸22 ¡ ¸22(¸1 + ¸2) ¡ 2¸21¸2 ¡ 2¸21¸2 =
A = (¸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 при ¸1 6= ¸2. Вычисляем определители:
¯¯ fn2+1 2¸1¸2 ¸21 ¯¯ ¢a2 = ¯¯ fnfn+1 (¸1 + ¸2) ¸2 ¯¯ = fn2+1 ¢ (¸1 ¡ ¸2) ¡ fnfn+1 ¢ 2(¸1 ¡ ¸2)¸2 + fn2 ¢ (¸1 ¡ ¸2)¸22; 1 ¯¯ fn2 2 1 ¯¯
¯¯ ¸21 fn2+1 ¢a1a2 = ¯¯ ¸1 fnfn+1 ¯¯ 1 fn2 Следовательно, по правилу Крамера, >>8 a21 = ¢ 1 > ¢a21 = (¸1¡¸2)2 [1 ¢ fn2+1 ¡ 2¸2fnfn+1 + ¸22fn2]; < a1a2 = ¢a1a2 = (¸1¡¸2)2 [(¡1) ¢ f 2n+1 ¡ (¸1 + ¸2)fnfn+1 + (¡1)¸1¸2fn2];
1 ¢ > 1 >>: a22 = ¢¢a22 = (¸1¡¸2)2 [1 ¢ fn2+1 ¡ 2¸1fnfn+1 + ¸21fn2]: Поэтому:
I. Если ¸21 = 1, т.е. ¸1 2 {+1, -1}, то a12 = (D1¸1n)2 = D12(¸21)n = D121n = D12 = Const – не зависит от n; значит, для любой последовательности f0; f1; f2; f3; : : : ; являющейся решением линейного рекуррентного (конечно-разностного) уравнения второго порядка fn+2 ¡ ¾1fn+1 + ¾2fn = 0 (где
1 т.е., т.к. ¸2 = ¡ 2 , Отсюда fn+2 ¡ 21 fn+1 ¡ 21 fn. ¸2 ¡ 12 ¸ ¡ 12 = 0. ¸1;2 = 14 § q 116 + 12 = 14 § q 196 = 14 § 43 . ¸1 = 14 + 34 = 1; ¸2 = 14 ¡ 43 = ¡ 2 .
1 Результаты расчетов представим в таблице 1. Все значения fn имеют знак +, т.к. fn > 0. Получим линейное неоднородное уравнение первого порядка что завершает рассмотрение примера.
fn+1 + fn+1fn + 41 (fn2 ¡ 25) = 0;
2 fn+1 = ¡ 2 fn § r 14 fn2 ¡ 41 fn2 + 1 24 1 5 4 = ¡ 2 fn § 2 : n 0 1 2 3 4 Список литературы [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.
On the problem of reducing the order of linear recurrence equations with constant coefficients
Ural State University of Railway Transport (Yekaterinburg, Russia)
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.