Несколько подходов к суммированию

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

Посмотрите на серию фигур из точек:

Назовём эти фигуры гексами (hex значит шесть). Первый гекс состоит из одной точки, второй — из семи точек; каждый следующий гекс получается из предыдущего добавлением одного слоя точек.

Вопрос: сколько всего точек на первых n гексах?

Сосчитаем ответ при малых : на первых двух гексах точек, на третьем -, поэтому на первых трёх - . Заметим, что и . Хм... Просто совпадение? Посмотрим, сколько точек на 4-м гексе. На его внешнем слое будет $6\cdot 3=18$ точек. Плюс внутри него расположен третий гекс из 19 точек. Итого, точек. Значит, всего на первых четырёх гексах точки. А - закономерность подтверждается. Правда ли, что на первых гексах всегда точек? Выведем это несколькими методами.

I МЕТОД: ИНДУКЦИЯ. При утверждение верно (база). Предположим, что на первых гексах ровно точек, и докажем, что на первых гексах ровно точек. Это равносильно тому, что число точек на -м гексе равно

$n^3-(n-1)^3=3n^2-3n+1. \;\;\;\;\;\;\; (1)$

Чтобы в этом убедиться, разобьём -й гекс на "концентрических" слоёв: первый слой - центр из одной точки, на втором слое 6 точек, на третьем - $6\cdot 2$ , $\ldots,$ на -м - . Итого, число точек на -м гексе равно

$1+6(1+2+\ldots+n-1)=1+6\cdot \dfrac{n(n-1)}{2}=3n^2-3n+1,$

что и требовалось.

II МЕТОД: СУММИРОВАНИЕ. Рассуждать по индукции можно, когда у нас уже есть гипотеза, какой будет ответ. Допустим, у нас такой гипотезы (про ) не было. Тогда мы бы просто сосчитали, сколько точек на -м гексе (как выше), и просуммировали по $k=1,\ldots,n$ :

$\sum_{k=1}^n (3k^2-3k+1)=3\sum_{k=1}^n k^2-3\sum_{k=1}^n k + n. \;\;\;\;\;\;\; (2)$

Формулу для суммы квадратов можно найти в справочнике:

$1^2+2^2+\ldots+n^2=\dfrac{n(n+1)(2n+1)}{6}. \;\;\;\;\;\;\; (3)$

Подставив эти выражения в вычисляемую сумму, после преобразований получим . Но было бы здорово всё-таки пролить свет на формулу для суммы квадратов. Оказывается, концептуальный путь начинается с формулы (1). Проведём вывод формулы (3) в духе одной из главных теорем анализа - формулы Ньютона-Лейбница:

$\int_a^b F'(x)dx=F(b)-F(a).$

Её дискретный аналог тривиален. Интегрирование заменяем на суммирование, а производную --- на разность. Именно, для любой последовательности $a_1,\ldots,a_n$ имеем:

$(a_n-a_{n-1})+(a_{n-1}-a_{n-2})+\ldots+(a_3-a_2)+(a_2-a_1)=a_n-a_1.$

Применим эту нехитрую идею к последовательности :

$\begin{align*} n^3-(n-1)^3=3n^2-3n+1,\\ \ldots\ \\ 2^3-1^3=3 * 2^2-3 * 2+1,\\ 1^3-0^3=3 * 1^3-3 * 1+1. \end{align*}$

Сложив числа в левой части, получим (остальные члены сократятся, а ).

В правой же части получим не что иное, как (2). Мы решили задачу о гексах, а заодно из неё вывели формулу (3): зная, что выражение (2) равно , легко выразить из него

$\sum_{k=1}^{n} k^2$ .

III МЕТОД: ГЕОМЕТРИЧЕСКИЙ. В качестве "вишенки на торте" покажем геометрическую интерпретацию сказанного выше. Третья степень неслучайно называется кубом, подобно тому, как вторая степень называется квадратом. Так, формула суммы первых нечётных натуральных чисел

$1+3+5+\ldots+(2n-1)=n^2$

имеет простой геометрический смысл: вкладывая уголки

из 1, 3, 5, ... точек друг в друга как матрёшки, сложим квадрат. Оказывается, нечто аналогичное происходит и с гексами! Взгляните:

Таким образом, -й гекс можно воспринимать как видимую часть поверхности куба $n\times n\times n$ под соответствующим углом зрения. Например, на втором гексе вы видите куб без одной вершины - её не видно, и можно считать, что это как раз точка на первом гексе. Вообще, все эти слоёв вкладываются друг в друга, образуя полный куб с ребром из точек.

Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер

Источник: https://habr.com/ru/articles/741634/

Вернуться к списку

Интересные статьи

F+ Flaptop R — несколько мощных ноутбуков на AMD Ryzen

Привет, Хабр! Мы продолжаем разговаривать об альтернативных брендах ноутбуков, которые доступны в России. И сегодня речь пойдет о мобильных ПК от компании F+, которые в отличие от предыдущих героев на...

Как построить большое мобильное приложение в проекте… который был уже несколько раз потрачен до тебя

Привет, Хабр! В этой серии статей я хотел бы поделиться опытом создания большой команды мобильной разработки и самих мобильных приложений в одной крупной финансовой организации, об архитектуре, приним...

Как построить мощного скоростного робота-шагохода? Несколько мыслей на тему…

Источник картинки: linuxgizmos.com Перемещение по земной поверхности с использованием шагающего принципа является своего рода «Священным Граалем» робототехники. В разные времена множество изобретат...

«Все на панель!» или несколько полезных приемов настройки панелей Xwiki

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

Как использовать несколько языков программирования и не сойти с ума

Привет, Хабр! Представляю вашему вниманию перевод статьи «How to use multiple programming languages without losing your mind» автора Bart Copeland. Сопливое нытьё про FSF и Red HatКароч, тема ...