По индукции доказательство: Метод математической индукции – Метод математической индукции. Видеоурок. Алгебра 9 Класс — Детская игровая комната «Волшебный лес»

Posted on 02.09.202001.02.2020 by alexxlab

Содержание

§ 9. Различные виды доказательств по индукции Усиленный принцип полной математической индукции

Докажем принцип полной математической индукции, в котором делается более сильное индуктивное предположение.

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

Т(п) верно для п=1,m.e. Т(1) истинно;

каково бы ни было натуральное число т, из предположения о том, что Т(п) истинно для всех п < т, следует, что оно верно и для т, т. е. Т (т) истинно.

Доказательство от противного. Предположим, что Т(п) верно не для всякого натурального числа. Тогда множество А всех натуральных чисел, для которых

Т(п) не верно, не пусто и имеет наименьший элемент, который обозначим через т. По условию 1) т≠1, следовательно, существуют натуральные числа, меньшие т. Так как т — наименьший элемент в А, то все натуральные числа, меньшие т, уже А не принадлежат, а значит, для них утверждение T(n) верно. Но тогда по условию 2) оно должно быть верно и для т — пришли к противоречию. Остается принять, что А = 0. Но это означает, что Т(п) верно для любого натурального числа.

Обобщенный принцип полной математической индукции

Иногда истинность утверждения Т(п) нужно доказать для всех натуральных чисел, начиная с некоторого натурального числа а. Тогда используется следующая теорема.

Теорема 2. (обобщенный принцип полной математической индукции). Пусть а N. Предложение Т(п) верно для любого натурального числа п

≥ а, если выполнены следующие условия:

1) предложение Т(п) верно для п=а, т.е. Т(а) истинно;

2) каково бы ни было натуральное число п > а, из предположения о том, что Т(п) истинно, следует, что Т(п’) истинно.

Доказательство. Обозначим через М множество, содержащее все натуральные числа, меньшие а, и все n, для которых Т(п) истинно. Пользуясь принципом полной математической индукции, докажем, что п М для любого пN. По условию 1) а М, а так как 1 ≤ а, то 1 М. Пусть п

М, тогда либо п < а, либо Т(п) истинно. В первом случае п’ ≤ а, откуда п’

М, а во втором — по условию 2) п’

М. Таким образом, М = N. Отсюда следует истинность Т(п) для любого n ≥ а.

Обобщенный усиленный принцип полной математической индукции

Докажем принцип полной математической индукции, который соединяет в себе черты усиленного и обобщенного принципов.

Теорема 3. Пусть а N. Предложение Т(п) верно для любого натурального числа п ≥ а, если выполнены следующие условия:

предложение Т(п) верно для п = а, т.е. Т (а) истинно;
каково бы ни было натуральное число т ≥ а, из предположения о том, что Т(п) истинно для всех натуральных п таких, что а≤п<т, следует истинность T(m).

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

§ 10. Вычитание и деление натуральных чисел

Вычитание

Теорема 1. Сумма любых двух натуральных чисел больше каждого из слагаемых (или каждое слагаемое меньше суммы).

Доказательство. Пусть х и у — любые натуральные числа, x + y = z — натуральное число, их сумма: она существует и определена слагаемыми однозначно. Отсюда, по определению знака > и следует теорема:

z = x + y > x, z = x + y > y Ч. т. д.

Следствие 1. Если натуральное число z меньше или равно натуральному числу y, z ≤ y, то не существует такого натурального числа х, для которого x + y = z.

Следствие 2. Если натуральное число z больше натурального числа y, z > y, то существует такое натуральное число х, для которого x + y = z.

Доказательство. Если z > y, то z = y + u, где и — требуемое натуральное число х. Ч. т. д.

Определение 1. Натуральное число х, удовлетворяющее равенству

x + y = z, называется разностью натуральных чисел z и у и обозначается z — y = x, (z — уменьшаемое, у — вычитаемое), а действие, которое дает разность, называется вычитанием.

Вычитание обратно сложению, так как представляет нахождение одного из слагаемых, когда известны сумма и второе слагаемое. Так как сложение коммутативно, то безразлично, какое из слагаемых — первое или второе — неизвестно.

Теорема 2. Если и z — натуральные числа, то для существования разности z – у необходимо и достаточно, чтобы выполнялось неравенство z > y .

Доказательство. Если существует разность z – у = x, то это значит, что x + y = z и z > y. И наоборот, если z > y, то z =

y + x, где х — натуральное число, т. е. разность z – у = x существует. Ч. т. д.

Следствие. Если существует разность натуральных чисел, то эта разность единственна.

Доказательство. Допустим, что существует разность двух чисел z и у, имеющая два значения х₁ и х₂:

z – у = x₁, z – у = x₂, т.е. x₁ + y = z, x₂ + y = z,

следовательно, x₁ + y = x₂ + y отсюда x₁ = x₂. Ч. т. д.

Деление

Теорема 3. Если х ≠ 1 — натуральное число, то любое натуральное число удовлетворяет неравенству у < ху

(1).

Доказательство. Доказательство проведем индукцией по у, при произвольно выбранном х.

При у = 1, 1 < x∙1 = x и так как х ≠ 1 то это неравенство верно.

Пусть имеет место неравенство y < xy. Докажем, что это неравенство верно для y′: Действительно, ху′ = ху + х > у + х > y+1 = y′, т. е. y′< ху′.

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

Теорема 4. Если натуральное число х меньше натурального числа у, х < у, то не существует такого натурального числа

z, что х = yz.

Доказательство. Допустим, что число z существует, т. е. выполняется равенство х = yz, тогда возможны два случая: z = 1 и z ≠ 1. Пусть z = 1 но тогда x = y∙1 = y, что противоречит условию теоремы: x < y.

Пусть теперь z ≠ 1, тогда 1 < z и так как x < y, то x < yz, что противоречит допущению х = yz. Следовательно, не существует натурального числа z такого, что при условии x < y имеет место равенство х = yz. Ч. т. д.

Следствие. Если х и у — натуральные числа, то для того, чтобы, существовало натуральное число

z, удовлетворяющее равенству х = yz, необходимо, чтобы х ≥ y.

Однако это условие не будет достаточным. Например, х=5, у=3, т. е. х > y, но не существует натурального числа z такого, чтобы 3∙z=5.

Определение 2. Натуральное число z, удовлетворяющее равенству между натуральными числами x=yz, называется частным и обозначается: z = x:y = , так что x = y·. Действие по которому находится частное, называется делением, оно обратно умножению.

Теорема 5. Если частное натуральных чисел существует, то оно единственное.

Доказательство. Пусть yz₁ = x и yz₂ = x. Тогда yz₁ = yz₂, отсюда z₁ = z₂. Ч. т. д.

Если частное двух чисел х и у существует, то говорят, что х делится на у.

Итак, вычитание и деление во множестве натуральных чисел выполняется не всегда.

Лекция 1. Метод математической индукции.

Метод математической индукции — это мощное средство для доказательства теорем.

Пусть P(n)  некоторое утверждение (формула, теорема, свойство), которое зависит от натурального n.

Принцип индукции.

Пусть P(n) таково, что P(1)  истинное утверждение;
Из истинности P(k) следует истинность P(k+1) Тогда P(n) – истинно для любого натурального n.

Эквивалентная формулировка принципа индукции:

Пусть P(n) таково, что P(1) – истинно;
Из истинности P(n) для всех n = 1, 2,…, k, следует истинность P(k+1). Тогда P(n) – истинно для любого натурального n.

Доказательство по методу математической индукции проходит в три этапа:

Доказательство истинности P(1).

допускается истинность утверждения P(k) (или P(n) для любого n = 1, 2,…, k).

доказывается истинность утверждения P(k+1), исходя из индуктивного предположения.

Замечание. База индукции не обязательно начинается с n = 1. Она может начинаться с любого натурального , тогда утверждение P(n) верно для любого натурального n, начиная со значения .

Схема доказательства по методу математической индукции такова (для простоты положим, что база индукции начинается с n = 1).

Утверждение P(n) 

истинно для всех

натуральных n!

Пример 1. Доказать при помощи метода математической индукции:

Доказательство.

1). База индукции.

Пусть n = 1, тогда верно равенство

;

2). Индуктивное предположение.

Пусть при n = k верно равенство

;

3). Индуктивный переход.

Пусть n = k + 1, тогда нужно доказать, что

В силу индуктивного предположения

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

Пример 2. Доказать при помощи метода математической индукции, что для любого натурального n.

Доказательство.

1). База индукции.

Пусть n = 1, тогда верно сравнение

2). Индуктивное предположение.

Пусть при n = k верно сравнение

значит

3). Индуктивный переход.

Пусть n = k + 1, тогда нужно доказать, что

В силу индуктивного предположения

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

Пример 3. Доказать при помощи метода математической индукции:

для любого

Доказательство.

1). База индукции.

Пусть n = 5, тогда верно неравенство

т. е. 32 > 25;

2). Индуктивное предположение.

Пусть при n = k верно неравенство

3). Индуктивный переход.

Пусть n = k + 1, тогда нужно доказать, что

. Но

так как если

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

Неравенство Коши-Буняковского.

Теорема 1.

Пусть даны два n-мерных вектора:

где

 вещественные числа.

Скалярным произведением этих векторов называется сумма

Длина вектора вычисляется по формуле

Докажем, что

(1)

Доказательство (1 способ).

Сначала возведём в квадрат неравенство, которое нужно доказать

Проведём доказательство методом математической индукции.

Пусть n = 1, тогда

2. Пусть при n = 1, 2,…, k справедливо неравенство

3. Положим n = k + 1, тогда

С другой стороны

В силу индуктивного предположения

Нужно показать, что справедливо неравенство

+ .

Раскроем скобки и проведём почленное сравнение:

+ ,

так как i = 1, 2,…, k.

Теорема доказана.

Метод математической индукции универсален. Именно поэтому доказательства по нему не всегда самые изящные и короткие из возможных.

Приведем другое доказательство неравенства Коши-Буняковского, которое основано на очевидных свойствах скалярного произведения.

Доказательство (2 способ).

Пусть  любое число, тогда

Очевидно, что

Тогда .

Мы получили квадратный трехчлен относительно , который не принимает отрицательных значений, значит, его дискриминант :

D= 

Теорема доказана.

Пример 4.

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

Решение. Идея доказательства основана на том, что если у правильно раскрашенной плоскости поменять цвета на противоположные, раскраска останется правильной.

При n = 1 плоскость можно правильно раскрасить.
Пусть при n = k плоскость можно правильно раскрасить.
Пусть на плоскости проведены (k + 1) прямых.

Временно удалим произвольную прямую, оставив k прямых: по индуктивному предположению правильная раскраска существует. Теперь добавим удалённую прямую. Эта прямая делит плоскость на две полуплоскости, каждая из которых раскрашена правильно. Нарушения правильности могут быть только на границе с добавленной прямой. Поменяем в любой из полуплоскостей цвета на противоположные, раскраска останется правильной, а нарушения исчезнут.

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

Принцип математической индукции — это… Что такое Принцип математической индукции?

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

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

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

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

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

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

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

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

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

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

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

Установлено, что P₁ верно.
Для любого натурального n доказано, что если верны все $P_1,P_2, P_3 \ldots P_n$ , то верно и P_{n + 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}$

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

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

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

См. также

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

Литература

Н. Я. Виленкин Индукция. Комбинаторика. Пособие для учителей. М., Просвещение, 1976.—48 с
Л. И. Головина, И. М. Яглом Индукция в геометрии, «Популярные лекции по математике», Выпуск 21, Физматгиз 1961.—100 с.
Р. Курант, Г. Роббинс «Что такое математика?» Глава I, § 2.
И. С. Соминский Метод математической индукции. «Популярные лекции по математике», Выпуск 3, Издательство «Наука» 1965.—58 с.

Wikimedia Foundation. 2010.

Принцип локальности
Принцип максимума (уравнение теплопроводности)

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

Метод математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… … Википедия
ИНДУКЦИИ АКСИОМА — утверждение о справедливости для всех хнек рого предиката Р(х), определенного на множестве всех неотрицательных целых чисел, если выполняются следующие условия: 1) справедливо Р(0),2) для любого х, если верно Р(х), то верно и P(x+1). И. а.… … Математическая энциклопедия
ИНТУИЦИОНИЗМ — (от позднелат. intuitio, от лат. intueor пристально смотрю) направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика … Философская энциклопедия
Трансфинитные числа — (от Транс… и лат. finitus ограниченный) обобщённые порядковые числа. Определение Т. ч. опирается на понятие вполне упорядоченного множества (см. Упорядоченные и частично упорядоченные множества). Каждое конечное множество можно сделать… … Большая советская энциклопедия
интуиционизм — направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика должна опираться, согласно И., на интуитивное представление … Словарь терминов логики
СОФИЗМ — (греч. sophisma хитрая уловка, измышление) рассуждение, кажущееся правильным, но содержащее скрытую логическую ошибку и служащее для придания видимости истинности ложному утверждению. С. является особым приемом интеллектуального мошенничества,… … Философская энциклопедия
ТОЖДЕСТВА ПРОБЛЕМЫ — проблемы эквивалентности, проблемы иден тичности, проблемы равенства с л о в (англ. word problems) – задачи нахождения общего метода (алгоритма), позволяющего для произвольной пары элементов к. л. множества, в к ром определено отношение типа… … Философская энциклопедия
Софизм — (от греч. sóphisma уловка, ухищрение, выдумка, головоломка) умозаключение или рассуждение, обосновывающее какую нибудь заведомую нелепость, абсурд или парадоксальное утверждение, противоречащее общепринятым представлениям. Аристотель… … Большая советская энциклопедия
Трансфинитная индукция — способ математических доказательств, обобщающий обычный принцип математической индукции (См. Математическая индукция). См. Трансфинитные числа … Большая советская энциклопедия
Софизм — (от греч. σόφισμα, «мастерство, умение, хитрая выдумка, уловка, мудрость») ложное высказывание, которое, тем не менее, при поверхностном рассмотрении кажется правильным. Софизм основан на преднамеренном, сознательном нарушении правил логики … Википедия

Приложение 10. Пример доказательства по индукции. Великая Теорема Ферма

Приложение 10. Пример доказательства по индукции

В математике важно иметь точные формулы, позволяющие вычислять сумму различных последовательностей чисел. В данном случае мы хотим вывести формулу, дающую сумму первых n натуральных чисел.

Например, «сумма» всего лишь одного первого натурального числа 1 равна 1; сумма двух первых натуральных чисел 1+2 равна 3, сумма первых трех натуральных чисел 1+2+3 равна 6, сумма первых четырех натуральных чисел 1+2+3+4 равна 10 и т. д.

Возможно, что требуемая формула имеет вид

?(n) = ?·n(n + 1).

Иначе говоря, если требуется найти сумму n первых натуральных чисел, то нужно просто подставить число n в приведенную выше формулу и получить ответ.

Доказательство по индукции позволяет убедиться в том, что эта формула дает правильный ответ при любом натуральном числе от 1 до бесконечности. Первый шаг состоит в том, чтобы показать, что формула работает в первом случае, при n=1. В этом нетрудно убедиться непосредственно, так как мы знаем, что сумма, состоящая из одного-единственного слагаемого, числа 1, равна 1. Подставляя n=1 в нашу формулу убеждаемся в том, что она дает правильный результат:

?(1) = ?·1·(1 + 1).

Следующий шаг в доказательстве по индукции заключается в том, чтобы показать, что если формула верна при каком-то значении n, то она должна быть верна и при n+1. Если

?(n) = ?·n(n + 1).

то

?(n + 1) = ?(n) + (n + 1) = ?·n(n + 1) + (n + 1).

После преобразования членов в правой части получаем

?(n + 1) = ?·(n + 1)[(n + 1) + 1].

Важно отметить, что последняя формула «устроена» точно так же, как исходная формула с той лишь разницей, что там, где в исходной формуле стоит n, в новой формуле стоит n+1. Иначе говоря, если формула верна для n, то она должна быть верна и для n+1. Доказательство по индукции завершено.

Поделитесь на страничке

Следующая глава >

доказательство по индукции — это… Что такое доказательство по индукции?

доказательство по индукции: мат. inductive proof, proof by induction

доказательство по аналогии
доказательство по иску

Смотреть что такое «доказательство по индукции» в других словарях:

ДОКАЗАТЕЛЬСТВО МЕТОДОМ ИНДУКЦИИ — (proof by induction) Метод, доказывающий существование некоего свойства у членов последовательности. Сначала проверяется в лоб наличие его у нескольких первых, затем высказывается предположение, что им обладают все – до N го включительно и… … Экономический словарь
Доказательство одноцветности всех лошадей — Доказательство одноцветности всех лошадей ошибочное доказательство того, что все лошади одного цвета, придуманное венгерским математиком Пойа[1]. Доказательство призвано продемонстрировать ошибки, возникающие при неправильном использовании… … Википедия
ДОКАЗАТЕЛЬСТВО — рассуждение, устанавливающее истинность к. л. утверждения путем приведения др. утверждений, истинность которых уже установлена. В Д. различаются тезис утверждение, которое нужно доказать, и основание, или аргументы, те утверждения, с помощью… … Философская энциклопедия
Метод математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… … Википедия
Принцип математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… … Википедия
КОСМОЛОГИЧЕСКОЕ ДОКАЗАТЕЛЬСТВО БЫТИЯ БОГА — своеобразная рационализация основного догмата авраамических религий о Боге как созидателе мирового порядка (космоса), отвечающая Книге Бытия из Ветхого завета. Оно называется космологическим (но не просто логическим ) потому, что апеллирует к… … Современный философский словарь
Математическая индукция — Математическая индукция один из методов математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала пров … Википедия
Теорема Бертрана о выборах — В комбинаторике, Теорема Бертрана о выборах, названая в честь Жозефа Бертрана, который опубликовал ее в 1887 году утверждение, доказывающее ответ на вопрос «Какова вероятность того, что на выборах с участием двух кандидатов, в которых… … Википедия
Неравенство Бернулли — утверждает: если , то для всех Доказательство Доказательство неравенства проводится методом математической индукции по n. При n = 0 неравенство, очевидно, верно. Допустим, что оно верно для n, докажем его вернос … Википедия
Доказательства вообще — Доказательство (Demonstratio) есть выведение истинности какого либо положения (на основании силлогистических законов) из других положений. Доказывать можно лишь положения (понятия могут быть определяемы, факты объясняемы и показываемы), и притом… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Coq — (фр. coq петух) интерактивное программное средство доказательства теорем, использующее собственный язык функционального программирования (Gallina) с зависимыми типами. Позволяет записывать математические теоремы и их… … Википедия

Книги

Практическая логика. Учебное пособие для академического бакалавриата, Ивин А.А.. В учебном пособии описаны основы логики. Даны задачи и законы логики, описана неклассическая логика и ее направления. Рассмотрено доказательство, раскрыты его структура и виды, способы… Подробнее Купить за 1093 грн (только Украина)
Практическая логика. Учебное пособие для академического бакалавриата, Ивин А.А.. В учебном пособии описаны основы логики. Даны задачи и законы логики, описана неклассическая логика и ее направления. Рассмотрено доказательство, раскрыты его структура и виды, способы… Подробнее Купить за 845 руб
Практическая логика 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата, А. А. Ивин. В учебном пособии описаны основы логики. Даны задачи и законы логики, описана неклассическая логика и ее направления. Рассмотрено доказательство, раскрыты его структура и виды, способы… Подробнее Купить за 499 руб электронная книга

Другие книги по запросу «доказательство по индукции» >>