Математична індукція , вельми загальний спосіб математичних доказів і визначень. Індуктивні докази засновані на так званому принципі М. і., що є одній з основних математичних аксіом. Хай, наприклад, потрібно довести для будь-якого натурального (цілого позитивного) числа n формулу:
1 + 3 + 5 + ... + (2 n - 1) = n 2 (1)
При n = 1 ця формула дає 1 = 1 2 . Щоб довести правильність формули при будь-якому n , допускають, що її вже удалося довести для деякого певного числа N , тобто передбачають, що
1 + 3 + 5 + ... + (2 N - 1) = N 2 . (2)
Далі, спираючись на зроблене допущення, намагаються довести правильність формули (1) для числа на одиницю більшого, то є для n = N + 1. В даному випадку досить приєднати до суми в лівій частині рівності (2) ще один доданок: (2 N + 1); тоді і права частина рівності повинна збільшитися на (2 N +1) і, отже,
1 + 3 + 5 + ... + (2 N — 1) + (2 N + 1) = N 2 + (2 N + 1) = ( N + 1) 2 .
Але той же результат вийде, якщо у формулі (1) замінити n на N + 1.
Отже, із справедливості формули (1) при n = N витікає (як би не було N ) її правильність і при n = N + 1. Але при n = 1 формула (1) вірна, отже, вона вірна також і при n = 2 = 1 + 1, 3 = 2 + 1, 4 = 3 + 1, 5 = 4 + 1 і так далі. Оскільки послідовним збільшенням одиниці можна отримати (починаючи з одиниці) будь-яке натуральне число, то формула (1) дійсно вірна при будь-якому натуральному числі n . Як ні очевидна завершальна частина приведеного міркування, вона спирається на деяку аксіому, що не зводиться лише до загальних законів логіки, але що виражає одна з основних властивостей натуральних чисел. Загальне формулювання цієї аксіоми таке.
Принцип М. і. Хай: 1) число одиниця володіє властивістю А ; 2) з того, що яке-небудь натуральне число n володіє властивістю А , витікає, що і число n + 1 володіє свойством А . За таких умов будь-яке натуральне число володіє властивістю А .
В розібраному вище прикладі свойство А числа n виражається так: «для числа n справедлива рівність (1)». Якщо принцип М. і. прийнятий як аксіома, то кожен окремий доказ що спирається на цей принцип, слід розглядати як чисто дедуктивне. При доказі [наприклад, формули (1)], заснованому на цьому принципі, не відбувається висновку від приватного до загального, оскільки одна з посилок (сам принцип М. і.) щонайменше настільки ж обща, як і висновок.
Принцип М. і., сформульований вище, служить, як було показано, для доказу математичних теорем. Окрім цього, в математиці уживаються ще так звані індуктивні визначення. Таке, наприклад, наступне визначення членів u n геометричної прогресії з першим членом а і знаменником q :
1) u 1 = а ,
2) u n+1 = u n q .
Умови 1) і 2) однозначно визначають члени прогресії u n для всіх натуральних чисел n . Доказ того, що це дійсно так, може бути засновано на принципі М. і.; в даному випадку можна, проте, безпосередньо отримати вираження u n через n :
u n = aq n-1 .
Принцип М. і. можна замінити рівносильними йому пропозиціями, наприклад таким: якщо підмножина М-коду безлічі всіх натуральних чисел N містить 1 і разом з будь-яким своїм елементом m містить і m + 1, то М-код = N .
