„ XT /п + к\ 12к\{-1)>

Пример 2. Чему равна сумма > I ) [ и )т-i-i если п - неотрицательное

целое число: к

Решение. Это более трудная задача, так как индекс суммирования fc встречается в шести местах! Сначала применим формулу (20) и получим

п + к\ (п\ {-If

Теперь можно вздохнуть с облегчением, поскольку некоторых опасностей, таящихся в первоначальной формуле, мы уже избежали. Следующий шаг очевиден: применим формулу (7) так, как в примере 1:

Прекрасно! Исчезло еще одно fc. И с этого момента перед нами открываются два одинаково перспективных пути. Можно заменить коэффициентом ("*) в

предположении, что fc > О, и вычислить сумму с помощью формулы (23):

Е/п + fc\ /п + 1\ (-1)* п )\к + \) п + \

к>0

П-1 + к\ /пЦ-1\

к>1

1 v/n-l + fc\/п + 1\- 1 fn-l\

= -lU гг )( fc У-Л п )

к>0

=--(-1)"+Ч""-f""-f"" V

n + V \ -1 J п + 1\ п J п + 1\ п J

Биномиальный коэффициент ("~) равен нулю, за исключением случая п = О, когда он равен единице. Поэтому решение задачи можно дать в виде [п=:0], воспол1>зо-вавшись обозначением Айверсона (формула 1.2.3-(16)), или в виде OnOj воспользовавшись символом Кронекера (формула 1.2.3-(19)).

Другой способ решения, начиная от формулы (27), заключается в использовании формулы (17). В результате получаем

(-{п + 1)\ (п + 1\ 1

к J\k + lJn + l

Теперь можно применить формулу (22) и получить

/п + 1- {п + 1)\ 1 /0\ 1 Vn-bl-H-oJn-M~ \п)п + 1 Итак, мы снова получили тот же ответ:

V/n-bfc\/2fc\(-1)*

Е( 2fc )(fc)lTr=- «"0- (28)

тт о и п + к \(2k\{-\Y

Пример 3. Чему равна сумма > I ) 1 ) -если тип - положителв

ные целые числа? (г-\т+ 2kJ \ к J к + 1

Решение. Если бы m было равно нулю, мы получили бы ту же сумму с которой имели дело в примере 2. Но присутствие ненулевого m означает, что мы не можем воспользоваться методом из предыдущего примера, так как уже на первом шаге формулу (20) применить нельзя. В этой ситуации имеет смысл усложнить задачу, заменив нежелательный коэффициент {2к) суммой членов вида {2к)-В результате задача сведется к ряду задач, решать которые мы уже умеем. Итак, воспользуемся формулой (25), положив

г = п + к-1, т = 2к, s - О, п = т - 1

В результате получим

к 0<j<n+k-l

Мы хотим выполнить суммирование сначала по к, но для изменения порядка сум-о мирования требуется, чтобы суммирование происходило по тем к, которые > О п > j - п + 1. К сожалению, последнее условие вызывает проблемы, так как при j > п сумма не определена. Попытаемся спасти ситуацию. Для начала заметим, что члены суммы (29) равны нулю при п < j < п + к - 1. Отсюда следует, что к > I; таким образом, О <n + k-l-j < k-l <2ки первый биномиальный коэффициент в формуле (29) обращается в нуль. Следовательно, во второй сумме можно вьшолнять суммирование по О < j < n и теперь с изменением порядка суммирования никаких проблем не будет. Суммируя по к согласно (28), получим

0<j<n

Все члены этой суммы, за исключением того, который соответствует j = п - 1, обращаются в нуль. Таким образом, окончательно получаем

С:;)

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

Пример 4. Докажите, что

Ak{r,t)An-k{s,t) = А{г + зЛ), целое п > О, (30)

где An{x,t) - многочлен степени п по х, такой, что

, , , fx - nt\ X

An(x,t)-[-- дляа;/гг<.

\ п / X - ni

Решение. Можно предположить, что т ф kt ф s для О < < п, так как обе части (30) -это многочлены по г, s, t. Вычислим сумму

/г - kt\ /s-{n- k)t\ г s

\ к )\ п-к ) r-kt s-{n-k)t

которая кажется еще более страшной, чем во всех предыдущих задачах! Тем не менее обратите внимание на сильное сходство с формулой (26), а также на случай t = 0.

Возникает искушение заменить

/r-kt\ г /r-kt-l\r

[ к «ьфажешем ( jp

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

1 Г 1 1 \

s-nt \r-kt s-{n-k)t)

r-kt s-{n-k)t Г +

Подставляя это вьфажение в исходную сумму, получаем

S Sf" -kt\fs-{n- k)t\ г r + s-nt\ к )[ п-к )r-kt

г /r-fet\ fs-{n-k)t\ s r + s-nt\ к J\ n-k ) s-(n-k)t

И теперь, если во второй сумме вьшолнить замену fe на п - fe, то по формуле (26) можно вычислить обе суммы; отсюда непосредственно получаем искомый результат. Тождества (26) и (30) получены Г. А. Роте (Н. А. Rothe) и опубликованы в его книге Formulse de Зепегшп Reversfone (Leipzig, 1793), а частные случаи этих формул время от времени продолжают "открывать". Об интересной истории данных тождеств и некоторых их обобщениях речь идет в статье Г. В. Гоулд (Н. W. Gould) и Дж. Каущси (J. Каиску), Journal of Combinatorial Theory 1 (1966), 233-248.

Пример 5. Как определить значения ao,ai,a2,..., такие, что

n\ = ao + ain + а2п{п - 1) + азп(п - 1)(п - 2) + • • • (31)

для всех неотрицательных целых п?

Решение. Ответ на этот вопрос дает равенство 1.2.5-(11), которое было приведено без доказательства в предыдущем разделе. Давайте сделаем вид, что ответ нам пока еще неизвестен. Очевидно, что задача имеет решение, так как можно положить п = О и определить cq, затем положить п = 1 и определить ci, и т. д. Сначала запишем (31) с помощью биномиальных коэффициентов:

« = Е(Э*«* (32)