Додаткова тема курсу. Для основного маршруту її можна пропустити. Достатньо квадрата суми й арифметичної послідовності.
Плитками можна скласти квадрат: 1, потім додати 3, потім 5. Математична індукція доводить твердження для всіх натуральних кроків через перший випадок і надійний перехід до наступного. Сто перевірених прикладів такого переходу не замінюють.
Що саме доводимо
Натуральними тут називаємо цілі n≥1. Твердження P(n) таке:
1 + 3 + ⋯ + (2n − 1) = (n)^(2) (n = 1,2,3,…).
Це сума перших n непарних чисел; останній доданок 2n−1. Для n=3: 1+3+5=9.
База: є звідки почати
При n=1 ліва частина 1, права 1²=1. Отже, P(1) істинне. Без бази ланцюг міг би не мати жодної підтвердженої ланки.
Припущення: один довільний крок
Візьмемо довільне ціле k≥1 і припустимо P(k):
1 + 3 + ⋯ + (2k − 1) = (k)^(2).
Не стверджуємо наперед, що формула вже істинна для всіх k. Доводимо умовний зв’язок: якщо вона істинна на цьому кроці, то істинна на наступному.
Перехід: додаємо наступне непарне
Після 2k−1 наступним є 2k+1. За припущенням замінюємо попередню суму на k², а тоді застосовуємо квадрат суми:
1 + 3 + ⋯ + (2k − 1) + (2k + 1) = (k)^(2) + 2k + 1 = ((k + 1))^(2).
Це саме P(k+1). Обчислення працює для будь-якого k≥1. База й перехід за принципом індукції дають P(n) для всіх n≥1. Формулювання принципу й обґрунтування, MIT, с. 3.
Від 3² до 4²
Картинка показує 3²+7=4²: новий край має 3+3+1 плиток. Вона допомагає зрозуміти доданок 2k+1, а загальність доводить наведений перехід із довільним k.
Як зламати «доведення»
Хибне твердження: «усі додатні цілі непарні». База 1 непарне. Якщо k непарне, то k+2 теж непарне. Чому це не доведення? Перехід перескакує через числа: від бази досягаємо 1,3,5,…, але ніколи 2. Число 2 — контрприклад.
Для послідовного маршруту потрібен саме крок k→k+1. Крок +2 може довести твердження для всіх цілих лише з окремими відповідними базами для обох парностей, а тут база 2 уже хибна. Також не можна під час переходу використовувати P(k+1) як відомий факт: це було б колом у доведенні.
Перевірка готового доведення коротка: чітка область n, база в цій області, одне припущення P(k), перехід до наступного кроку без додаткових недоведених умов і висновок за індукцією.