Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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


Dominoeffect.png

План:


Введення

Dominoeffect.png

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

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


1. Формулювання

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

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

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

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


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


1.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 . Принцип повної математичної індукції є прямим застосуванням сильнішою трансфінітних індукції.

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


2. Історія

Усвідомлення методу математичної індукції як окремого важливого методу сходить до Блезу Паскалю і Герсоніду, хоча окремі випадки застосування зустрічаються ще в античні часи у Прокла і Евкліда [1]. Сучасна назва методу було введено де Морганом в 1838.

3. Приклади

Завдання. Довести, що, які б не були натуральне 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} =
,

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

Коментар: вірність твердження P n в цьому доказі - те саме, що вірність рівності

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

4. Варіації і узагальнення


Примітки

  1. Nachum L. Rabinovih Рабі Леві бен Гершем і походження методу математичної індукції = Rabbi Levi ben Gershom and the origins of mathematical induction / / Archive for History of Exact Sciences. - 1970. - В. 6. - С. 237-248.

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Індукція
Магнітна індукція
Електростатична індукція
Магнітна індукція
Математична біологія
Математична фізика
Математична олімпіада
Математична структура
Математична логіка
© Усі права захищені
написати до нас
Рейтинг@Mail.ru