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

2.5 ОБЩИЕ МЕТОДЫ СУММИРОВАНИЯ

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

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

Но вначале, как обычно, понаблюдаем некоторые крайние случаи:

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

Метод 0: с помощью справочника

Проблема типа суммы первых квадратов, несомненно, уже кем-нибудь решена, так что весьма вероятно, что ее решение можно найти в любом имеющемся под рукой справочнике. И в самом деле, на странице Стандартных математических таблиц содержится такой ответ:

Исключительно с целью проверки правильности прочтения убедимся в том, что эта формула верна: Между прочим, на той же 36-й странице таблиц содержится дальнейшая информация, о суммах третьих, десятых степеней.

Авторитетным собранием математических формул служит Справочник по специальными функциям [2] под редакцией Абрамовича и Стиган. На сс. 616-617 этой книги приведены значения для всех а на сс. 608 и 612 представлены формулы, эквивалентные (2.38), вместе с аналогичными формулами для сумм третьих, пятнадцатых степеней (с переменой или без перемены знаков).

Но наилучшим источником ответов на вопросы о последовательностях остается изумительная небольшая книжка Слоана под названием Справочник по целочисленным последовательностям [276], в которой перечислены тысячи последовательностей в соответствии с их числовыми значениями. Если вы сталкиваетесь с некоторой рекуррентностью, которую есть основание считать уже изученной, все, что нужно сделать, - это вычислить достаточное число членов для того, чтобы распознать вашу рекуррентность среди других известных; тогда у вас появятся шансы найти указание на соответствующую литературу в справочнике Слоана. Так, выясняется, что Слоана имеет номер 1574 и называется последовательностью „квадратных пирамидальных чисел“ (ибо в пирамиде с квадратным основанием из шаров умещается Пп шаров). Слоан отсылает нас к трем источникам, одним из которых служит уже упоминавшийся справочник Абрамовича и Стиган.

Еще один способ почерпнуть из кладезя мировой математической мудрости — использование компьютерных программ (таких, как MACSYMA, Axiom, Maple или Mathematica), дающих средства для символьных преобразований. Такие программы особенно ценны, когда приходится иметь дело с громоздкими формулами.

Знакомство со стандартными источниками информации небесполезно, ибо они могут оказаться исключительно полезными. Тем не менее, метод 0 не вполне согласуется с духом этой книги, поскольку нам хотелось бы знать, как угадать ответ самостоятельно. „Справочный" метод ограничивает нас задачами, которые кто-то счел заслуживающими внимания — интересующую нас задачу среди них можно и не найти.

Метод, 1: угадывание ответа с подтверждением по индукции

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

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

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

„Итак, Ваша честь, нам известно, что так что с базой индукции просто. Для индуктивного перехода предположим, что и допустим, что (2.39) остается в силе, когда заменяется на Поскольку

то

Таким образом, формула (2.39) действительно справедлива при всех вне всякого сомнения. Господа присяжные, нет возражений?

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

Метод 2: метод, приведения

Итак, давайте вернемся к методу приведения, который так хорошо проявил себя в случае геометрической прогрессии (2.25). Выделим первый и последний члены для того чтобы получить уравнение относительно :

Оп-па! Величины Пп взаимно уничтожаются. Случается, что, несмотря на все наши старания, метод приведения приводит к чему-то вроде и мы остаемся в проигрыше.

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

хотя мы и рассчитывали вычислить сумму их квадратов. А не может случиться так, что, начав с суммы кубов целых чисел, которую можно обозначить через мы получим выражение для суммы их квадратов? Давайте попробуем:

Как мы и ожидали, величины уничтожаются, и мы можем определить не полагаясь на индукцию:

Метод 3: подбор репертуара

Для суммирования квадратов достаточно также немного обобщить рекуррентное соотношение (2.7). Решение рекуррентности

вообще будет иметь вид

и мы уже определили поскольку (2.40) — то же самое, что и (2.7), когда . Если теперь подставить то выясняется, что будет решением при Итак,

откуда определяется

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

Метод 4: замена сумм интегралами

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

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

интервале от 0 до

А так как площадь под этой кривой есть мы выясняем, что величина приближенно равна

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

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

В любом случае можно было бы найти а затем .

Метод 5: усложнение и упрощение

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

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

Метод 6: исчисление конечных разностей

Метод 7: использование производящих функций

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

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