5.2 НЕОБХОДИМЫЕ НАВЫКИ

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

общий план и наполнить его конкретным содержанием. Однако в „реальной действительности" мы обычно сталкиваемся не с необходимостью доказать некоторое тождество — сталкиваемся с необходимостью упростить некоторую сумму. К тому же мы не знаем, как могла бы выглядеть сумма в упрощенной форме (и существует ли таковая вообще). Разобравшись с множеством подобных сумм в этом и следующем разделах, отшлифуем свое мастерство в обращении с биномиальными коэффициентами.

Для начала испытаем свои силы на нескольких суммах, содержащих по одному биномиальному коэффициенту.

Задача 1: сумма отношений

Нам хотелось бы выразить в замкнутой форме сумму

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

Таким образом, мы заменяем отношение слева на отношение справа, и сумма приобретает вид

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

Можно также упростить граничные условия, суммируя по всем к 0: при члены суммы равны нулю. Оставшаяся сумма уже не столь страшна:

Она аналогична сумме из тождества (5.9), ибо индекс k присутствует в двух местах с одним и тем же знаком. Но здесь он —k,

а в (5.9) - наоборот. Поэтому следующий шаг напрашивается сам собой — только так и надо действовать:

Теперь можно воспользоваться формулой суммирования по обоим индексам (5.9):

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

На самом деле этот вывод проходит при любом вещественном если только не происходит деления на нуль; т. е. если не является одним из целых

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

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

Задача 2: из литературы по методам сортировки

Наша следующая сумма восходит к тем давним временам (к началу 1970-х гг.), когда люди еще не приобрели навыков свободного обращения с биномиальными коэффициентами. Одна статья, в которой предлагался улучшенный метод слияния [107], заканчивается следующим замечанием: „Можно показать, что среднее число сэкономленных пересылок данных определяется выражением

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

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

Сперва следует превратить эту сумму в то, с чем можно работать. Одного только ужасного обозначения достаточно, чтобы опустились руки у любого, за исключением полного энтузиазма рецензента (не стоит благодарности). В наших обозначениях следует записать

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

А дальше что? Переменная суммирования входит в верхний индекс биномиального коэффициента, но не входит в нижний. Так что если бы здесь не было другого к, то можно было бы упростить данную сумму и применить формулу суммирования по верхнему индексу (5.10). Но с дополнительным к этого сделать нельзя. Если бы нам удалось каким-либо образом внести это к под знак биномиального коэффициента, используя одно из наших правил внесения, то потом можно было бы просуммировать по верхнему индексу. К сожалению, и те правила здесь не работают. Но если бы вместо к было то можно было бы воспользоваться правилом внесения (5.6):

Так вот где ключ к решению! Перепишем к в виде и разобьем сумму на две:

где

Оставшиеся суммы А и В — это не что иное, как наши старые знакомые, в которых верхний индекс изменяется, в то время как нижний остается неизменным. Начнем с суммы В, ибо она выглядит попроще. Для того чтобы привести общий член данной суммы к виду левой части (5.10), достаточно ее немножко преобразовать:

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

Другая сумма почти такая же, за тем исключением, что в ней заменено на Отсюда получается выражение в замкнутой форме для суммы которое можно еще несколько упростить:

А это дает нам выражение в замкнутой форме для исходной суммы:

Даже рецензент не смог бы это упростить.

Для проверки результата опять воспользуемся небольшими величинами. Если то

что согласуется с полученной по нашей формуле величиной

Задача 3: из одного старого домашнего задания

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

Эта задача потруднее других: ни одно из тождеств, которые встречались до сих пор, применить нельзя. К тому же мы имеем дело с суммой из членов, так что их нельзя просто взять и сложить. Переменная суммирования к фигурирует в обоих индексах — верхнем и нижнем, но с разными знаками. Обращение верхнего индекса также не помогает — оно удаляет множитель но вводит в верхний индекс.

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

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

Итак, значения начинаются с чисел 1, 0, —1, 0. Даже если бы нам были известны один или два следующих члена, выражение в замкнутой форме все равно бы не просматривалось. Вот если бы была возможность найти и подтвердить рекуррентное соотношение для тогда у нас, вероятно, появилась бы возможность угадать и убедиться в правильности его решения в замкнутой форме. А для того чтобы найти рекуррентность, необходимо связать (или с при иных k), но для этого необходимо связать член типа который получается при с членами типа Это не сулит ничего хорошего: нам не известны сколько-нибудь удовлетворительные соотношения между элементами треугольника Паскаля,

отделенными друг от друга 64 рядами. Формула сложения — наш основной инструмент при доказательствах по индукции — связывает элементы, которые отделены друг от друга только одним рядом.

И тем не менее, именно это обстоятельство подводит к решающему наблюдению: на самом деле нет необходимости иметь дело с элементами, отделенными друг от друга рядами. Переменная никогда не фигурирует сама по себе, а всегда в связи с Так что — случай только для отвода глаз! Если заменить на то все, что нам нужно сделать, — это отыскать замкнутое выражение для более общей (но более простой суммы

тем самым мы получим замкнутое выражение и для . А надежда получить рекуррентность для последовательности возлагается на формулу сложения.

Значения при малых можно получить из табл. 180, если поочередно сложить и вычесть те величины, которые простираются по диагонали с юго-запада на северо-восток. Вот они:

Судя по всему, дальше будет уйма сокращений.

А теперь обратимся к формуле для и посмотрим, определяется ли оно рекуррентно. Наш замысел состоит в применении формулы сложения (5.8) и нахождении сумм, имеющих вид в окончательном выражении — нечто вроде того, что проделывали в методе приведения из гл. 2!

(На предпоследнем шаге мы воспользовались формулой которая, как мы знаем, верна при сам вывод справедлив при

С помощью этой рекуррентности можно быстро получать значения и столь же быстро убедиться, что получающаяся последовательность периодична. Действительно,

Доказательство по индукции есть простая проверка. Но если требуется дать более высоконаучное доказательство, то можно развернуть данную рекуррентность на один шаг, получая

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

И, наконец, поскольку можно установить определяя и используя замкнутое выражение для Если то а продолжая умножать на , получаем повторения чисел 2 и 4. Таким образом,

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

Задача 4: сумма с двумя биномиальными коэффициентами

Наше следующее задание — найти замкнутое выражение для суммы

Минуточку. А где же второй биномиальный коэффициент, обещанный в названии этой задачи? И зачем нужно упрощать сумму, которую мы уже упрощали? (Ведь это сумма S из задачи 2.)

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

составляющих табл. 195. Второй биномиальный коэффициент материализуется, если переписать к в виде (к):

Тем тождеством, которым нужно воспользоваться, является тождество (5.26), поскольку в нем переменная суммирования входит в оба верхних индекса, причем с разными знаками.

Однако наша сумма еще не совсем в нужном виде. Если нужно полное соответствие формуле (5.26), то верхним пределом суммирования должно быть Нет проблем: при все члены суммы равны нулю, так что можно произвести подстановку и ответом будет

Это аккуратнее по сравнению с ранее полученной формулой. А воспользовавшись правилом (5.7), эту формулу можно превратить в выведенную ранее:

Аналогичным образом можно получить интересные результаты путем подстановки определенных значений в другие известные нам тождества. Подставим, например, в (5.26). Тогда данное тождество принимает вид

Здесь левая часть есть что дает нам еще один „фирменный" способ решения задачи о сумме квадратов, которую мы до смерти замучили в гл. 2.

Мораль сей басни такова. Специальные случаи самых важных сумм лучше всего сводить к общему виду. Изучив суммы в общем виде, имеет смысл рассмотреть их простые специализации.

Задача 5: сумма с тремя сомножителями

А вот другая сумма, с которой неплохо разобраться. Желательно упростить сумму

Переменная суммирования к встречается в обоих нижних индексах с одним и тем же знаком, так что тождество (5.23) из табл. 195 весьма похоже на то, в чем мы нуждаемся. После небольших манипуляций, мы должны бы суметь им воспользоваться.

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

Нас не волнует, что когда исчезает к, то вылезает поскольку это константа. Теперь пришло время воспользоваться соотношением (5.23) и получить сумму в замкнутой форме:

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

Задача 6: сумма со многими трудностями

Следующая сумма выглядит более вызывающе. Требуется выразить в замкнутой форме сумму

Одним из наглядных показателей степени трудности той или иной суммы служит число вхождений в нее переменной суммирования. Но здесь этот показатель повергает нас в глубокий траур — индекс к встречается в шести местах! Более того, решающий шаг, который оправдал себя в предыдущей задаче — внесение чего-нибудь, находящегося за скобками биномиальных коэффициентов, в один из них, — в данном случае себя не оправдывает. Если внести то вместо него все равно явится другое к. И дело не только в этом: индекс к входит дважды с коэффициентом 2 в биномиальные коэффициенты. А мультипликативные постоянные, как правило, удалять труднее, чем аддитивные.

И тем не менее, на этот раз нам повезло: переменные находятся именно там, где требуется, для того чтобы, воспользовавшись тождеством (5.21), получить

Две двойки исчезают, а с ними и одно к. Итак, одно к пропало, пять — осталось.

Из всех оставшихся затруднений наибольшее неудобство причиняет в знаменателе, но теперь эту величину можно внести в биномиальный коэффициент (?), используя тождество (5.6):

(Напомним, что Два к пропало, четыре — осталось.

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

Три к пропало, три — осталось, и у нас появляется возможность добиться большего успеха, подключив к делу (5.24). Заменяя на получаем

Как нуль? И это после такой работы? Давайте-ка проверим это при . В самом деле нуль.

Просто ради интереса испробуем другой возможный вариант — с обращением верхнего индекса

А теперь воспользуемся тождеством (5.23) с заменой :

Подождите-ка! Это нуль при но при это единица. А ведь при другом подходе к решению данная сумма равнялась нулю во всех случаях! В чем же дело? На самом деле искомая

сумма оказывается равной 1 при так что правильное решение Мы, должно быть, сделали ошибку в предыдущем выводе.

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

Другой множитель в данной сумме, оказывается равным нулю при кроме Вот почему допущенная нами ошибка не была выявлена при проверке случая . В упр. 6 объясняется, как следовало поступить.

Задача 7: новое затруднение

Эта задача еще труднее: надо вычислить в замкнутой форме сумму

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

Однако если бы удалось каким-то образом избавиться от то можно было бы воспользоваться только что полученным результатом. Так что наш план действий таков: заменить суммой членов вида при некотором целом неотрицательном I; тогда общий член суммы будет выглядеть как общий член суммы из задачи и можно изменить порядок суммирования.

Но чем же заменить Скрупулезный перебор выведенных ранее в этой главе тождеств выявляет только одну подходящую кандидатуру, а именно равенство (5.26) из табл. 195. При этом один из способов воспользоваться им состоит в замене параметров соответственно на

На последнем шаге мы изменили порядок суммирования, манипулируя граничными условиями под знаками в соответствии с правилами из гл. 2.

Мы не можем просто так заменить полученную внутреннюю сумму на результат решения задачи поскольку в ней имеется дополнительное условие Но данное дополнительное условие не является излишним, только если т. е. если . А если то первый биномиальный коэффициент внутренней суммы равен нулю, ибо верхний индекс изменяется от 0 до и, таким образом, строго меньше нижнего индекса Следовательно, на внешнюю сумму может быть наложено дополнительное ограничение не оказывающее влияния на то, какие ненулевые члены в нее включены. Тем самым ограничение к становится излишним, и можно воспользоваться решением задачи 6. Полученная двойная сумма распадается на две суммы:

Внутренняя сумма обращается в нуль при всех кроме так что в качестве ответа мы получаем простое выражение в замкнутой форме.

Задача 8: еще одно затруднение

Расширим задачу по-другому, рассмотрев сумму

Если снова получаем сумму, с которой имели дело раньше, но теперь появляется в другом месте. И хотя эта задача немного труднее, чем задача 7, мы (к счастью) уже гораздо лучше освоились с нахождением решений. Начать можно так же, как и в задаче

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

допускающие такое внесение члены. Удача по-прежнему сопутствует нам: в задаче 1 было получено подходящее тождество:

Замена на дает желаемое разложение

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

А согласно (5.24), сумма по всем целым равна нулю. Следовательно, это сумма по

Для вычисления по заменим на и просуммируем по :

Наконец, применяем (5.25) и получаем ответ:

Ну и ну — это надо бы проверить! При находим, что

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