5.8 МЕХАНИЧЕСКОЕ СУММИРОВАНИЕ

Алгоритм Госпера замечателен сам по себе, однако он позволяет найти выражение в замкнутом виде лишь для некоторых биномиальных сумм из числа встречающихся на практике. Дорон Зильбергер [120] сумел так расширить алгоритм Госпера, что он стал еще замечательнее и теперь справляется с куда большим числом случаев. Используя расширение Зильбергера, мы можем не только находить частные суммы, но и выполнять суммирование по всем к, так что у нас появляется альтернатива гипергеометрическим методам из разд. 5.5 и 5.6. При этом вычисления, как и в исходном методе Госпера, могут выполняться на компьютере почти механически; нам не нужно рассуждать или полагаться на удачу.

Основная идея заключается в том, чтобы рассматривать наше слагаемое как функцию от двух переменных пик. (В алгоритме Госпера мы писали просто Если неопределенная сумма по к не выражается в гипергеометрических членах — и давайте считать, что так оно и есть, исключение составляют лишь немногие суммы, - то, как заметил Зильбергер, часто удается так видоизменить чтобы получить иные слагаемые, которые уже суммируются в неопределенном виде. Например, на практике часто оказывается, что неопределенно суммируемо по к для подходящих многочленов . А вычислив сумму по к, мы получаем рекуррентное соотношение по которое и решает нашу задачу.

Чтобы познакомиться с общим подходом, начнем с рассмотрения простого случая. Предположим, что мы забыли биномиальную теорему и хотим вычислить Как можно было бы получить ответ, если мы не обладаем даром ясновидения и никакие догадки не приходят в голову? Ранее в этой главе, например в задаче 3 из разд. 5.2, мы научились заменять на

и с легкостью получать требуемый результат. Но есть и более систематический путь.

Пусть — суммируемая величина. Алгоритм Госпера говорит, что мы не можем вычислить частные суммы в гипергеометрических членах для произвольного кроме случая Так что вместо этого рассмотрим более общее слагаемое

Попробуем найти значения при которых алгоритм Госпера сработает успешно. Во-первых, мы хотели бы упростить (5.126), применяя соотношение между с тем чтобы исключить из выражения. Поскольку

имеем

где

Теперь применим алгоритм Госпера к с фиксированным Сначала запишем

как в (5.117). Метод Госпера нашел бы такое представление, начав с но в расширении Зильбергера лучше начать с Заметим, что если положить то уравнение (5.127) будет эквивалентно

Таким образом, мы получим удовлетворяющие (5.127), если найдем удовлетворяющие (5.128), начав с Это облегчает жизнь, поскольку не содержит неизвестных величин которые входят в . В нашем случае так что

и мы можем взять Предполагается, что эти многочлены удовлетворяют (5.118). Если же нет, то мы должны удалить из некоторые множители и включить соответствующие множители (5.119) в но это нужно делать, только если величина в (5.118) является целой положительной константой, не зависящей от поскольку мы хотим, чтобы наши вычисления были справедливы для произвольного . (Формулы, которые мы выводим, будут в действительности справедливы, даже когда — не целые (при использовании обобщенных факториалов (5.83).)

Наши начальные удовлетворяют (5.118) в указанном смысле, так что можно переводить прямо к шагу 2 в алгоритме Госпера; мы хотели бы решить уравнение, аналогичное (5.122), с использованием (5.127) вместо (5.117). Так что наша задача — решить

относительно секретного многочлена

(Коэффициентами могут быть не константы, а функции от ) В нашем случае уравнение (5.129) имеет вид

и мы рассматриваем его как полиномиальное уравнение по к, где коэффициенты зависят от Как и ранее, находим степень многочлена рассматривая многочлены Поскольку (в предположении , имеем не зависит от Наше уравнение превращается в

приравнивая коэффициенты при одинаковых степенях к, мы получаем эквивалентную систему уравнений, не содержащую к:

Таким образом, мы имеем решение (5.129) с

(По случайному совпадению исчезло.)

Итак, мы установили, пользуясь чисто механическим методом, что суммируемо в гипергеометрических членах. Иными словами,

где — гипергеометрический член относительно к. Чему равно ? В соответствии с (5.121) и (5.128) имеем

поскольку (На практике почти всегда оказывается равным 1.) Следовательно,

И, несомненно, концы с концами сходятся — равенство (5.131) выполняется:

Но в действительности нам не требуется точно знать поскольку мы собираемся суммировать по всем целым к. Все, что нам нужно - это то, что отлично от нуля лишь для конечного множества значений к, когда — произвольное заданное неотрицательное целое. Тогда сумма по всем к должна свернуться в 0.

Пусть это сумма» с которой мы начинали и теперь готовы вычислить ее, поскольку уже много знаем о . Процедура Госпера—Зильбергера установила, что

Но эта сумма равна Следовательно,

Ага! Эту рекуррентность мы умеем решать, если нам известно -Очевидно, однако, что Поэтому мы заключаем, что для всех целых

Посмотрим вновь на проделанное вычисление и подытожим наши действия в такой форме, которую можно будет использовать и для других слагаемых Алгоритм Госпера—Зильбергера записывается следующим образом (считаем, что дано):

0 Положим (Мы будем искать рекуррентность по порядка I.)

1 Пусть где — неизвестные функции. Используя свойства , найдем — линейную комбинацию коэффициентами которой являются многочлены от такую, что может быть записана в форме

где является гипергеометрическим членом относительно к. Найдем многочлены так чтобы отношение членов выражалось в виде (5.128) и при этом удовлетворяли условию Госпера (5.118). Положим

2а Положим и

2b Если то определим как в (5.130) и рассмотрим линейные уравнения относительно по" лучаемые приравниванием коэффициентов при степенях к в основном уравнении (5.129). Если эти уравнения имеют решение, в котором все не равны одновременно нулю, то перейдем к шагу 4. Иначе, если есть целое число, большее d ( — коэффициент при — коэффициент при в то положим и повторим шаг

3 (Слагаемое не суммируемо в гипергеометрических членах.) Увеличим I на 1 и вернемся к шагу 1.

4 (Успех.) Положим Алгоритм нашел, что .

Позднее мы докажем, что этот алгоритм завершается успешно для всех из широкого класса выражений, называемых подходящими членами.

Биномиальную теорему можно вывести многими способами, так что наш первый пример применения алгоритма Госпера— Зильбергера был скорее поучительным, нежели впечатляющим. На этот раз попробуем справиться со сверткой Вандермонда. Смогут ли Госпер с Зильбергером вывести алгоритмически, что простой вид? Алгоритм начинает с что, по сути, есть повторение исходного алгоритма Госпера, т. е. мы пытаемся проверить, суммируемо ли в гипергеометрических членах. Тут нас ждет сюрприз: это слагаемое оказывается суммируемым, если а — некоторое специальное неотрицательное целое число (см. упр. 94). Однако нас интересуют произвольные а и и алгоритм быстро обнаруживает, что в общем случае неопределенная сумма не является гипергеометрическим членом. Так что I увеличивается с 0 до 1 и алгоритм теперь пробует . На следующем шаге, как в нашем выводе биномиальной теоремы, мы записываем где получается путем сокращения дробей в . В этом случае — мы настоятельно рекомендуем читателю проверить все наши выкладки на листке бумаги; они не такие сложные, как кажется, — все происходит почти так же, как и ранее, но с

Шаг 2а находит, что так что опять не зависит от к. Основное уравнение Госпера (5.129) оказывается эквивалентным системе двух уравнений от трех неизвестных

которая имеет решение

Мы заключаем, что суммируемо по следовательно, если то имеет место рекуррентное соотношение:

и, значит, поскольку Как все замечательно получилось!

А что мы сможем сделать с тождеством Заальшютца (5.28), содержащим три биномиальных коэффициента? Доказательство (5.28) в упр. 43 интересно, конечно, но оно требует некоторого озарения. Преобразуя искусство в науку, мы стремимся заменить озарение работой в поте лица; так что давайте посмотрим, в состоянии ли метод суммирования Госпера—Зильбергера обнаружить и доказать (5.28) чисто механическим путем. Для удобства сделаем подстановки с, так чтобы (5.28) приняло более симметричный вид

Чтобы сумма была конечной, будем полагать, что либо а, либо неотрицательное целое.

Положим Двигаясь по проторенной дорожке, положим

и попытаемся решить (5.129) относительно . Снова оказывается, что , но на этот раз так что тут мы, кажется, застопорились. Однако шаг представляет на выбор для степени важный второй вариант стоит отказываться от еще одной попытки, так что испытаем сейчас этот выбор. Уже так что тогда как многочлен каким-то чудом имеет степень 1 относительно k — коэффициенты При сокращаются! Следовательно, метод Госпера позволяет взять Уравнения, которые нам предстоит решать, выглядят так:

и мы находим

пролив совсем немного пота. Отсюда немедленно вытекает тождество (5.134).

Можно получить аналогичное доказательство (5.134), если работать с вместо (См. упр. 99.)

Подход Госпера—Зильбергера помогает вычислять не только неопределенные суммы по всем к, но и определенные суммы по ограниченному диапазону. Рассмотрим, например, сумму

Для мы получили „неожиданный" результат (5.20); может быть для Госпера и Зильбергера здесь нет ничего неожиданного? Обозначая получаем

Решением уравнения (5.129) будет Следовательно, мы находим

где Теперь можно просуммировать (5.136) для 0 к , получая

Но , так что

Сразу ясно, что действительно особый случай, и Более того, можно упростить рекуррентное соотношение (5.137), умножив обе части на суммирующий множитель это приводит к общему тождеству

которое мало кто мог ожидать до появления Госпера с Зильбергером. Теперь же производство подобных тождеств — чисто рутинная работа.

А вот похожая сумма

встретившаяся нам в (5.74), как быть с ней? Полные уверенности, мы полагаем и затем вычисляем

Но увы — уравнение (5.129) не решается, если поскольку степень должна бы быть равной

Никаких проблем; просто добавим еще один параметр и испытаем

Теперь можно взять и (5.129) имеет решение

Мы обнаружили, что

где равно Суммирование от до дает

Но для любого так что получаем

Мы будем изучать такие рекуррентности в гл. 6 и 7; методы этих глав позволяют немедленно перейти от (5.140) к замкнутой форме (5.74) при условии

Еще один, знаменитый пример завершает картину. В 1978 г. французский ученый Роже Апери решил проблему, которая долго не поддавалась усилиям математиков, доказав, что число иррационально [8]. Одна из важнейших частей его работы включает вычисление биномиальной суммы

Рекуррентное соотношение для этой последовательности, которое он объявил, другие математики в то время не могли проверить. (С тех пор числа стали известны как числа Апери; имеем ) Наконец, Дон Загиер и Генри Коэн [46] нашли доказательство предположения Апери, и это их доказательство для одной (но трудной) суммы стало впоследствии одним из важнейших соображений, приведших Зильбергера к открытию общего метода, который мы сейчас обсуждаем.

Ну вот, мы увидели достаточно примеров, чтобы сумма (5.141) стала почти тривиальной. Полагая , попытаемся решить (5-129) с

(То обстоятельство, что имеет множитель — множитель к, можно проигнорировать; это не нарушает (5.118), поскольку мы рассматриваем как переменную, а не как фиксированное целое.) Так как можно положить и возьмем

С таким выбором рекуррентное соотношение (5.129) превращается в пять уравнений относительно шести неизвестных Так, например, приравнивание коэффициентов при упрощается до уравнения

уравнением для будет

Три других уравнения более сложны. Но главное здесь то, что эти линейные уравнения — как и вообще все уравнения, появляющиеся на этой стадии алгоритма Госпера—Зильбергера, — однородны (их правая часть равна 0). Поэтому они всегда имеют ненулевое решение, если только число неизвестных превышает число уравнений. В нашем случае решением оказывается

Следовательно,

Суммируя по к, получаем немыслимое рекуррентное соотношение Апери,

Неужели метод Госпера—Зильбергера работает со всеми суммами, которые встретились нам в этой главе? Нет. Он неприменим в случае, когда равно из (5.65), поскольку отношение членов не является рациональной функцией от к. Он также не справляется со случаями вроде поскольку здесь второе отношение членов не является рациональной функцией от к. (Мы можем, однако, получить решение в этом случае, просуммировав и затем положив ) И, наконец, этот метод терпит неудачу для удивительно простого слагаемого, наподобие даже несмотря на то, что оба отношения рациональные функции от и к; см. упр. 107.

Вместе с тем, алгоритм Госпера—Зильбергера с гарантией приводит к успеху в огромном числе случаев, а именно, когда слагаемое является так называемым подходящим членом, т. е. может быть записано в виде

Здесь — многочлены от коэффициенты — определенные целочисленные константы; параметры ненулевые; остальные величины — произвольные комплексные числа. Мы докажем, что если является подходящим членом, то найдутся такие многочлены не все равные нулю, и подходящий член что

Следующее доказательство принадлежит Вильфу и Зильбергеру [54].

Обозначим через оператор, увеличивающий на 1, а через К — оператор, увеличивающий к на 1, так что, например, Мы будем изучать линейные разностные операторы от а именно операторные многочлены вида

где каждый коэффициент есть многочлен от Первое наше наблюдение состоит в том, что, если - произвольный подходящий член и произвольный разностный оператор, то подходящий член. Допустим, и Н задаются, соответственно, равенствами (5.143) и (5.145); тогда мы определим слагаемое

Если, например, есть базовым слагаемым, соответствующим линейному разностному оператору степеней I и будет Главное то, что равно умноженному на некоторый многочлен от и к, если Конечные суммы многочленов — снова многочлены, так что имеет требуемый вид (5.143).

На следующем шаге нам надо показать, что если — подходящий член, то всегда найдется такой линейный разностный оператор что

Если то сдвинутый член есть произведение и многочлена от и к, имеющего степень по к, самое большее,

Следовательно, требуемый оператор существует, если мы сможем решить систему из однородных линейных уравнений с переменными коэффициентами которых являются многочлены от Все, что нам требуется, — это выбрать настолько большие I и чтобы выполнялось неравенство . Например, можно взять , где

Последний шаг доказательства заключается в переходе от уравнения к решению (5.144). Пусть Н выбран так, чтобы минимизировать иными словами, Н имеет наименьшую возможную степень по К. Можно записать

для некоторого линейного разностного оператора Пусть . Тогда — подходящий член и (5.144) имеет место.

Доказательство почти завершено, но надо еще проверить, что не является просто нулевым оператором. Если это так, то не зависит от к. Поэтому найдутся такие многочлены что Но тогда является ненулевым разностным оператором степени который аннулирует это противоречит минимальности Таким образом, наше доказательство (5.144) завершено.

Теперь, зная что (5.144) выполнено для некоторого подходящего члена Т, мы можем быть уверены, что алгоритм Госпера успешно найдет Т (или Т плюс константу). Мы обосновали алгоритм Госпера только для случая гипергеометрических членов зависящих от одной переменной к, однако можно распространить доказательство на случай двух переменных следующим образом. Существует бесконечно много комплексных чисел для которых выполнено условие (5.118), если мы разложим как многочлены от к, и для которых вычисление степени на шаге 2 дает тот же результат, что в алгоритме Госпера для одной переменной. Для всех таких наше предыдущее доказательство устанавливает существование нужного многочлена ; следовательно, существует и требуемый многочлен от двух переменных пик.

Мы доказали, что алгоритм Госпера—Зильбергера сможет найти решение (5.144) Для некоторого, как можно меньшего I. Это решение дает нам рекуррентное соотношение по для вычисления суммы по к любого подходящего члена при условии, что отлично от нуля лишь для конечного множества значений к. И, разумеется, можно поменять ролями пик, поскольку определение подходящего члена (5.143) симметрично относительно и к.

Упражнения 98-108 дают еще несколько примеров применения алгоритма Госпера—Зильбергера, иллюстрируя его разносторонность. Вильф и Зильбергер [54] существенно расширили эти результаты и получили метод, который справляется с обобщенными биномиальными коэффициентами и кратными суммами.