Принцип математической индукции

Принцип математической индукции

Математическая индукция — в математике — один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.

Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино. Пусть какое угодно число косточек домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку (в этом заключается индукционный переход). Тогда, если мы толкнём первую косточку (это база индукции), то все косточки в ряду упадут.

Содержание

Точное описание

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

Допустим, что

  1. Установлено, что P1 верно. (Это утверждение называется базой индукции.)
  2. Для любого n доказано, что если верно Pn, то верно Pn + 1. (Это утверждение называется индукционным переходом.)

Тогда все утверждения нашей последовательности верны.


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

Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:

Пусть имеется последовательность утверждений P_1,P_2, P_3 \ldots. Допустим, что

  1. Установлено, что P1 верно.
  2. Для любого натурального n доказано, что если верны все P_1,P_2, P_3 \ldots P_n, то верно и Pn + 1. (Это утверждение называется индукционным переходом.)

Тогда все утверждения в этой последовательности верны.


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

Примеры

Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство

1 + q + \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},

что и требовалось доказать.

Комментарий: верность утверждения Pn в этом доказательстве — то же, что верность равенства

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

См. также

Вариации и обобщения

Литература


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Принцип математической индукции" в других словарях:

  • Метод математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… …   Википедия

  • ИНДУКЦИИ АКСИОМА — утверждение о справедливости для всех хнек рого предиката Р(х), определенного на множестве всех неотрицательных целых чисел, если выполняются следующие условия: 1) справедливо Р(0),2) для любого х, если верно Р(х), то верно и P(x+1). И. а.… …   Математическая энциклопедия

  • ИНТУИЦИОНИЗМ — (от позднелат. intuitio, от лат. intueor пристально смотрю) направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика …   Философская энциклопедия

  • Трансфинитные числа — (от Транс… и лат. finitus ограниченный)         обобщённые порядковые числа. Определение Т. ч. опирается на понятие вполне упорядоченного множества (см. Упорядоченные и частично упорядоченные множества). Каждое конечное множество можно сделать… …   Большая советская энциклопедия

  • интуиционизм — направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика должна опираться, согласно И., на интуитивное представление …   Словарь терминов логики

  • СОФИЗМ — (греч. sophisma хитрая уловка, измышление) рассуждение, кажущееся правильным, но содержащее скрытую логическую ошибку и служащее для придания видимости истинности ложному утверждению. С. является особым приемом интеллектуального мошенничества,… …   Философская энциклопедия

  • ТОЖДЕСТВА ПРОБЛЕМЫ — проблемы эквивалентности, проблемы иден тичности, проблемы равенства с л о в (англ. word problems) – задачи нахождения общего метода (алгоритма), позволяющего для произвольной пары элементов к. л. множества, в к ром определено отношение типа… …   Философская энциклопедия

  • Софизм — (от греч. sóphisma уловка, ухищрение, выдумка, головоломка)         умозаключение или рассуждение, обосновывающее какую нибудь заведомую нелепость, абсурд или парадоксальное утверждение, противоречащее общепринятым представлениям. Аристотель… …   Большая советская энциклопедия

  • Трансфинитная индукция —         способ математических доказательств, обобщающий обычный принцип математической индукции (См. Математическая индукция). См. Трансфинитные числа …   Большая советская энциклопедия

  • Софизм — (от греч. σόφισμα, «мастерство, умение, хитрая выдумка, уловка, мудрость»)  ложное высказывание, которое, тем не менее, при поверхностном рассмотрении кажется правильным. Софизм основан на преднамеренном, сознательном нарушении правил логики …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»