Главная > Математика > Конкретная математика. Основание информатики
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.7 ЧАСТИЧНЫЕ ГИПЕРГЕОМЕТРИЧЕСКИЕ СУММЫ

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

Изложенное в гл. 2 обеспечивает нас чудесным способом трактовки формул, подобных этой. Если то мы условились писать, что и

Кроме того, если а и — целые числа и а то

Поэтому тождество (5.114) соответствует формуле вычисления неопределенных сумм

и формуле вычисления разностей

Начав с функции можно легко вычислить — функцию, суммой которой будет . Но гораздо труднее, начав с выяснить ее неопределенную сумму — функция может вообще не выражаться в замкнутой форме. Так, по всей видимости, сумма к не выражается в простой форме — иначе мы умели бы вычислять суммы типа которыми мы беспомощны. Но, может быть, все же существует простая формула для которую мы просто еще не придумали; почему мы уверены, что ее нет?

В 1977 г. Р. У. Госпер [79] обнаружил замечательный способ вычисления неопределенной суммы если только принадлежат обширному классу функций, называемых гипергеометрическими членами. Обозначим через

член гипергеометрического ряда Будем рассматривать как функцию а не как функцию Оказывается, что во многих случаях существуют параметры такие, что

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

существуют. Алгоритм Госпера либо находит такие константы, либо доказывает, что их не существует.

В общем случае мы говорим, что есть гипергеометрический член, если является рациональной функцией от к, не равной тождественно нулю. Это значит, по существу, что кратно с постоянным множителем члену вида (5.115). (Тут возникают некоторые технические детали, связанные с нулями, поскольку мы хотели бы, чтобы имело смысл для отрицательных к, а также когда одно или более из значений в (5.115) нулевое или целое отрицательное. Строго говоря, наиболее общий гипергеометрический член получится, если умножить (5.115) на ненулевую константу и на некоторую степень 0, а затем сократить нули в числителе и знаменателе. Пример в упр. 12 поможет прояснить это общее правило.)

Предположим, что мы хотим найти где — гипергеометрический член. Алгоритм Госпера состоит из двух шагов, каждый из которых достаточно прямолинеен. Шаг 1 состоит в том, чтобы выразить отношение членов в специальной форме

где суть многочлены, подчиняющиеся следующему условию:

Данное условие легко достижимо: мы начинаем, предварительно положив полагаем равными числителю и знаменателю значения членов и разлагаем их на линейные множители. Если, например, имеет вид (5.115), то начинаем с факторизации Затем проверяем, не нарушено ли условие (5.118). Если имеют сомножителями где то выделяем их из и заменяем на

Новые по-прежнему удовлетворяют (5.117), и эта процедура повторяется до тех пор, пока не будет выполнено условие (5.118). Вскоре мы поймем, почему (5.118) так важно.

Шаг 2 алгоритма Госпера завершает работу — он состоит в нахождении гипергеометрического члена такого, что

если это возможно. Однако совсем не очевидно, как добиться этого; чтобы двигаться дальше, нам нужно развить какую-то

теорию. Госпер, проанализировав множество частных случаев, заметил, что разумно записать неизвестную функцию в виде

где — некоторая секретная функция, которую необходимо каким-то образом раскрыть. Подставляя (5.121) в (5.120) и применяя (5.117), получаем

так что мы должны иметь:

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

Мы предполагаем, что — гипергеометрический член, а это значит, что является рациональной по к функцией. Поэтому, согласно (5.121) и (5.120), функция является рациональной по к функцией, а сама функция должна быть отношением многочленов:

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

а если положить то получим

Теперь потому что не имеют общих корней. К тому же потому что в противном случае функция содержала бы сомножитель или вопреки допущению о максимальности Поэтому

Но это противоречит условию (5.118). Следовательно, функция должна быть многочленом.

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

с неизвестными коэффициентами и подставить данное выражение в основное рекуррентное соотношение (5.122). Многочлен будет удовлетворять данной рекуррентности тогда и только тогда, когда все удовлетворяют линейным уравнениям, получаемым в результате приравнивания коэффициентов при каждой степени к в (5.122).

Но как установить степень Оказывается, что в действительности имеются самое большее две возможности. Уравнение (5.122) может быть переписано в виде

где

Если многочлен имеет степень то сумма также имеет степень в то время как разность степень (Можно считать, что нулевой многочлен имеет степень — 1.) Обозначим через степень многочлена . Если то степенью правой части равенства (5.124) будет так что мы должны получить . С другой стороны, если то можно записать, что где правая часть уравнения (5.124) имеет вид

две возможности таковы: либо либо Второй случай необходимо проверять только тогда, когда является некоторым целым числом большим чем

Итак, мы располагаем достаточным количеством фактов для того, чтобы выполнить шаг 2 алгоритма Госпера: попробовав, самое большее, два значения мы можем найти если только уравнение (5.122) имеет полиномиальное решение. Если существует, то его можно подставить в (5.121) и получить нашу функцию Т. Если же нет, то тем самым доказано, что не суммируемо в гипергеометрических членах.

Пора привести какой-нибудь пример: попробуем вычислить частичную сумму (5.114). Методу Госпера должно быть под силу установить величину

при любом фиксированном так что мы будем искать сумму членов

На шаге 1 мы должны представить отношение членов в требуемом виде (5.117):

т.е. мы просто выбираем Подобный выбор удовлетворяет условию (5.118), если только не является целым отрицательным числом: предположим, что таковым не является.

Теперь переходим к шагу 2. Согласно (5.124) нам следует рассмотреть многочлены . А поскольку имеет степень большую, чем степень то необходимо рассмотреть два случая: либо что равно 0, либо где так что Первый случай предпочтительнее, поскольку он не требует, чтобы было целым положительным, так что займемся им в первую очередь; нам надо будет рассмотреть вторую возможность для только если первый случай не приведет к успеху. Если то значение есть просто и уравнение (5.122) сводится к

Следовательно, мы выбираем Это удовлетворяет требуемым условиям и дает точно тот результат, который мы рассчитывали подтвердить:

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

Как бы то ни было, раз уж мы избавились от невозможного, все, что бы ни осталось, обязано быть истинным, каким бы невероятным оно не казалось (по утверждению Ш. Холмса [162]). Когда мы определяли то решили пренебречь возможностью того, что могло быть целым отрицательным числом. А что, если это так? Давайте положим где — положительное число. Тогда отношение членов для есть

и, согласно (5.119), его следует представлять при помощи Теперь шаг 2 метода Госпера советует поискать многочлен степени (а вдруг повезет?). Так, при рекуррентность (5.122) дает следующее уравнение, которое нужно решить:

Приравнивание коэффициентов при к и 1 показывает, что

следовательно, является решением, а

Может ли это быть желаемой величиной суммы? Да, все получается:

Формулу суммирования можно записать в другом виде, с верхним пределом

В этом представлении скрыт тот факт, что биномиальный коэффициент суммируем в гипергеометрических членах, ибо не является гипергеометрическим членом. (См. упр. 12.)

Со знаменателем (5.121) могут возникнуть затруднения, если для некоторого целого к. Упражнение 97 помогает понять, что можно сделать в такой ситуации.

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

Марко Петковшек [236] нашел замечательный способ обобщения алгоритма Госпера на более сложные задачи обращения. А именно, он показал, как найти все гипергеометрические члены удовлетворяющие рекуррентности порядка

если даны гипергеометрический член и многочлены

<< Предыдущий параграф Следующий параграф >>
Оглавление