Математика, яка пов’язує те, куди ми йдемо, і те, де ми були | Журнал Quanta

Скажімо, ви на вечірці з дев’ятьма іншими людьми, і кожен потисне кожному руку рівно один раз. Скільки відбувається рукостискань?

Це «проблема рукостискання», і це одна з моїх улюблених. Мені, як учителю математики, це подобається, тому що існує так багато різних способів, якими можна прийти до рішення, а різноманітність і взаємозв’язок цих стратегій чудово ілюструє силу творчого мислення в математиці.

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

Існує також зовсім інший спосіб вирішення проблеми. Уявіть, що гості приходять по черзі, а коли приходять, то тиснуть руки всім присутнім. У першої особи немає рукостискань, тому в вечірці з однією особою нуль рукостискань. Тепер приходить другий і тисне руку першому. Це додає одне рукостискання до загальної кількості, тож у вечірці з двох осіб загальна кількість рукостискань становить 0 + 1 = 1. Коли третя особа приходить і тисне руку першим двом гостям, це додає два рукостискання до загальної кількості. Прихід четвертої особи додає до загальної кількості три рукостискання і так далі.

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

Як ми побачимо нижче, рекурсія є гнучкою та потужною основою для роздумів про широкий спектр математичних ідей. І хоча стародавнім індійським вченим, таким як Гемачандра, приписують знання про ці послідовності ще в 1150 році, вони все ще пропонують інтригуючі виклики для математиків сьогодні.

Давайте подивимося, як рекурсивне мислення допомагає вирішити проблему рукостискання. Якщо $latex a_n$ дорівнює кількості рукостискань у an n-партія особи, ми можемо представити це рекурсивне відношення за такою формулою:

$латекс 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$

$latex cdots$

$латекс 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многокутник із двостороннім боком — це $латекс (n-2), помножений на 180^{circ}$. Один із способів довести цей результат - почати з an n-gon і уявіть, що станеться, якщо ви видалите трикутник.

Видалення трикутника перетворює n-увійти в (n − 1)-кутник, а також вилучає 180 градусів внутрішнього кута. Це рекурсивне співвідношення: сума внутрішніх кутів для an n-gon на 180 градусів більше, ніж сума внутрішніх кутів для (n − 1)-кутник. Щоб визначити загальний результат, продовжуйте видаляти трикутники, доки не досягнете початкового значення, яке в цій ситуації відбувається, коли ви видаляєте всі трикутники, крім трьох n-вершини гона. У цій точці початковий багатокутник було зведено до трикутника, сума внутрішніх кутів якого, як відомо, дорівнює 180 градусам. Тепер поверніться назад, додаючи 180 градусів на кожному кроці, і ви отримаєте формулу.

Повертаючись до нашої вечірки, проблема рукостискання сама по собі показує нам, що можливо, коли ми мислимо творчо, а потім об’єднуємо ці численні різні точки зору на проблему. Якщо ми пограємо з рекурсивною моделлю нашої послідовності рукостискань:

$латекс a_1 = 0$

$latex 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 cdots$

$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$
$latex a_n = a_{n-1} – a_{n-2}$