Математична індукція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Dominoeffect.png

Математи́чна інду́кція — застосування принципу індукції для доведення теорем в математиці. Зазвичай полягає в доведенні правильності твердження стосовно одного з натуральних чисел, а потім всіх наступних.

Принцип індукції полягає в тому, що нескінченна послідовність тверджень P_i, i = 1, \dots, \infty, правильна якщо:

  1. P_1 — правильне, та
  2. із правильності P_k випливає правильність (істинність) P_{k+1} для всіх k.

Індуктивне доведення наочно може бути представлене у вигляді т.зв. принципу доміно. Нехай довільне число кісточок доміно виставлено в ряд таким чином, що кожна кісточка, падаючи, обов'язково перекине наступну за нею кісточку (це індукційний перехід). Тоді, якщо ми штовхнемо першу кісточку (це база індукції), то всі кісточки в ряду впадуть.

На практиці використовується, щоб довести істинність певного твердження для всіх натуральних чисел. Для цього спочатку перевіряється істинність твердження за номером 1 - база (базис) індукції, а потім доводиться, що, якщо правдиве твердження з номером n, то правдиве й наступне твердження за номером n + 1 - крок індукції, або індукційний перехід.

Формулювання[ред.ред. код]

Припустимо, що потрібно встановити справедливість безкінечною послідовності тверджень, занумерованих натуральними числами: P_1, P_2, \ldots, P_n, P_{n+1}, \ldots.

Припустимо, що

  1. Встановлено, що  P_1 правильне. (Це твердження називається базою індукції.)
  2. Для будь-якого n доведено, що якщо вірно  P_n , то вірно  P_{n+1}. (Це твердження називається індукційним переходом.)

Тоді всі твердження нашої послідовності вірні.

Логічною підставою для цього методу докази слугує так звана аксіома індукції, п'ята з аксіом Пеано, що визначають натуральні числа. Правильність методу індукції еквівалентна тому, що в будь-якій непорожній підмножині натуральних чисел існує мінімальний елемент.

Принцип повної математичної індукції[ред.ред. код]

Існує також варіація, так званий принцип повної математичної індукції. Ось його суворе формулювання:

Нехай є послідовність тверджень P_1, P_2, P_3, \ldots. Якщо для будь-якого натурального  n з того, що істинні всіP_1, P_2, P_3, \ldots, P_{n-1}, слід також істинність P_n, то всі твердження в цій послідовності істинні, тобто (\forall n\in{\mathbb N})\Big((\forall i\in\{1;\dots;n-1\})P_i\longrightarrow P_n\Big)\longrightarrow(\forall n\in{\mathbb N})P_n.

У цій варіації база індукції виявляється зайвою, оскільки є тривіальним окремим випадком індукційного переходу. Дійсно, при n=1 імплікація (\forall i\in\{1;\dots;n-1\})P_i\longrightarrow P_n еквівалентна P_1. Принцип повної математичної індукції є прямим застосуванням більш сильною трансфінітної індукції.

Принцип повної математичної індукції також еквівалентний аксіомі індукції в аксіомах Пеано.

Історія[ред.ред. код]

Усвідомлення методу математичної індукції окремим методом походить від Блеза Паскаля і Герсоніда, хоча окремі випадки використання цього методу відомі ще в Платона (Діалог Парменід — можливо, міститься на початку приклад неявного індуктивного доведення), Прокла і Евкліда. Сучасну назву методу запровадив британський математико Ауґустус де Морган у 1838 році.

Приклади[ред.ред. код]

Задача. Довести, що, якими б не були натуральне n і дійсне q ≠ 1, справджується рівність

1 + q + q^2 +\cdots + q^n = \frac{1 - q^{n + 1}}{1  -q}.

Доведення. Індукція по n.

База, n = 1:

1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}.

Перехід: припустимо, що

1 + q + \cdots + q^n=\frac{1- q^{n + 1}}{1 - q},

тоді

1+q+\cdots +q^n+q^{n+1}=\frac{1-q^{n+1}}{1-q}+q^{n+1}=
=\frac{1-q^{n+1}+(1-q)q^{n+1}}{1-q}=\frac{1-q^{n+1}+q^{n+1}-q^{(n+1)+1}}{1-q}=\frac{1-q^{(n+1)+1}}{1-q},

що й потрібно було довести.

Коментар: істинність тверджения P_n в цьому доведенні — то саме, що й істинність рівності

1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}.

Варіації та узагальнення[ред.ред. код]

Джерела[ред.ред. код]

  • Weisstein, Eric W. (1999). CRC concise encyclopedia of mathematics. Boca Raton, Fla.: CRC Press. ISBN 0-8493-9640-9. 

Література[ред.ред. код]

Відеоматеріали[ред.ред. код]

Див. також[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.