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

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

Одно из решений выглядит следующим образом: начните с того, что каждый человек пожимает руку другому человеку. Десять человек, по девять рукопожатий каждый, производят 9 × 10 = 90 рукопожатий. Но при этом каждое рукопожатие учитывается дважды — по одному разу с точки зрения каждого шейкера — поэтому фактическое количество рукопожатий равно $latex frac{90}{2} = 45$. Простой и красивый аргумент в пользу победы!

Есть и совершенно другой способ решения проблемы. Представьте, что гости приходят по одному и, придя, пожимают руки всем присутствующим. У первого человека нет рук, которые он мог бы пожать, поэтому в группе из одного человека общее количество рукопожатий нулевое. Теперь подходит второй человек и пожимает руку первому. Это добавляет одно рукопожатие к общему количеству, поэтому в группе из двух человек общее количество рукопожатий составляет 0 + 1 = 1. Когда третий человек приходит и пожимает руку первым двум гостям, это добавляет к общему числу два рукопожатия. Прибытие четвертого человека добавляет к общей сумме три рукопожатия и так далее.

Эта стратегия моделирует последовательность рукопожатий рекурсивно, то есть каждый термин в последовательности определяется относительно тех, которые предшествуют ему. Вы, вероятно, знакомы с последовательностью Фибоначчи, самой известной рекурсивной последовательностью из всех. Он начинается с 1, 1, 2, 3, 5, 8, 13, 21 и продолжается с каждым последующим членом, равным сумме двух предыдущих.

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

Давайте посмотрим, как рекурсивное мышление помогает решить проблему рукопожатия. Если мы позволим $latex a_n$ равняться количеству рукопожатий в n-person party, мы можем представить эту рекурсивную связь следующей формулой:

$латекс a_n = a_{n-1} + n–1$

Это говорит нам о том, что количество рукопожатий за n-person party ($latex a_n$) равна количеству рукопожатий в (n − 1)-персона ($latex a_{n-1}$) плюс n − Еще 1 рукопожатие, отражающее идею о том, что когда приходит новый человек, они добавляют определенное количество новых рукопожатий к уже состоявшимся.

В нашей конкретной версии задачи о рукопожатии мы хотим знать $latex a_{10}$, количество рукопожатий на вечеринке из 10 человек, чтобы обнаружить, что мы используем рекурсивное отношение

$латекс a_{10} = a_9 + 9$

Чтобы найти значение $latex a_{10}$, нам просто нужно знать значение $latex a_9$ и прибавить к нему 9. Как нам найти значение $latex a_9$? Конечно же, используя рекурсию!

$латекс a_9 = a_8 + 8$

Теперь, чтобы найти значение $latex a_8$, нам нужно найти значение $latex a_7$, для чего необходимо знать $latex a_6$ и так далее. На данный момент вы можете волноваться, что это будет продолжаться вечно в своего рода бесконечном спуске, но как только мы достигнем $latex a_1$, все будет готово, потому что мы знаем, что на вечеринке из одного человека общее количество рукопожатий нулевое.

$латекс a_1 = 0$

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

$латекс a_1 = 0$

$латекс a_2 = a_1 + 1 = 0 + 1 = 1$

$латекс a_3 = a_2 + 2 = 1 + 2 = 3$

$латекс a_4 = a_3 + 3 = 3 + 3 = 6$

$латексные точки$

$латекс a_{10} = a_9 + 9 = 36 + 9 = 45$

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

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

В частности, рекурсия полезна, потому что она повсюду в математике. Оно возникает, например, в линейных отношениях, о которых все узнают на уроках математики, — тех, которые характеризуются постоянной скоростью изменения и представляются линиями на плоскости. Линейную функцию, такую ​​как $latex f(x) = 3x + 5$, можно рассматривать как рекурсивную формулу:

$латекс a_0 = 5$

$латекс a_n = a_{n-1} + 3$

Хотя более очевидный способ представить $latex f(2)$ состоит в том, что $latex f(2) = 3×2 + 5 = 11$, другой способ состоит в том, что $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Рекурсивное моделирование фундаментальной характеристики линейных функций — постоянной скорости изменения — дает нам другой способ подумать об этой взаимосвязи. То же самое можно сделать и с показательными функциями, характеризующимися постоянным мультипликативным изменением.

Рекурсивное мышление работает и за пределами последовательностей чисел. Если вы когда-либо решали систему уравнений, вы, вероятно, применяли рекурсивный подход. Чтобы решить систему

$латекс 2x + y = 10$

$латекс 3x – y = 5$

вы можете сначала сложить два уравнения вместе, чтобы исключить y переменная, что приводит к уравнению $latex 5x = 15$. Решите это, чтобы получить $latex x =$ 3, подставьте его и найдите $latex y = 4$, и все готово. В этом подходе используется рекурсивный алгоритм, в котором решение системы строится на основе решения более мелких связанных систем. Например, чтобы решить систему 3×3, вы исключаете одну переменную, чтобы превратить ее в систему 2×2, а затем еще раз, чтобы превратить ее в систему 1×1. Это простое для решения единственное уравнение похоже на начальное значение этого рекурсивного процесса. Это сигнализирует об окончании обратного поиска, и оттуда вы продолжаете двигаться вверх по цепочке уравнений, как в рекурсивной последовательности.

Существуют даже методы рекурсивного доказательства. Например, известная формула геометрии — это формула суммы углов многоугольника, которая гласит, что сумма мер внутренних углов многоугольника nОдносторонний многоугольник равен $latex (n-2) умноженному на 180^{circ}$. Один из способов доказать этот результат — начать с n-gon и представьте, что произойдет, если вы удалите треугольник.

Удаление треугольника превращает n-гон в (n − 1)-угольник, а также удаляет 180 градусов меры внутреннего угла. Это рекурсивная зависимость: сумма внутренних углов для n-gon на 180 градусов больше, чем сумма внутренних углов для (n − 1)-гон. Чтобы получить общий результат, продолжайте удалять треугольники, пока не достигнете начального значения, что в этой ситуации происходит, когда вы удалили все треугольники, кроме трех. n-вершины угольника. На этом этапе исходный многоугольник превратился в треугольник, сумма внутренних углов которого, как известно, равна 180 градусам. Теперь вернитесь назад, прибавляя 180 градусов на каждом этапе, и вы получите формулу.

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

$латекс a_1 = 0$

$латекс a_n = a_{n-1} + n – 1$

получается красивая закономерность:

$латекс a_2 = a_1 + 1 = 0 + 1$

$латекс a_3 = a_2 + 2 = 0 + 1 + 2$

$латекс a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$латексные точки$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Теперь у нас есть новый и общий подход к проблеме: количество рукопожатий в n-человека партия равна сумме первых n − 1 положительное целое число.

Вспомните наш первоначальный подход. В n- вечеринка, каждый человек пожимает друг другу руки n − 1 человек. Продукт $latex n (n-1)$ считает каждое рукопожатие дважды, поэтому общее количество рукопожатий равно $latex frac{n(n-1)}{2}$. Но поскольку наши разные методы рассчитывают одно и то же, они должны давать один и тот же результат. В частности, это означает:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Соединив разные подходы к проблеме рукопожатия, получаем замкнутую формулу суммы первых n − 1 положительное целое число. Но мы получаем даже больше: выражение $latex frac{n(n-1)}{2}$ включает в себя дробь, но поскольку она равна сумме целых чисел, она тоже должна быть целым числом. Это доказывает простой факт теории чисел: для каждого целого числа n, $latex frac{n(n-1)}{2}$ — целое число.

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

Упражнения

1. Найдите замкнутую формулу для последовательности, которая определяется рекурсивно как
$латекс a_1 = 1$
$латекс a_n = a_{n-1} + 2n – 1$

2. В конце столбца было показано, что выражение $latex frac{n(n-1)}{2}$ является целым числом, даже несмотря на то, что выражение содержит дробь, поскольку $latex frac{n(n-1) )}{2}$ — это результат подсчета чего-либо. Существует также аргумент теории чисел, который показывает, что это выражение должно быть целым числом. Что это такое?

3. Найдите первые несколько членов рекурсивной последовательности.
$латекс a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Найдите первые несколько членов рекурсивной последовательности.
$латекс a_1 = 1$
$латекс a_2 = 1$
$латекс a_n = a_{n-1} – a_{n-2}$