ПРОГРАММИРОВАНИЕ, 2011, No 4, с. 3-8
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ОПРЕДЕЛЕННОЕ СУММИРОВАНИЕ ГИПЕРГЕОМЕТРИЧЕСКИХ ТЕРМОВ СПЕЦИАЛЬНОГО ВИДА
© 2011 г. А. А. Рябенко Вычислительный центр им. А. А. Дородницына РАН 119333 Москва, ул. Вавилова, 40
E-mail: ryabenko@cs.msu.ru Поступила в редакцию 12.10.2010 г.
Рассматривается определенное суммирование гипергеометрических термов двух переменных. В настоящее время в системах компьютерной алгебры для суммирования таких термов используется сочетание алгоритма Цейлбергера и дискретного аналога формулы Ньютона-Лейбница, что, как известно, не всегда дает правильный результат. Мы предлагаем несложное предварительное исследование терма перед использованием алгоритма Цейлбергера. Если гипергеометрический терм относится к описываемому нами виду, то использование алгоритма Цейлбергера будет корректным, или, даже, в его использовании не будет необходимости.
1. ВВЕДЕНИЕ
Пусть K - поле характеристики 0, и пусть дана двумерная последовательность (гипергеометрический терм) T(n,k), которая для всех n,k £ Z удовлетворяет системе (H-системе данного терма)
pi(n, k) T(n + 1, k) = qi(n, k) T(n, k), ( ) P2(n, k) T(n, k + 1) = q2(n, k) T(n, k), (.)
где pi(n,k),qi(n,k) — взаимно простые полиномы над K для i = 1, 2.
Система Maple предоставляет пакет SumTools[Hypergeometric] (см. [1]) для работы с суммами гипергеометрических термов. Например, SumTools[Hypergeometric][DefiniteSum] вычисляет в замкнутом виде, когда это возможно, определенную конечную сумму
U2U+V2
S (n)= ^ T (n,k) для n = 0,1, 2,...,
fc=Ul«,+Vl
где u1 ,v1,u2,v2 £ Z и u1 < u2. Коротко перечислим основные действия этой процедуры:
1. Для данного T(n,k), если это возможно, строится с помощью алгоритма Цейлбергера (см. [2]) так называемая Z-пара (L,G), где
• Ь — разностный оператор
Ь = аг (п)Ег +-----+ а1(п)Е + а0(п)
с полиномиальными над К коэффициентами, Е — оператор сдвига:
Еу(п) = у(п + 1),
• С(п, к) = Е(п,к)Т(п,к), где Е(п,к) — рациональная от п, к функция,
такие, что
ЬТ(п,к)= С(п, к + 1) - С(п,к). (1.2)
2. Если Z-пара построена, строится рекуррентное соотношение для Б (п)
ЬБ(п) = С(п,и2п + у2 + 1) - (1.3) -С(п, и1п + У\) + Е(п),
где
Е(п) = ЕГ=1 аг(п) (
ЕП-1 Т(п + г, к + и2п + у2 + 1)- Еи=0-1 Т(п + г, к + щп + VI + 1)) .
3. С помощью алгоритма из [3] находятся гипергеометрические решения (1.3).
4. Если такие решения существуют, осуществляется проверка, представима ли сумма 5(п) в замкнутом виде.
n+1
Пример 1. Для
kf n + k\ /2k
T(n-k> = M>\n - kAk
алгоритм Цейлбергера вычисляет Z-пару
L = E + 1, G =
2k2
(-n + k - 1)(n + 1)
T (n, k).
E
k=0
(-W n+Й (2kki = (-1)n
В Maple мы получаем этот результат
> T := (-1)~k*binomial(n+k, n-k)*
> binomial(2*k, k):
> Sum(T,k=0..n) =
> SumTools:-Hypergeometric:-
> DefiniteSum(T,n,k,0..n);
(-1)
k=0
n + k\ /2 k
nk
k
= (-1)n
У^ (-1)k binomial(n + k, n - k) binomial(2 k, k)
k=0
□
Для 5 (п) = ^П=о Т(п, к) получается однородное рекуррентное соотношение
5 (п) + 5 (п + 1) = 0,
которое имеет решение 5(0)(-1)п, а поскольку 5(0) = 1, то
2. КОРРЕКТНОСТЬ ПОСТРОЕНИЯ РЕКУРРЕНТНОГО СООТНОШЕНИЯ ДЛЯ СУММЫ
Пакет ВитТооЦНуре^еоше!™] предоставляет процедуру ZeilbergerRecurrence, которая для заданных Т(п, к), -1, VI, и2, г2 строит рекуррентное соотношение для 5(п) по формуле (1.3), если для Т(п, к) получена Z-пара (алгоритм Цейлбергера реализован процедурой Zeilberger в этом же пакете). Чтобы получить формулу (1.3), соотношение (1.2) суммируется по к на интервале [щп + VI, и2п + г2]:
U2U+V2
U2U+V2
ЬТ (п,к)= (С(п,к + 1)
-С(п,к)).
Однако так суммировать (1.2) можно только в случае, если на [-1п + VI, и2п + г2 + 1] не существует целых особенностей рациональной функции Я(п,к).
Пример 3. Продолжаем пример 2. Поскольку рациональная функция
R(n,k) =
2k2
(-n + k - 1)(n + 1)
□
Однако известно (см. [4], [5]), что применение этого подхода может быть некорректным. В худшем случае, можно получить неверный результат. Или достаточно простой ответ не будет получен.
Пример 2. Для T(n,k) из примера 1 Maple не может вычислить сумму при увеличении верхней границы суммирования:
> SumTools:-Hypergeometric:-
> DefiniteSum(T,n,k,0..n+1);
имеет в знаменателе множитель (-n + k - 1), программа при вычислении
G(n, k + 1) = R(n, n + 1)T (n, n + 1)
в правой части (1.3) получает ошибку деления на ноль и не может построить рекуррентное соотношение для S(n) = Y1 П+0 T(n, k):
> SumTools:-Hypergeometric:-
> ZeilbergerRecurrence(T,n,k,S,0..n+1);
Error, (in SumTools:-Hypergeometric:-
ZeilbergerRecurrence) unable to compute the recurrence
□
Отсутствие целых особенностей R(n, k) на интервале суммирования — достаточное условие
k
корректности использования (1.3), но не необходимое. В работе [5] рассмотрено другое достаточное условие, допускающее наличие таких особенностей.
Итак, пусть для данного Т(п, к) построена Z-пара (Ь, С), где С(п, к) = Я(п, к)Т(п, к). Пусть знаменатель рациональной функции Я(п, к) делится на (п — п0), где п0 € 2. Это значит, что Я(п, к) имеет целые особенности вида
Для S(n) = ^П=-га T(n, k) по формуле (1.3) по-
(n0, к), при всех k G Z.
(2.1)
Тогда использование (1.3) будет некорректно при п = по. Пусть далее, знаменатель Я(п,к) делится на (щ0п + г0 — к), где и0,г0 € 2 и щ < щ0 < и2, то есть Я(п, к) имеет целые особенности вида
(п, щ0п + г0) при п € (2.2)
Если для всех достаточно больших п эти особенности попадают в интервал суммирования, то есть выполняется
щ п + VI + 1 < щ0п + г0 < щ2п + г2,
то использование (1.3) будет так же некорректно. Предлагаем представить исходную сумму следующим образом:
«0 га+^о—2
£ (п) = Е Т (п, к) + Т (п,щ0п + г0 — 1) +
к=у,1П+Ь1
+ Т (п,здп + г0) + Е Т (п, к).
к=«о™+^о+1
Если Я(п, к) не имеет других целых особенностей в данном интервале, то применение формулы (1.3) к суммам в правой части этого представления будет корректным для достаточно больших п. Если существуют другие особенности вида (2.2), мы продолжим разбивать Б(п).
Пример 4. Для
T (n,k) = 4-fc( 2kk_57)(k + n)
алгоритм Цейлбергера вычисляет Z-пару
т _ , п _ 2 (15—3n—4fc+3nfc+fc2)(fc—2)^^ ,ч L = 1 G = 3 (fc-4)(fc+ra) T (П, k).
лучаем
Б (п) = С(п, п + 1) — С(п, —п)
_ 4—п (6 + 2п2 — п)(п — 1) /2п — 5 (п) = ~3 п — 3 V п — 4
Полученное соотношение верно только при 0 < п < 2, неприменимо при п = 3 и неверно при п > 3. Это связано с тем, что при п > 3 внутри интервала суммирования находится корень к = 4 знаменателя Я(п, к). Разбиваем сумму 2
Б(п) = Е Т(п, к) + Т(п, 3) + Т(п, 4) +
fc=— га
+ Е T (n,k),
k=5
применяем (1.3) к двум суммам в правой части
S(n) = G(n, 3) _ G(n, —n) + T(n, 3) + + T(n, 4) + G(n, n + 1) — G(n, 5)
S (n) = 128 + lis n+
4-n (6+2ra2-ra)(ra-1) /2ra-5\
+
n-3
n—4 ,
Последнее соотношение верно при п > 3.
3. НУЛЕВЫЕ СЛАГАЕМЫЕ Пример 5. Рассмотрим другой пример. Для
□
T(n, k) = 2
к( 2n _ k 2n
Z-пара
т = Е 4 С = 1 (—6га—6+к)(—2п+к—1) Т(п к) Ь = Е — 4, С = 2-(га+1)(2га+1)-Т (п, к).
Для Б(п) = ^П=0 Т(п, к) рекуррентное соотношение
Б (п + 1) — 4Б(п) = —3,
имеет решение (—1 + Б(0))4п + 1, а поскольку Б(0) = 1, получаем
Е 2А
k=0
2n - k 2n
= 1.
Эту сумму Maple не может вычислить, несмотря на то что R(n, k) не имеет особенностей на интервале суммирования:
3
> T := 2~k*binomial(2*n-k, 2*n):
> Sum(T,k=0..n) =
> SumTools:-Hypergeometric:-
> DefiniteSum(T,n,k,0 .. n);
ЕП=о 2k binomial(2 n - k, 2 n) =
ЕП=о 2k binomial(2 n - k, 2 n)
> SumTools:-Hypergeometric:-
> ZeilbergerRecurrence(T,n,k,S,0..n);
Error, (in SumTools:-Hypergeometric:-
ZeilbergerRecurrence) unable to compute the recurrence
Однако для вычисления этой суммы нет необходимости применять алгоритм Цейлбергера. В S(n) только одно слагаемое отлично от нуля. Чтобы убедиться в этом, рассмотрим H-систему данного терма:
2(n + 1)(2n + 1) T(n + 1,k) =
= (-2n - 2 + k)(-2n + k - 1) T(n, k) (-2n + k) T(n,k + 1) = 2 kT(n,k).
Коэффициенты этой системы являются произведением линейных по n, k множителей. Для таких полиномов можно найти все целые корни. Выпишем целые корни второго соотношения
(n, 0), (n, 2n) для n £ Z
и разделим множество целых значений k на три части: k < 0, 1 < k < 2n, 2n + 1 < k. Запишем T(n, k) следующим образом:
2k T(2ra-k+1) Г(-к+1)Г(2п+1)
T(n, k) = 0
2k Г(к) Г(-2п+к)Г(2п+1)
Отсюда сразу следует
k<0 0 <k < 2n 2n < k
Y T(n,k)= T(n, 0) = 1.
к=0
□
Итак, пусть коэффициенты Н-системы данного терма таковы, что мы можем определить все их целые корни. Пусть целые корни р2(п,к - 1) и д2(п, к - 1) имеют вид
где Ui,Vi € Z (3 < г < п), и для достаточно больших п > по выполняется
и,1п+и1 < Uin+Vi < Ui+ln+Vi+l < и,2п+и2 (3.2)
для 3 < г < п - 1. Разобьем искомую сумму следующим образом:
«зга+^з —1
Б (п)= Y Т1(п,к) + ••• +
к=и 1 n+Vl Ui+1n+Vi+1 — 1
+ ^ Щп,к) + ••• +
k=uin+vi +
U2n+V2
Y
k=Un n+v-q
Tn (n,k),
где
Ti(n,k) = «f'MI
' ' p2(n,k-1)
q2(n,uin+vi) t(n u.n + v.)
no (n,U„-n+Vo) ^ ' i г'
P2 (n,Uin+Vi)
4
k-1
Ti(n,k)= T(n, u.n + Vi) П
q2(n,j)
P2 (n, j)'
(n, un + Vi) при n £ Z,
(3.1)
j=Uin+Vi
Определяем все г такие, что Т(п, щп + V^ = 0 для всех достаточно больших п > щ. Для остальных г к соответствующим суммам Б^,(п) применяем алгоритм Цейлбергера. Причем, разбивать эти суммы, как описано в предыдущем разделе, нет необходимости, поскольку Т,^(п,к), представимые через Г-функции, будут удовлетворять достаточному условию из [5], где вместо соотношения (1.2) используется
ЬТ^п,к) = Иш (Е(п,х + 1)Т(п, х + 1)-
х^к
-К(п, х)Т,^(п, х)).
Оно выполняется при всех
щп + Vi <к < щ+т + Vi+l - 1,
и суммы удовлетворяют рекуррентным соотношениям
ЬБ^п) =
= liШx^Ui+ln+Vi+l —1 Е(п, х + 1)Т^п, х + 1)- (3.3) - НШх^ «in+Vi К(п,х)Т^п,х) + Е^п).
Пример 6. Рассмотрим H-систему для T(n, k) из примера 1:
(—n + k — 1) T (n + 1, k) = (—n — k — 1) T (n, k)
(k + 1)2 T(n, k + 1) = (n + k + 1)(—n + k) T(n, k)
Делим множество целых значений k на четыре части:
T(n, k) =
Г 0
0
k < —n — 1 n k 1
( —1)kr(n+fc+1) 0 ^ , ^ Г(п—fc+1)r(fc+1)2 0 < k < n
0 k > n
Тогда
n+1
]TT (n,k) = E T (n,k) = (—1)n
k=0
k=0
□
Пример 7. Рассмотрим еще оди
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.