Математическая индукция это: Недопустимое название — Викиучебник — Детская игровая комната «Волшебный лес»

Posted on 13.04.197206.01.2022 by alexxlab

Содержание

Математическая индукция — CoderLessons.com

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

Определение

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

Техника состоит из двух шагов, чтобы доказать утверждение, как указано ниже —

Шаг 1 (Базовый шаг) — Это доказывает, что утверждение верно для начального значения.

Шаг 2 (Индуктивный шаг) — Это доказывает, что если утверждение верно для n- ^й итерации (или числа n ), то оно также верно для (n + 1) ^-й итерации (или числа n + 1 ).

Как это сделать

Шаг 1 — Рассмотрим начальное значение, для которого утверждение верно. Следует показать, что утверждение верно для n = начального значения.

Шаг 2 — Предположим, что утверждение верно для любого значения n = k . Затем докажите, что утверждение верно для n = k + 1 . На самом деле мы разбиваем n = k + 1 на две части, одна часть — n = k (что уже доказано), и пытаемся доказать другую часть.

Проблема 1

3n−1 является кратным 2 для n = 1, 2, …

Решение

Шаг 1 — для n=1,31−1=3−1=2, который кратен 2

Шаг 2. Предположим, что 3n−1 верно для n=k, следовательно, 3k−1 верно (это предположение)

Мы должны доказать, что 3k+1−1 также кратно 2

3k+1−1=3 раз3k−1=(2 раза3k)+(3k−1)

Первая часть (2 times3k) наверняка будет кратна 2, а вторая часть (3k−1) также верна, как наше предыдущее предположение.

Следовательно, 3k+1−1 кратно 2.

Итак, доказано, что 3n−1 кратно 2.

Проблема 2

1+3+5+…+(2n−1)=n2 для n=1,2, dots

Решение

Шаг 1 — для n=1,1=12, следовательно, шаг 1 выполняется.

Шаг 2. Предположим, что утверждение верно для n=k.

Следовательно, 1+3+5+ dots+(2k−1)=k2 верно (это предположение)

Мы должны доказать, что 1+3+5+…+(2(k+1)−1)=(k+1)2 также имеет место

1+3+5+ dots+(2(k+1)−1)

=1+3+5+ dots+(2k+2−1)

=1+3+5+ dots+(2k+1)

=1+3+5+ dots+(2k−1)+(2k+1)

=k2+(2k+1)

=(k+1)2

Итак, выполняется 1+3+5+ dots+(2(k+1)−1)=(k+1)2, что удовлетворяет шагу 2.

Следовательно, 1+3+5+ dots+(2n−1)=n2 доказано.

Проблема 3

Докажите, что (ab)n=anbn верно для каждого натурального числа n

Решение

Шаг 1 — Для n=1(ab)1=a1b1=ab, следовательно, шаг 1 выполняется.

Шаг 2 — Предположим, что утверждение верно для n=k, следовательно, (ab)k=akbk верно (это предположение).

Мы должны доказать, что (ab)k+1=ak+1bk+1 также имеет место

Учитывая, (ab)k=akbk

Или, (ab)k(ab)=(akbk)(ab) [Умножение обеих сторон на ‘ab’]

Или (ab)k+1=(aak)(bbk)

Или (ab)k+1=(ak+1bk+1)

Следовательно, шаг 2 доказан.

Таким образом, (ab)n=anbn верно для каждого натурального числа n.

Сильная Индукция

Сильная индукция является еще одной формой математической индукции. С помощью этой техники индукции мы можем доказать, что пропозициональная функция P(n) справедлива для всех натуральных чисел n, используя следующие шаги:

Шаг 1 (Базовый шаг) — Доказано, что начальное предложение P(1) верно.

Шаг 2 (Индуктивный шаг) — Доказывается, что условное утверждение [P(1) landP(2) landP(3) land dots landP(k)]→P(k+1) верно для натуральных чисел k.

§ 6. Математическая индукция. Введение в логику и научный метод

Площадь всякого треугольника равна

это утверждение общее.

От этого общего утверждения можно сделать переход к частному утверждению, например такому:

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

т. е. равна , где а — длина стороны равностороннего треугольника.

Дедукция есть одна из форм умозаключения. (Дедукция происходит от латинского слова «deductio» — выведение.)

Индукцией называется переход от частного утверждения к общему. Индукция есть также одна из форм умозаключения, применяя которую от знания отдельного факта идут к обобщению, к общему положению. (Индукция происходит от латинского слова «inductio» — наведение, побуждение.)

Все формы умозаключения связаны между собой, а потому связаны между собой дедукция и индукция. Одна дедукция (или одна индукция) никогда не может обеспечить познания объективной действительности.

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

Рассмотрим выражение

Подставив в это выражение вместо п нуль, получим простое число 41. Подставив вместо п единицу, получим 43, т. е. опять простое число. Продолжая подставлять вместо п последовательно 2; 3; 4; 5; 6; 7; 8; 9; 10; 11, получим соответственно 47, 53; 61; 71; 83; 97; 113; 131 151; 173, т. е. опять же числа простые. Можем ли мы теперь быть уверенными в справедливости такого утверждения:

«Выражение принимает значение, равное простому числу при любом целом положительном значении буквы п»?

Быть уверенными в справедливости этого утверждения мы не можем, так как полученные выше результаты не являются достаточным основанием для такого утверждения. Они являются лишь основанием для предположения о верности этого утверждения. В действительности более полное исследование выражения показывает, что значение этого выражения не при всяком целом значении п является простым числом. Например, при п= 40 получается число 1681, которое уже не является простым. (Число 1681 делится на 41.)

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

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

Принцип математической индукции можно сформулировать следующим образом.

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

Пусть S(n)—некоторое утверждение, в формулировку которого входнт натуральное число п. Пусть, во-первых, утверждение справедливо и пусть, во-вторых, из справедливости утверждения S(k), где k есть тоже любое натуральное число, не меньшее следует справедливость утверждения S(k + 1). Тогда утверждение S(n) справедливо при любом

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

Допустим, что утверждение S(n) не справедливо при некотором т. е. что утверждение S(N) ложно. Тогда должно быть ложным и утверждение S(N — 1), так как в противном случае из справедливости S(N — 1) по второму условию теоремы следовала бы справедливость и утверждения S(N). Точно так же убеждаемся, что из ложности S(N— 1) следует ложность S(N — 2), а из этого ложность
S(N —3) и т. д.

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

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

Если в утверждении некоторой теоремы фигурирует целое положительное число п и если из справедливости этой теоремы для какого угодно частного значения п = k следует справедливость ее для значения k + 1, то, коль скоро это утверждение справедливо для п — 1, оно будет справедливо для любого целого положительного числа п.

Здесь дело обстоит так. Сначала мы убеждаемся в том, что теорема верна при п = 1. Затем, предполагая, что она верна для какого угодно частного значения п = k, доказываем ее справедливость для п = k + 1.

После этого рассуждаем так: поскольку теорема верна для п = 1, значит, она будет верной и для п — 1 + 1, т. е. для п = 2. Поскольку она верна для п = 2, она будет верной и для п = 2 + 1, т. е. для п = 3 и т. д.

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

Примеры:

1. Доказать, что

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

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

1. При п = 1 утверждение справедливо,

так как

2. Допустим, что утверждение справедливо при п = k, т. е

Тогда

Утверждение оказалось верным и для п =k+1. Следовательно, теорема верна при всяком целом положительном значении п.

Доказать, что

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

1. При п = 1 утверждение справедливо, так как

2. Допустим, что утверждение справедливо при п = k, т. е.

Тогда

Утверждение оказалось верным и для п = k + 1. Следовательно, формула верна при всяком целом положительном значении п.

3. Доказать, что при п > 1

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

При п = 2 утверждение справедливо.
Действительно,

Итак, оказалось, что

Но а потому

Следовательно,

Пусть

Докажем, что тогда будет справедливым и неравенство:

К обеим частям неравенства (I) прибавим по . Тогда получим:

или

Но Поэтому и подавно

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

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

Существует очень много и других теорем, которые успешно доказываются с помощью метода математической индукции. Некоторые из таких теорем встретятся нам в последующих главах.

Доказательство неравенства

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

где — положительные числа.

(Выражение называется средним геометрическим чисел , выражение — их средним арифметическим.)

Во-первых, покажем справедливость неравенства (А) при n = 2.

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

Отсюда

Значит, при n = 2 неравенство (А) справедливо. Теперь докажем следующую лемму.

Лемма:

Если неравенство (А) верно при п = k, то оно будет верно при n=2k.

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

Пользуясь свойствами арифметических корней, получим:

Но

(Мы здесь воспользовались доказанным выше неравенством:

Следовательно,

Поскольку мы предположили неравенство (А) верным при n = k, постольку

Учитывая эти два последних неравенства и неравенство (В), получим:

Итак, предполагая, что неравенство (А) справедливо при п = 2k, мы доказали, что оно будет справедливым и при п = 2k. Но ранее было доказано, что неравенство (А) справедливо при п = 2. Следовательно, оно будет справедливым и при п = 4,8,16, 32,…, т. е. при где m — любое натуральное число.

Теперь перейдем к доказательству неравенства (А) для любого натурального числа п.

Пусть п есть любое натуральное число. Если окажется, что п есть целая степень числа 2, то для такого п, как это уже было доказано, неравенство (А) справедливо. Если же п не есть целая степень числа 2, то к n всегда можно прибавить такое число q, что п+ q станет целой степенью числа 2. Итак, положим, что

Тогда получим неравенство:

справедливое при любых положительных где

Это следует из того, что число п + q есть целая степень числа 2. Положим, что

Тогда получим последовательно:

или

и, наконец,

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

Значит, неравенство (А) справедливо при всяком натуральном п.

Метод математической индукции

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

Предложение , зависящее от натуральной переменной , считается истинным для всех , если выполнены следующие два условия:

а) предложение истинно для ;

б) из предположения, что истинно для (где — любое натуральное число), следует, что оно истинно и для следующего значения, т.е. для .

Этот принцип называется принципом математической индукции.

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

Пример:

Методом математической индукции доказать равенство

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

При равенство (1) является верным . Нужно доказать, что из предположения о том, что является верным равенство (1), следует справедливость равенства

полученного из (1) заменой на

Прибавляя к обеим частям (1) слагаемое , имеем

Преобразуя правую часть (3), получаем

Таким образом, равенство (2) является верным, и поэтому формула (1) доказана для любого

Дадим другое доказательство формулы (1), используя символ которым обозначается сумма т.е. Воспользуемся тождеством

Полагая в (4) и складывая получаемые равенства, находим

Левая часть (5) равна а Поэтому из (5) получаем

откуда следует равенство (1).

Пример:

Доказать, что для любых и при любом справедлива формула бинома Ньютона

где

Правую часть формулы (6) называют разложением бинома, числа — биномиальными коэффициентами, слагаемое членом разложения бинома.

Доказательство. Воспользуемся методом математической индукции. При формула (6) верна, так как ее правая часть равна левой:

Предполагая справедливым равенство (6), докажем, что верна формула

Умножая обе части равенства (6) на получаем

где

Следовательно,

Сравнивая правые части равенств (8) и (9), заключаем, что для доказательства формулы (8) достаточно показать, что

Используя (7), находим

Поэтому

Равенство (10) доказано и поэтому справедливо равенство (8). Итак, формула (6) верна при любом . Отметим, что

т.е.

Поэтому формулу (6) можно записать в виде

Из (11) следует, что .

Возможно вам будут полезны эти страницы:

Решение заданий и задач по предметам:

Дополнительные лекции по высшей математике:

Тождественные преобразования алгебраических выражений
Функции и графики
Преобразования графиков функций
Квадратная функция и её графики
Алгебраические неравенства
Неравенства
Неравенства с переменными
Прогрессии в математике
Арифметическая прогрессия
Геометрическая прогрессия
Показатели в математике
Логарифмы в математике
Исследование уравнений
Уравнения высших степеней
Уравнения высших степеней с одним неизвестным
Комплексные числа
Непрерывная дробь (цепная дробь)
Алгебраические уравнения
Неопределенные уравнения
Соединения
Бином Ньютона
Число е
Непрерывные дроби
Функция
Исследование функций
Предел
Интеграл
Двойной интеграл
Тройной интеграл
Интегрирование
Неопределённый интеграл
Определенный интеграл
Криволинейные интегралы
Поверхностные интегралы
Несобственные интегралы
Кратные интегралы
Интегралы, зависящие от параметра
Квадратный трехчлен
Производная
Применение производной к исследованию функций
Приложения производной
Дифференциал функции
Дифференцирование в математике
Формулы и правила дифференцирования
Дифференциальное исчисление
Дифференциальные уравнения
Дифференциальные уравнения первого порядка
Дифференциальные уравнения высших порядков
Дифференциальные уравнения в частных производных
Тригонометрические функции
Тригонометрические уравнения и неравенства
Показательная функция
Показательные уравнения
Обобщенная степень
Взаимно обратные функции
Логарифмическая функция
Уравнения и неравенства
Положительные и отрицательные числа
Алгебраические выражения
Иррациональные алгебраические выражения
Преобразование алгебраических выражений
Преобразование дробных алгебраических выражений
Разложение многочленов на множители
Многочлены от одного переменного
Алгебраические дроби
Пропорции
Уравнения
Системы уравнений
Системы уравнений высших степеней
Системы алгебраических уравнений
Системы линейных уравнений
Системы дифференциальных уравнений
Арифметический квадратный корень
Квадратные и кубические корни
Извлечение квадратного корня
Рациональные числа
Иррациональные числа
Арифметический корень
Квадратные уравнения
Иррациональные уравнения
Последовательность
Ряды сходящиеся и расходящиеся
Тригонометрические функции произвольного угла
Тригонометрические формулы
Обратные тригонометрические функции
Теорема Безу
Показатель степени
Показательные функции и логарифмы
Множество
Множество действительных чисел
Числовые множества
Преобразование рациональных выражений
Преобразование иррациональных выражений
Геометрия
Действительные числа
Степени и корни
Степень с рациональным показателем
Тригонометрические функции угла
Тригонометрические функции числового аргумента
Тригонометрические выражения и их преобразования
Преобразование тригонометрических выражений
Комбинаторика
Вычислительная математика
Прямая линия на плоскости и ее уравнения
Прямая и плоскость
Линии и уравнения
Прямая линия
Уравнения прямой и плоскости в пространстве
Кривые второго порядка
Кривые и поверхности второго порядка
Числовые ряды
Степенные ряды
Ряды Фурье
Преобразование Фурье
Функциональные ряды
Функции многих переменных
Метод координат
Гармонический анализ
Вещественные числа
Предел последовательности
Аналитическая геометрия
Аналитическая геометрия на плоскости
Аналитическая геометрия в пространстве
Функции одной переменной
Высшая алгебра
Векторная алгебра
Векторный анализ
Векторы
Скалярное произведение векторов
Векторное произведение векторов
Смешанное произведение векторов
Операции над векторами
Непрерывность функций
Предел и непрерывность функций нескольких переменных
Предел и непрерывность функции одной переменной
Производные и дифференциалы функции одной переменной
Частные производные и дифференцируемость функций нескольких переменных
Дифференциальное исчисление функции одной переменной
Матрицы
Линейные и евклидовы пространства
Линейные отображения
Дифференциальные теоремы о среднем
Теория устойчивости дифференциальных уравнений
Функции комплексного переменного
Преобразование Лапласа
Теории поля
Операционное исчисление
Системы координат
Рациональная функция
Интегральное исчисление
Интегральное исчисление функций одной переменной
Дифференциальное исчисление функций нескольких переменных
Отношение в математике
Математическая логика
Графы в математике
Линейные пространства
Первообразная и неопределенный интеграл
Линейная функция
Выпуклые множества точек
Система координат

Занятие 9.

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

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

Но есть и еще один способ рассуждений – от частного к общему. Такой метод носит название индукция. Индукция (induction– по-латыни наведение). То есть один или несколько частных случаев «наводят» на общее утверждение, общий вывод делается на основании частных наблюдений. Однако, индуктивный метод имеет весьма существенный недостаток: на основании частных примеров может быть сделан неверный вывод. Гипотезы, возникающие при частных наблюдениях, не всегда являются правильными. Рассмотрим пример, принадлежащий Эйлеру.

Будем вычислять значение трехчлена n² +n+41 при некоторых первых значениях n:

n	1	2	3	4	5	6	7	8
	43	47	53	61	71	83	97	113

Заметим, что получаемые в результате вычислений числа являются простыми. И непосредственно можно убедиться, что для каждого n от 1 до 39 значение многочлена является простым числом. Однако при n=40 получаем число 1681=41², которое не является простым. Таким образом, гипотеза, которая здесь могла возникнуть, то есть гипотеза о том, что при каждом n число n²+n+41 является простым, оказывается неверной.

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

1 шаг. Проверяем истинность утверждения P(п) для п = 1.

2 шаг. Предполагаем, что P(п) истинно для п = к (к — произвольное натуральное число).

3 шаг. Доказываем, что Р(п) истинно, для п = к + 1.

Заменим в левой части равенства первые к слагаемых их суммой из 2-го шага:

В числителе левой части раскроем скобки:

Способом группировки разложим числитель левой части на множители:

Равенство верно.

Задание 2.

(Задача из книги А. Шеня «Математическая индукция», Москва, издательство МЦНМО, 2007)

Игрушка «Ханойские башни» имеет три стержня. На одном находится пирамидка из нескольких колец (уменьшающихся снизу вверх). Эту пирамидку нужно переложить на другой стержень, соблюдая правила игры: нельзя переносить сразу несколько колец и нельзя класть большее кольцо поверх меньшего. Например, пирамидку из двух колец можно переложить так: положить меньшее кольцо на второй стержень, затем большее на третий, а затем меньшее поверх большего. Доказать, что возможно переместить на другой стержень пирамидку из любого числа колец, соблюдая правила игры.

Задание 3.

Задание 4.

Доказать, что для любого натурального n значение выражения 4ⁿ +15n-1 кратно 9.

Задание 5.

Доказать, что при любом натуральном n число

делится на 3.

Задание 6.

Доказать, что сумма первых n натуральных нечётных чисел равна квадрату их числа, то есть

Задание 7.

Доказать, что

Задание 8.

Доказать, что сумма квадратов n первых чисел натурального ряда равна

Задание 9.

Доказать, что

Задание 10.

Доказать, что

Задание 11.

Доказать, что

Задание 12.

Доказать, что

Метод математической индукции (ММИ) | Математика, которая мне нравится

Рассмотрим на примере, как работает метод.

Задача. Доказать, что для всех натуральных справедливо равенство

Решение. Обозначим через левую часть равенства, а через — его правую часть.

1) Докажем сначала, что .

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

2) Дано: . Нужно доказать: .

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

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

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

Для того чтобы доказать все эти утверждения, достаточно доказать две теоремы:

1. — верное утверждение.

2. Если для какого-либо натурального верно утверждение , то верно и утверждение .

Такой способ доказательства последовательности утверждений называется методом математической индукции. Первая часть метода называется базой индукции, вторая — индукционным переходом.

Теорема. Если последовательности и таковы, что , и для любого натурального

то для всех натуральных выполняется равенство .

С помощью метода математической индукции можно также доказывать неравенства.

Теорема. Если последовательности и таковы, что , и для любого натурального

то для всех натуральных выполняется неравенство .

Пример. Доказать, что для всех натуральных

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

Действительно,

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

то для всех натуральных выполняется неравенство .

Задачи. Доказать

1. .

2. .

3. при .

4. при .

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

6. Доказать, что для всех натуральных

(четверок — ).

7. Доказать, что для всех натуральных

8. Доказать, что для всех натуральных

9. Доказать, что для всех натуральных

10. Доказать, что сторона правильного вписанного в окружность -угольника выражается формулой

где — радиус этой окружности (двоек — ).

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

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

13. Доказать, что если — суммы членов геометрических прогрессий, у которых первые члены , а знаменатели соответственно равны , то

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

равна квадрату нечетного числа.

15. Доказать, что произведение

состоящее из сомножителей, равно

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

17. Доказать, что для любого натурального

математическая индукция | Определение, принцип и доказательство

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

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

Класс целые числа называются наследственными, если всякий раз, когда любое целое число x принадлежит классу, наследник x (то есть целое число x + 1) также принадлежит классу. Принцип математической индукции тогда: Если целое число 0 принадлежит классу F и F является наследственным, каждое неотрицательное целое число принадлежит F . В качестве альтернативы, если целое число 1 принадлежит классу F и F наследственно, то каждое положительное целое число принадлежит F. Принцип формулируется иногда в одной форме, иногда в другой. Поскольку любая форма принципа легко доказывается как следствие другой, нет необходимости проводить различие между ними.

Этот принцип также часто формулируется в интенсиональной форме: свойство целых чисел называется наследственным, если всякий раз, когда любое целое число x обладает этим свойством, его преемник обладает этим свойством. Если целое число 1 обладает определенным свойством, и это свойство является наследственным, каждое положительное целое число обладает этим свойством.

Доказательство математической индукцией

Примером применения математической индукции в простейшем случае является доказательство того, что сумма первых n нечетных натуральных чисел равна n ^2, то есть (1.) 1 + 3 + 5 + ⋯ + (2 n — 1 ) = n ² для любого натурального числа n . Пусть F — класс целых чисел, для которых выполняется уравнение (1.) ; тогда целое число 1 принадлежит F , так как 1 = 1 ² . Если любое целое число x принадлежит F , то (2.) 1 + 3 + 5 + ⋯ + (2 x — 1) = x ² . Следующее нечетное целое число после 2 x — 1 равно 2 x + 1, и, когда это добавляется к обеим частям уравнения (2.) , результат (3.) 1 + 3 + 5 + ⋯ + (2 x + 1) знак равно х ² + 2 х + 1 = ( х + 1) ² . Уравнение (2.) называется гипотезой индукции и утверждает, что уравнение (1.) выполняется, когда n равно x , а уравнение (3.) утверждает, что уравнение (1.) выполняется, когда n равно x + 1. Поскольку уравнение(3) было доказанокак следствие уравнения (2) , было доказаночто всякий разкогда х принадлежит F правопреемником х принадлежит F . Следовательнопо принципу математической индукции все целые положительные числа принадлежат F .

Получите подписку Britannica Premium и получите доступ к эксклюзивному контенту. Подпишитесь сейчас

Вышеизложенное является примером простой индукции; иллюстрацией многих более сложных видов математической индукции является следующий метод доказательства с помощью двойной индукции. Чтобы доказать, что конкретное бинарное отношение F выполняется среди всех положительных целых чисел, достаточно сначала показать, что отношение F выполняется между 1 и 1; во-вторых, всякий раз, когда F находится между x и y , оно выполняется между x и y + 1; и, в-третьих, всякий раз, когда F находится между x и некоторым положительным целым числом z (которое может быть фиксированным или может зависеть от x), между x + 1 и 1.

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

Пеано, Джузеппе
Джузеппе Пеано.
Архив истории математики MacTutor / Школа математики и статистики Университета Сент-Эндрюс, Шотландия
Анри Пуанкаре утверждал, что математическая индукция является синтетической и априорной, то есть она не сводится к принципу логики или не может быть доказана только на основе логических оснований, и тем не менее известна независимо от опыта или наблюдения. Таким образом, математическая индукция занимает особое место как составляющая математического рассуждения par excellence и позволяет математике исходить из своих предпосылок.к действительно новым результатам, что якобы невозможно с помощью одной лишь логики. В этой доктрине Пуанкаре следует школе математического интуиционизма, которая рассматривает математическую индукцию как окончательное основание математической мысли, не сводимое ни к чему предшествующему и синтетическое a priori в смысле Иммануила Канта .
Анри Пуанкаре, 1909 год.
Х. Роджер-Виолле
Этому прямо противоположно начинание Готтлоб Фреге , позже последовали Альфред Норт Уайтхед и Бертран Рассел вPrincipia Mathematica , чтобы показать, что принцип математической индукции является аналитическим в том смысле, что он сводится к принципу чистой логики путем подходящих определений задействованных терминов.
Трансфинитная индукция
Обобщением математической индукции, применимым к любому хорошо упорядоченному классу или области D вместо области положительных целых чисел, является метод доказательства с помощью трансфинитной индукции. Область D называется хорошо упорядоченной, если элементы (числа или объекты любого другого типа), принадлежащие ей, находятся в или были размещены в таком порядке, что: 1. ни один элемент не предшествует самому себе по порядку; 2. если x предшествует y по порядку, а y предшествует z , то x предшествует z ; 3.в каждом непустом подклассе D есть первый элемент (тот, который предшествует всем остальным элементам подкласса). Из 3., в частности, следует, что сама область D , если она не пуста, имеет первый элемент.
Когда элемент x предшествует элементу y в только что описанном порядке, можно также сказать, что y следует за x . Последователь элемента x хорошо упорядоченной области D определяется как первый элемент, следующий за x (поскольку согласно 3. , если есть какие-либо элементы, следующие за x , среди них должен быть первый). Точно так же, преемник класс Е элементов D является первым элементом , который следует все членам Е . Класс F элементов Dназывается наследственным, если всякий раз, когда все члены класса E элементов D принадлежат F , наследник E , если таковой имеется, также принадлежит F (и, следовательно, в частности, всякий раз, когда элемент x из D принадлежит F , преемник x , если таковой имеется, также принадлежит F ). Доказательство по индукции трансфинитной тогда зависит от принципа , что если первый элемент хорошо упорядоченной области D принадлежит к наследственному классу F , всем элементам D принадлежат F .
Один из способов трактовать математическую индукцию — рассматривать ее как частный случай трансфинитной индукции. Например, в некотором смысле простую индукцию можно рассматривать как трансфинитную индукцию, применяемую к области D положительных целых чисел. Фактическое сведение простой индукции к этому частному случаю трансфинитной индукции требует использования принципов, которые сами по себе обычно доказываются математической индукцией, особенно упорядочения положительных целых чисел, и принципа, который является наследником класса положительных целых чисел, если существует равно единице, должно быть преемником определенного целого числа (последнего или наибольшего целого числа) в классе. Следовательно, в некотором смысле математическая индукция не сводится к трансфинитной индукции.
Однако точка зрения трансфинитной индукции полезна при классификации более сложных видов математической индукции. В частности, двойную индукцию можно рассматривать как трансфинитную индукцию, применяемую к области D упорядоченных пар ( x , y ) положительных целых чисел, где D хорошо упорядочивается по правилу, что пара ( x ₁ , y ₁ ) предшествует паре ( x ₂ , y ₂ ), если x ₁ < x ₂ или если x ₁ = x ₂ и y ₁< у ₂ .
Метод математической индукции — презентация онлайн
1. Метод математической индукции
презентацию выполнили
ученики(-цы) 9 класса «Б»
МАОУ «Средняя Общеобразовательная Школа №83»
Рыбалко Екатерина, Дудырев Артём, Ямшинина Ульяна
город Пермь, 2019 год
2.
Цели / Задачи проекта обозначить
определение математической индукции
в краткой форме изложить историю возникновения метода
математической индукции
изложить формулировку принципа математической индукции
представить составляющее метода математической индукции
привести примеры и разобрать их, используя данный метод
3. Определение математической индукции
Математическая индукция — метод математического доказательства,
который используется для доказательства истинности некоторого
утверждения для всех натуральных чисел.
4. История появления метода математической индукции К середине XVII века в математике накопилось немало ошибочных выводов в силу
того, что многие
ученные верили в непогрешимость индукции. Требовалось научное обоснование метода, который
позволял бы делать общие выводы на основании рассмотрения нескольких частных случаев. И такой
метод был разработан. Основная заслуга в этом принадлежит французским математикам Паскалю и
Декарту, а также швейцарскому математику Бернулли, хоть и отдельные случаи применения
встречаются ещё в античные времена у Эвклида.
5. Принцип математической индукции
Если свойство, зависящее от натурального n, во-первых, верно при n=1 и,
во-вторых, из предположения, что оно верно при n=k, следует, что оно
верно при n=k+1, то считают что это свойство верно для любого
натурального n.
6. Составляющее метода математической индукции
Для справедливости любого утверждения, высказанного для всех
натуральных чисел n>1, достаточно:
(1) Доказать данное утверждение для n=1.
(2) Предположить его справедливость при n=k≥1.
(3) Доказать, что оно n=k+1.
7. Разбор примеров доказательств утверждений с помощью метода математической индукции
I. Применение метода математической индукции к доказательству 0 n=0.
II. Применение метода математической индукции к доказательству
неравенств.
III. Применение метода математической индукции к доказательству
формулы суммы первых n членов геометрической прогрессии, где q≠1.
Математическая индукция
Математическая индукция — это особый способ доказательства. В нем всего 2 ступени:
Шаг 1. Покажите, что это верно для первого
Шаг 2. Покажите, что если любое из истинно, то следующее истинно
Тогда все верны
Вы слышали об «эффекте домино»?
Шаг 1. Первое падение домино
Шаг 2.Когда выпадает любое домино, следующее домино выпадает
Итак … все домино упадут!
Так работает математическая индукция.
В мире чисел мы говорим:
Шаг 1. Покажите, что это верно для первого случая, обычно n = 1
Шаг 2. Покажите, что если n = k верно, то n = k + 1 также верно
Как это сделать
Шаг 1 обычно прост, нам просто нужно доказать, что он верен для n = 1
Шаг 2 лучше всего выполнить так:
Предположим, что верно для n = k
Докажите, что истинно для n = k + 1 (мы можем использовать случай n = k как факт . )
Это все равно что сказать «ЕСЛИ мы можем заставить домино упасть, упадет ли следующая?»
Шаг 2 часто может быть сложным , нам, возможно, придется использовать творческие уловки, чтобы заставить его работать!
Как в этом примере:
Пример: делится ли 3
ⁿ −1 на 2?
Это правда? Давайте узнаем.
1. Покажите, что это верно для n = 1
3 ¹ −1 = 3−1 = 2
Да 2 делится на 2.Это было просто.
3 ¹ −1 верно
2. Предположим, что это верно для n = k
3 ^k −1 верно
(Погодите! Откуда мы это знаем? Мы этого не делаем!
Это предположение … что мы рассматриваем
как факт для остальной части этого примера)
Теперь докажем, что 3 ^{k + 1} −1 делится на 2
3 ^{k + 1} также 3 × 3 ^k
Затем разделите 3 × на 2 × и 1 ×
И каждое из них кратно 2
Потому что:
2 × 3 ^k делится на 2 (мы умножаем на 2)
3 ^k −1 верно (мы сказали, что в предположении выше)
Итак:
3 ^{k + 1} −1 верно
СДЕЛАНО!
Вы видели, как мы использовали случай 3 ^k −1 как истинный , хотя мы этого и не доказали? Это нормально, потому что мы полагаемся на Domino Effect . ..
… мы спрашиваем , если упадет любое домино, упадет ли следующий ?
Итак, мы принимаем это как факт (временно), что домино « n = k » падает (т.е. 3 ^k −1 верно), и посмотрим, означает ли это « n = k + 1 ». «Домино тоже упадет.
Уловки
Я уже говорил, что нам часто нужно использовать воображаемые трюки.
Распространенный трюк — переписать случай n = k + 1 на 2 части:
одна часть представляет собой случай n = k (который предполагается верным)
затем можно проверить другую часть, чтобы убедиться, что она также верна
Мы сделали это в примере выше, а вот еще один:
Пример: сложение нечетных чисел
1 + 3 + 5 +… + (2n − 1) = n ²
1. Покажите, что это верно для n = 1
1 = 1 ² верно
2. Предположим, что это верно для n = k
1 + 3 + 5 + … + (2k − 1) = k ² верно
(Предположение!)
Теперь докажите, что это верно для «k + 1»
1 + 3 + 5 + … + (2k − 1) + (2 (k + 1) −1) = (k + 1) ² ?
Мы знаем, что 1 + 3 + 5 +… + (2k − 1) = k ² (предположение выше), поэтому мы можем сделать замену для всех членов, кроме последнего:
к ² + (2 (к + 1) −1) = (к + 1) ²
Теперь разверните все термины:
к ² + 2 к + 2 — 1 = к ² + 2 к + 1
И упростить:
к ² + 2 к + 1 = к ² + 2 к + 1
Они такие же! Так что это правда.
Итак:
1 + 3 + 5 +… + (2 (k + 1) −1) = (k + 1) ² верно
СДЕЛАНО!
Твоя очередь
А теперь еще два примера , на которых вы можете попрактиковаться.
Сначала попробуйте сами, а затем посмотрите наше решение ниже.
Пример: треугольные числа
Треугольные числа — это числа, которые могут образовывать треугольный точечный узор.
Докажите, что n-ое треугольное число равно:
Т _п = п (п + 1) / 2
Пример: сложение чисел куба
Числа куба — это кубы натуральных чисел
Докажите, что:
1 ³ + 2 ³ + 3 ³ +… + n ³ = ¼n ² (n + 1) ²
. . . . . . . . . . . . . . . . . .
Пожалуйста, не читайте решения, пока не попробуете сами, это единственные вопросы на этой странице, над которыми вы можете попрактиковаться!
Пример: треугольные числа
Докажите, что n-ое треугольное число равно:
Т _п = п (п + 1) / 2
1. Показать, что это верно для n = 1
T ₁ = 1 × (1 + 1) / 2 = 1 истинно
2. Предположим, что это верно для n = k
T _k = k (k + 1) / 2 Верно (предположение!)
Теперь докажите, что это верно для «k + 1»
Т _{к + 1} = (к + 1) (к + 2) / 2?
Мы знаем, что T _k = k (k + 1) / 2 (предположение выше)
T _{k + 1} имеет дополнительный ряд из (k + 1) точек
Итак, T _{k + 1} = T _k + (k + 1)
(к + 1) (к + 2) / 2 = к (к + 1) / 2 + (к + 1)
Умножьте все члены на 2:
(к + 1) (к + 2) = к (к + 1) + 2 (к + 1)
(к + 1) (к + 2) = (к + 2) (к + 1)
Они такие же! Так что правда .
Итак:
T _{k + 1} = (k + 1) (k + 2) / 2 истинно
СДЕЛАНО!
Пример: сложение чисел куба
Докажите, что:
1 ³ + 2 ³ + 3 ³ + … + n ³ = ¼n ² (n + 1) ²
1. Покажите, что это верно для n = 1
1 ³ = ¼ × 1 ² × 2 ² верно
2. Предположим, что это верно для n = k
1 ³ + 2 ³ + 3 ³ + … + k ³ = ¼k ² (k + 1) ² верно (предположение!)
Теперь докажите, что это верно для «k + 1»
1 ³ + 2 ³ + 3 ³ + … + (k + 1) ³ = ¼ (k + 1) ² (k + 2) ²?
Мы знаем, что 1 ³ + 2 ³ + 3 ³ +… + k ³ = ¼k ² (k + 1) ² (предположение выше), поэтому мы можем заменить все, кроме последнего члена:
¼k ² (k + 1) ² + (k + 1) ³ = ¼ (k + 1) ² (k + 2) ²
Умножьте все члены на 4:
к ² (к + 1) ² + 4 (к + 1) ³ = (к + 1) ² (к + 2) ²
Все термины имеют общий множитель (k + 1) ², поэтому его можно отменить:
к ² + 4 (к + 1) = (к + 2) ²
И упростить:
к ² + 4 к + 4 = к ² + 4 к + 4
Они такие же! Так что это правда.
Итак:
1 ³ + 2 ³ + 3 ³ + … + (k + 1) ³ = ¼ (k + 1) ² (k + 2) ² верно
СДЕЛАНО!
Математическая индукция — Темы в предварительном исчислении
27
Принцип математической индукции
ЕСТЕСТВЕННЫЕ ЧИСЛА — это подсчет числа: 1, 2, 3, 4 и т. д. Математическая индукция — это метод доказательства утверждения — теоремы или формулы — которое утверждается примерно на каждые натуральных чисел.
Под «каждым» или «всеми» натуральными числами мы подразумеваем любое имя, которое мы называем.
Например,
1 + 2 + 3 +. . . + n = ½ n ( n + 1).
Утверждают, что сумма последовательных чисел от 1 до n дается формулой справа. Мы хотим доказать, что это будет верно для n = 1, n = 2, n = 3 и так далее. Теперь мы можем проверить формулу для любого с заданным номером , скажем, n = 3:
.
1 + 2 + 3 = ½ · 3 · 4 = 6
— это правда.Это также верно для n = 4:
1 + 2 + 3 + 4 = ½ · 4 · 5 = 10.
Но как мы можем доказать это правило для через каждое значение из n ?
Метод доказательства следующий. Мы показываем, что , если утверждение — правило — верно для любого конкретного числа k (например, 104), то оно также будет верно для его преемника, k + 1 (например, 105). Затем мы покажем, что утверждение верно для 1.Из этого следует, что утверждение будет истинным для 2. Следовательно, оно будет истинным для 3. Оно будет истинным для любого натурального числа, которое мы назовем.
Это называется принципом математической индукции.
Если
1) , когда утверждение верно для натурального числа n = k ,
, то оно также будет верно для его преемника, n = k + 1;
и
2) утверждение верно для n = 1;
, тогда утверждение будет истинным для любого натурального числа n .
Чтобы доказать утверждение по индукции, мы должны доказать пункты 1) и 2) выше.
Гипотеза шага 1) — « Утверждение верно для n = k » — называется предположением индукции или гипотезой индукции. Это то, что мы, , предполагаем, , когда доказываем теорему по индукции.
Пример 1. Докажите, что сумма первых n натуральных чисел дается следующей формулой:
1 + 2 + 3 +.. . + n = n ( n + 1)
2 .
Доказательство . Мы выполним шаги 1) и 2) выше. Во-первых, мы предположим, что , что формула верна для n = k ; то есть примем:
1 + 2 + 3 +. . . + к = к ( к + 1)
2 .(1)
Это предположение индукции. Предполагая это, мы должны доказать, что формула верна для ее преемника, n = k + 1. То есть мы должны показать:
1 + 2 + 3 +. . . + ( к + 1) = ( к + 1) ( к + 2)
2 . (2)
Для этого мы просто добавим следующий член ( k + 1) к обеим сторонам предположения индукции, линия (1):
Это строка (2), это первое, что мы хотели показать.
Затем мы должны показать, что формула верна для n = 1. У нас есть:
1 = ½ · 1 · 2
— это правда. Теперь мы выполнили оба условия принципа математической индукции. Таким образом, формула верна для любого натурального числа.
(В Приложении к арифметике мы устанавливаем эту формулу напрямую.)
Пример 2. Докажите, что это правило экспонент верно для любого натурального числа n :
.
( ab ) ⁿ = a ⁿ b ⁿ.
Доказательство . Опять же, мы начинаем с , предполагая, что истинно для n = k ; то есть мы предполагаем:
( ab ) ^k = a ^k b ^k. . . . . . . . (3)
С этим предположением мы должны показать, что правило верно для его преемника, n = ( k + 1).Мы должны показать:
( ab ) ^{k + 1} = a ^{k + 1} b ^{k + 1}. . . . . . . (4)
(При использовании математической индукции ученик всегда должен писать именно то, что должно быть показано.)
Теперь, учитывая предположение, строку (3), как мы можем из нее построить строку (4)?
Просто умножив обе стороны прямой (3) на ab :
( ab ) ^k ab = a ^k b ^k ab
= a ^k a b ^k b
, поскольку порядок факторов не имеет значения,
= а ^{к + 1} b ^{к + 1}.
Это строка (4), которую мы хотели показать.
Итак, мы показали, что если теорема верна для любого конкретного натурального числа k , то она верна и для его преемника, k + 1.
Затем мы должны показать, что правило верно для n = 1; то есть
( ab ) ¹ = a ¹ b ¹.
Но ( ab ) ¹ = ab ; и a ¹ b ¹ = ab .
Следовательно, это правило верно для любого натурального числа n .
Пример 3. Сумма последовательных кубиков. Докажите этот замечательный арифметический факт:
1 ³ + 2 ³ + 3 ³ +. . . + n ³ = (1 + 2 + 3 +.. . + н ) ².
«Сумма n последовательных кубов равна квадрату
суммы первых n чисел».
Другими словами, согласно Примеру 1:
1 ³ + 2 ³ + 3 ³ +. . . + n ³ = n ² ( n + 1) ²
4
Доказательство .Для удобства обозначим сумму до n через S ( n ). Мы предполагаем, что формула верна для n = k ; то есть
S ( к ) = k ² ( k + 1) ²
4 (1)
Теперь мы должны показать, что формула верна и для n = k + 1; тот
S ( k + 1) = ( к + 1) ² ( к + 2) ²
4 (2)
Для этого добавьте следующий куб к S ( k ), строка (1):
S ( k + 1) = S ( к ) + ( к + 1) ³
= k ² ( k + 1) ²
4 + ( к + 1) ³
= k ² ( k + 1) ² + 4 ( k + 1) ³
4
= ( k + 1) ² [ k ² + 4 ( k + 1)]
4
— принимая ( k + 1) ² в качестве общего множителя,
= ( к + 1) ² ( к ² + 4 к + 4)
4
= ( к + 1) ² ( к + 2) ²
4
Это строка (2), которую мы хотели показать.
Наконец, мы должны показать, что формула верна для n = 1.
1 ³ = 1² · 2²
4
1 = 1 · 4
4
— это правда. Таким образом, формула верна для любого натурального числа.
В Приложении к арифметике мы прямо показываем, что это правда.
Задача 1. Согласно принципу математической индукции, чтобы доказать утверждение, которое утверждается в отношении каждого натурального числа n , нужно доказать две вещи.
а) Что первое?
Чтобы увидеть ответ, наведите указатель мыши на цветную область.
Чтобы закрыть ответ еще раз, нажмите «Обновить» («Reload»).
Если утверждение верно для n = k , то оно будет верно для его преемника, k + 1.
б) Что такое второе?
Утверждение верно для n = 1.
c) Часть a) содержит предположение индукции. Что это?
Утверждение верно для n = k .
Проблема 2.Пусть S ( n ) = 2 n — 1. Вычислите
а) S ( к ) = 2 к — 1
б) S ( к + 1) = 2 ( k + 1) — 1 = 2 k + 2 — 1 = 2 k + 1
Задача 3. Сумма первых n нечетных чисел равна n-му квадрату .
1 + 3 + 5 + 7 +. . . + (2 n — 1) = n ².
a) Чтобы доказать, что с помощью математической индукции, какова будет индукция
а) предположение?
Утверждение верно для n = k :
1 + 3 + 5 + 7 +. . . + (2 к — 1) = к ².
б) Что мы должны показать на основании этого предположения?
Утверждение верно для его преемника, k + 1:
.
1 + 3 + 5 + 7 +. . . + (2 k — 1) + 2 k + 1 = ( k + 1) ².
c) Покажи это.
При добавлении 2 k + 1 к обеим сторонам предположения индукции:
1 + 3 + 5 + 7 +. . . + (2 к — 1) + 2 к + 1 = к ² + 2 к + 1
= ( к + 1) ²
г) Что мы должны показать, чтобы завершить доказательство математической индукцией?
Утверждение верно для n = 1.
д) Покажи это.
1 = 1 ²
Задача 4. Докажите математической индукцией:
Если мы обозначим эту сумму как S ( n ), тогда предположим, что формула верна для n = k ; то есть предположим, что
S ( к ) = к
2 к + 1 .
Теперь покажите, что формула верна для n = k + 1; то есть показать:
S ( к + 1) = к + 1
2 к + 3 .
Начало:
Далее,
Формула верна для n = 1:
Следовательно, это верно для всех натуральных чисел.
Содержание | Дом
Сделайте пожертвование, чтобы TheMathPage оставалась в сети.
Даже 1 доллар поможет.
Авторские права © 2021 Лоуренс Спектор
Вопросы или комментарии?
Электронная почта: [электронная почта защищена]

Создание математики: математические инструменты: математическая индукция
Математическая индукция — распространенный метод доказательства теоремы о натуральных числах или о любой ситуации, когда один случай зависит от предыдущих случаев. Вот основная идея, сформулированная в виде целых чисел:
У вас есть предположение, которое, по вашему мнению, верно для каждое целое число больше 1. Показать (вычислением или другим способом) что ваша гипотеза определенно верна для 1.
Покажите, что всякий раз, когда ваша гипотеза верна для некоторых число, оно должно сохраняться и для следующего числа.
Почему это работает? Ну вы знаете свою догадку выполняется для 1.Вы показали, что всякий раз, когда это справедливо для некоторого числа, оно должно быть верным и для следующего, так что ваша гипотеза верна и для 2. Но если он выполняется для 2, он должен выполняться и для следующего числа, поэтому он выполняется для 3. И так далее, для всех целых чисел больше 1.
Несколько замечаний:
Начальная точка (или базовый случай) 1 является обычным явлением, но это не единственный выбор. У вас может быть гипотеза, которая верна для каждое целое число больше 5 или каждое целое число больше 1001. Единственное, что изменится, — это базовый вариант.
На практике, шаг 2 заключается в том, что вы предполагаете, что для некоторого номера, который вы набираете (n-1), ваша гипотеза верна. (Это называется предположением индукции.) Используйте это предположение, чтобы показать, что гипотеза должно выполняться и для числа n.Некоторые люди жалуются, что они «предполагают что они хотят доказать ». Конечно, это не так. Вы просто доказываете, что если ваше утверждение верно в конкретном случае, то оно верно для последующего. Если базовый вариант не может быть установлен, тогда связь между делами бессмысленна. Предположение нет отличается от того, который мы делаем, когда говорим «если форма параллелограмм, то прилегающие к нему углы являются дополнительными. ” Мы не доказали, что какие-либо фигуры являются параллелограммами. Мы просто утверждая, что если существует форма, которая соответствует нашему определению для параллелограмм, что он также должен обладать указанным свойством.
Может быть полезно небольшое изменение гипотезы индукции: предположим что для всех целых k
Математическая индукция и ее вариации полезны при доказательстве идентичности, которые верны для любого значения целого числа, но они не помочь вам увидеть, как кто-то определил личность в первую очередь.
Математическая индукция полезна не только для доказательства алгебраических идентичности. Его можно использовать в любое время, когда у вас есть рекурсивные отношения — один где текущий случай зависит от одного или нескольких предыдущих случаев. См. Второй пример ниже для геометрического применения индукции. Вот еще общий способ думать об индукции:
У вас есть гипотеза, которая, по вашему мнению, верна во всех случаях.Докажите, что ваша гипотеза определенно верна для базового случая.
Покажите, что всякий раз, когда ваша гипотеза верна для некоторого случая, она должна справедливо и для следующего случая.
Примеры
Вот пример использования целых чисел. Кто-то открыл формулу, которая похоже, работает для суммы целых чисел:
Вы можете проверить много-много дел, но неважно как долго вы работали, вы никогда не сможете проверить, что формула верна для каждое целое число больше 1. С помощью математической индукции вы могу доказать, что это так!
Покажите, что гипотеза верна для базового случая. Итак, сумма слева будет равна 1. Формула справа дает = 1. Таким образом, формула верна за 1.
Покажите, что всякий раз, когда ваша гипотеза верна для некоторых число, оно должно сохраняться и для следующего числа. Так хорошо начните с исходной формулы и покажите, что когда она верна для некоторое n — 1, тогда формула должна работать и для n:
Теперь равенство будет сохраняться, если мы добавим n к обеим частям уравнения:
И сделаем небольшое упрощение справа часть уравнения, пытаясь получить ее в виде нашего оригинального гипотеза:
, что является нашей оригинальной формулой!
Итак, формула верна для 1. Если это верно для 1, это должен удерживать 2 (следующее число). Если это верно для 2, оно должно сохраняться в течение 3 (следующее число). И так далее, и так далее — по математической индукции, это справедливо для любого целого числа больше 1!
Вот геометрический пример: кто-то заметил, что каждый многоугольник с n сторонами можно разделить на n — 2 треугольника. Опять же, вы никогда не сможете проверить каждый многоугольник, но вам не обязательно. Индукция позволяет вам это доказать.Вот набросок доказательства. Можете ли вы заполнить подробности?
В этом случае базовый вариант будет четырехугольником, или многоугольники с четырьмя сторонами. Нарисуйте одну диагональ и разрежьте ее на 2 треугольника. (Убедитесь, что вы верите, что можете сделать это для каждого четырехугольника — иногда диагональ выпадает за пределы фигуры. Что тогда?)
Теперь предположим, что для каждого многоугольника с n — 1 стороной вы можете разрезать их на (n-1) -2 = n-2 треугольника. Теперь представьте себе многоугольник с n сторонами.
Найдите диагональ, образующую треугольник и (n — 1) -сторонний многоугольник. (Вы всегда можете это сделать?)
Вы можете разделить многоугольник со стороной (n-1) на n-3 треугольника. (Почему?)
Итак, общее количество треугольников равно (n — 3) = 1 = n — 2.
Дополнительные ресурсы
Вы можете попробовать свои силы в математической индукции проблемы — некоторые числовые, а некоторые нет — на странице «Проблемы с точкой» на Принцип математической индукции.Вы можете найти более серьезные проблемы для которых полезна индукция на http://www.geocities.com/jespinos57/induction.htm.
Дополнительная информация и задачи по математической индукции можно найти на http://www.math.csusb.edu/notes/proofs/pfnot/node10.html и http://www. cut-the-knot.com/induction.html и в статьях «Преподавание математической индукции: альтернатива Подход »и« Когда не хватает памяти »в сентябре 2001 г. выпуск учителя математики.
Математический вводный курс — Основы математики
千里之行，始於足下
Путешествие в тысячу миль начинается с одного шага.
Лао-Цзы
Многие математические утверждения верны {\ em для любого натурального числа}. Например.
Основная теорема арифметики. Каждое натуральное число имеет уникальное разложение на простые числа.
Теорема. Каждое натуральное число бывает четным или нечетным.
Правило мощности для дифференциации. Для любого натурального числа.
Наше первое использование определения (кроме доказательства арифметических фактов) будет заключаться в установлении способа доказательства подобных утверждений. Но для этого нам нужно убедиться, что наше определение достаточно формально, чтобы служить основой доказательства. Для этого мы сосредоточимся на структуре задействованных открытых предложений. Поскольку нас интересуют только утверждения, которые каким-то образом включают натуральные числа, мы будем предполагать, что переменные, с которыми мы имеем дело, представляют натуральные числа, если не указано иное.То есть, мы берем Вселенную, чтобы все было до дальнейшего уведомления.
Определение. Мы называем открытое предложение индуктивным , если оно имеет свойство:.
Мы можем думать об индуктивных предложениях как о представлении наследственных свойств, то есть они передаются наследникам. Например, быть королевским — это свойство индукции.
Используя это определение, мы можем сформулировать аксиому 5 натуральных чисел как формальное символическое предложение.(Если вы помните, мы сформулировали первые четыре аксиомы как формальные символические предложения, а пятую аксиому оставили только в терминах слов. ) Вот:
Аксиома индукции. Позвольте быть открытое предложение, переменная которого представляет собой натуральное число. Предположим, что:
верно, а
— индуктивный.
Тогда.
В этой версии все еще есть несколько слов, но мы могли бы сделать их чисто символическими:
Чтобы увидеть, что эта версия такая же, как и более многословная версия, которую мы давали ранее, давайте примем, что « может быть достигнуто из 1 последовательностью ».Понятно, что это индуктивно: если может быть достигнуто из 1 последовательностью, то может и его преемник. Ясно, что 1 может быть достигнута из 1 с помощью (n чрезвычайно короткой) последовательности последовательностей. Таким образом, удовлетворяет обоим критериям — Индуктивная аксиома гласит: « любое натуральное число может быть получено из 1 последовательностью ».
Индуктивная аксиома также известна как Принцип математической индукции , или для краткости PMI . Это двигатель, который позволит нам доказывать множество утверждений формы, потому что это вывод PMI.
Чтобы использовать PMI таким образом, вам необходимо следующее:
определить, что такое
проверьте, что это правда (мы называем это «базовым случаем»)
показать, что индуктивно, что означает доказать (мы называем это «индуктивным шагом»)
К счастью, мы уже знаем, как доказывать универсальные утверждения, и мы уже знаем, как доказывать условные утверждения. Итак, общий план доказательства по индукции выглядит следующим образом:
Доказательство. (по индукции)
базовый вариант:. [установить]
шаг индукции: Позвольте быть натуральным числом. Предположение верно.
[. . . здесь идет некоторая работа. . .] Сделайте вывод.
Давайте напишем пример доказательства по индукции, чтобы показать, как работает эта схема. Я заключу свой комментарий в синие скобки.
Прет. Я могу добраться до любой ступеньки любой лестницы, стоящей на земле.
Доказательство. Если есть лестница, мы покажем, что любому я могу достичь ступеньки этой лестницы.(Вот утверждение: «Я могу достичь ступеньки лестницы».)
Я могу добраться до первой ступеньки, сделав шаг — в конце концов, лестница стоит на земле. (Мы только что доказали.)
А теперь предположим, что я стою на перекладине. (Это предположение.) Затем я могу сделать шаг (это «пикантные кусочки» доказательства.) И перейти к шагу. (Мы пришли к выводу.)
Согласно принципу математической индукции, это показывает, что мы можем достичь любой ступени лестницы.
Вот пример, где стоит «более математически».
Прет. Для любого натурального числа.
Доказательство. ( базовый вариант ) Когда, левая сторона. Правая часть есть. Так что равенство верно, когда.
( шаг индукции ) Позвольте быть натуральным числом. Предполагать . Рассмотрим левую часть:
Здесь мы использовали предположение.
Сейчас работаем над правой частью:
Поскольку левая и правая части равны, они равны друг другу.То есть верно. На этом индуктивный шаг завершен.
По принципу математической индукции мы доказали это требование. .
Здесь следует отметить несколько моментов. Во-первых, базовый вариант обычно довольно очевиден. Во-вторых, самая интересная (то есть сложная) часть доказательства — это выяснить, как использовать, чтобы получить.
Не всегда очевидно, что такое натуральное число (или индуктивная переменная ). Часто это размер чего-то (поскольку натуральные числа нужны для счета!).Если ваша индуктивная переменная не очевидна из постановки задачи, это хороший способ сообщить читателю, что вы будете вводить.
Прет. Каждый конечный набор действительных чисел имеет наименьший элемент.
Доказательство. Мы продолжим индукцию по размеру набора.
( базовый вариант ) Предположим, что в наборе ровно один элемент. Тогда этот элемент наименьший.
( шаг индукции ) Предположим, мы доказали, что любой набор действительных чисел с точно различными элементами имеет наименьший элемент.Мы покажем, что любой набор действительных чисел с точно различными элементами имеет наименьший элемент.
Позвольте быть таким набором, и обозначьте его элементы. Есть два варианта того, как это связано с другими элементами набора.
футляр : для всех. Тогда это минимум.
case : Есть такие с. Затем рассмотрим набор, состоящий из всех s, кроме. имеет ровно элементы, поэтому по нашему индуктивному предположению существует наименьший элемент из (назовем его).Тогда так тоже меньше всего.
В любом случае имеет наименьший элемент, что завершает индуктивный шаг, следовательно (согласно PMI) доказательство.
Индукция обобщенная
Теперь рассмотрим следующее:
Прет. Если я стою в окне второго этажа, я могу добраться до любой ступеньки любой лестницы, стоящей на земле, при условии, что эта ступенька является хотя бы ступенькой.
Форма претензии:, или.
Доказательство. Так как я нахожусь в окне второго этажа, я могу выйти на ступеньку.(Доказать.)
Теперь, если я нахожусь на любой ступеньке, я могу сделать шаг, чтобы перейти на следующую ступеньку. (Докажите, что это гарантирует.)
Так что независимо от того, на какую ступень (выше) я хочу попасть, я могу. .
Эту технику запуска с места, отличного от 1, иногда называют обобщенной индукцией , но на самом деле она не заслуживает такого причудливого названия. Это обычная индукция, но начиная с некоторого числа, отличного от 1.
Питер Субер, «Математическая индукция»
В ходе обычной индукции мы исследуем некоторое количество частных случаев, а затем обобщать.
Бургер №1 в кофейне был жирным.
Бургер №2 в кофейне был жирным.
Бургер №3 в кофейне был жирным ….
Бургер №100 в кофейне был жирным.
Следовательно, , все гамбургеры в кофейнях жирные. (Или: следующий бургер в кофейне будет жирным.)
Сильная индукция отличается от действительных выводов в одном важном отношении: при индукции заключение содержит информацию, которой не было в предпосылках.Это источник неопределенности индукции. (И наоборот, выводы достоверны, потому что они тавтологично повторяют свои посылки.) Индукции усиливаются по мере накопления подтверждающих примеров. Но они никогда не принесут уверенности, пока не будут изучены все возможные случаи, и в этом случае они станут умозаключениями. Несмотря на наш опыт с 100 жирными бургерами в кофейнях, следующий может быть сухим и эластичным.
«Математическая индукция», к сожалению, названа, так как это однозначно форма дедукции.Однако у него есть определенное сходство с индукцией, что, скорее всего, и послужило причиной его названия. Это похоже на индукцию в том смысле, что она обобщает на весь класс из меньшей выборки. Фактически, образец обычно представляет собой образец один , а класс обычно бесконечный . Однако математическая индукция дедуктивна, потому что образец плюс правило для неисследованных случаев фактически дает нам информацию о каждом члене класса. Следовательно, вывод математической индукции не содержит больше информации, чем было скрыто в предпосылках.Таким образом, математическая индукция завершается с дедуктивной уверенностью.
Вы, вероятно, совершенно уверены, что каждое четное число делится на 2. Но вы никогда не проверяли каждое четное число, и никто другой не проверял. Так как же узнать, что какое-то очень большое четное число не нарушит это правило? Почему ситуация не аналогична гамбургерам в кофейнях? В обоих случаях разве мы не переходим от известных случаев к неизвестным?
Причина, по которой четные числа решительно отличаются от гамбургеров в кофейнях, кроется в логике математической индукции. Мы можем доказать, что наименьшее четное число (а именно, 2) делится на 2. Это наша очень маленькая выборка. И мы можем доказать, что следующее четное число после каждого числа, делящегося на 2, также будет делиться на 2. Это наше правило в отношении неисследованных случаев. Этого достаточно, чтобы подразумевать, что преемник 2, а именно 4, будет делиться на 2, а его преемник — 6, а его преемник — 8 … и так далее до бесконечности . Вот как небольшая выборка и правило о нерассмотренных случаях могут дать нам информацию о каждом случае.Таким образом, наши знания о бесконечном множестве неисследованных случаев могут быть столь же достоверными, как и вывод действительной дедукции, в отличие от заключения обычной индукции.
Масштабная структура доказательства с помощью математической индукции довольно проста.
Теорема верна для образца. (Это требует отдельного доказательства.)
Правило говорит нам, что если оно верно для выборки, то оно верно для непроверенных членов определенного класса. (Это правило требует отдельного доказательства.)
Следовательно, теорема верна для всех членов определенного класса.
Вот как выглядит вывод, описанный в специальной терминологии математической индукции.
Основа . Докажите, что теорема верна в минимальном случае.
Индукционный ступень . Докажите, что свойство соблюдения теоремы «наследственно» и распространяется на всех последователей минимального случая.
Шаг индукции — это доказательство условного утверждения, а именно: «Если теорема верна для случая-предка, то она верна для случаев-потомков». Предложение if этого условного оператора, утверждающее, что теорема является верной для случая предка, называется гипотезой индукции .
Заключение . Вместе, №1 и №2 означают, что теорема верна для всех возможных случаев, т.е.е., минимальный случай и все его последователи. Если вы не использовали истинный минимальный случай на шаге № 1, то вы доказываете только, что теорема верна для этого случая и его последователей, а не для всех возможных случаев.
Индукционная ступень — это та часть, которая вызывает наибольшие трудности. Он может принимать две формы, которые соответствуют двум формам математической индукции:
Слабый : докажите, что , если , теорема верна для всех случаев в произвольной точке n , затем это справедливо для всех случаев в точке n + 1 .
Strong : докажите, что , если , теорема верна для всех случаев от до некоторой произвольной точки n , затем it справедливо для всех случаев в точке n + 1 .
Или, если T _n означает, что теорема верна для случая n , то гипотеза индукции для слабой математической индукции утверждает
т _н
, а для сильной математической индукции
(Т ₀ · Т ₁ · Т ₂ ·. .. · Т _№).
Обратите внимание, что шаг индукции заключается в доказательстве условного утверждения, для которого предположение индукции является антецедентом. Например, в слабой форме нам не нужно доказывать, что теорема действительно верна для произвольного случая n , просто , если , она верна для n , , то , она также верна для n + 1 .
Или нам не нужно доказывать T _n, просто T _n T _{n + 1}.
Это значительно упрощает доказательство. Для доказательства условного утверждения мы можем принять антецедент (предположение индукции) и вывести следствие. Мы можем завершить шаг индукции, приняв T _n и получив из него T _{n + 1}.
Вот схематический набросок типичного доказательства с помощью математической индукции.
Теорема верна для минимального случая.
Это основа; будем считать, что это уже доказано.
Теорема верна для произвольного случая n .
Это гипотеза индукции. Предполагается ради условного доказательства; нам не нужно это доказывать.
Промежуточные шаги …
Теорема верна для случая n + 1 .
Не предполагается, но получено из шагов ## 2-3.
Если теорема верна для n , , тогда она верна для n + 1 .
Это индукционная ступень; шаг №2 является его предшествующим, №4 — его следствием. Это следует «условным доказательством» из шагов 2–4. Мы сделали предположение в № 2, вывели промежуточное заключение в № 4 и теперь опровергаем это предположение, утверждая, что предположение подразумевает промежуточное заключение.
Следовательно, теорема верна для всех возможных случаев.
По математической индукции. Базовый случай был доказан в # 1, а индукция шаг в # 5.
Возможно, само собой разумеется, что если мы собираемся использовать математическую индукцию для доказательства того, что некоторая теорема применима ко «всем возможным случаям», то эти случаи должны быть каким-то образом перечислимы и тесно связаны с последовательными целыми числами. Мы должны иметь возможность говорить о минимальном случае , n-м случае и преемнике данного случая. Так что это идеально подходит для доказательства теоремы о самих целых числах. Теорема о том, что все четные числа делятся на 2, очевидно, имеет минимальный случай, а именно 2, и каждый случай (четное число) явно имеет преемника (следующее четное число).Мы не могли использовать математическую индукцию, чтобы доказать, что все хакеры пахнут пиццей.
Иногда требуется изобретательность, чтобы увидеть, как математическая индукция может применяться к предмет. Если вы хотите доказать, что некоторые виды результатов нельзя доказать, тогда не сразу ясно, может ли помочь математическая индукция; но может. Минимальный случай доказательства — это одношаговое доказательство. Шаг индукции докажет, что если рассматриваемые результаты не могут быть доказаны в n -шаговых доказательствах, то они не могут быть доказаны в n + 1 -шаговых доказательствах.Вывод состоит в том, что такие результаты не могут быть доказаны никакими доказательствами.
Если задуматься, возможно, мы могли бы доказать, что все хакеры пахнут пиццей. В базовом случае мы доказываем, что все хакеры с нулевым IQ пахнут пиццей. Гипотеза индукции утверждает, что , если хакер с IQ n пахнет пиццей, то хакер с IQ n + 1 пахнет пиццей.
Математическая индукция — обзор
Теорема 6.1.
Пусть C — класс PRC. Если f ( t , x ₁,…, x _n ) принадлежит C, то функции
g (y, x1,…, xn) = ∑t = 0yf (t, x1,…, xn)
и
h (y, x1,…, xn) = ∏t = 0yf (t, x1,…, xn) ⋅
Распространенной ошибкой является попытка доказать это с помощью математической индукции по г. Небольшое размышление показывает, что такой аргумент по индукции показывает, что
g (0, x1,…, xn), g (1, x1,…, xn),…
все принадлежат C, но не то, что функция g ( y, x ₁, …, x _n), , один из аргументов которого равен y , принадлежит C
Мы продолжаем правильное доказательство.
Доказательство. Отметим рекурсивные уравнения
g (0, x1,…, xn) = f (0, x1,…, xn), g (t + 1, x1,…, xn) = g (t, x1,… , xn) + f (t + 1, x1,…, xn),
и напомним, что, поскольку + примитивно рекурсивно, он принадлежит C. Аналогично,
h (0, x1,…, xn) = f ( 0, x1,…, xn), h (t + 1, x1,…, xn) = h (t, x1,…, xn) ⋅f (t + 1, x1,…, xn) ⋅
Иногда мы мы захотим начать суммирование (или произведение) с 1 вместо 0. То есть мы захотим рассмотреть
g (y, x1,…, xn) = ∑t = 1yf (t, x1,…, xn)
или
h (y, x1,…, xn) = ∏t = 1yf (t, x1,…, xn) ⋅
Тогда исходные рекурсивные уравнения можно принять равными
g (0, x1, …, Xn) = 0, h (0, x1,…, xn) = 1,
с уравнениями для g ( t + 1, x ₁, …, x _n ) и h ( t + 1, x ₁, …, x _n ), как в предыдущем доказательстве. Обратите внимание, что мы неявно определяем, что пустая сумма равна 0, а пустое произведение — 1. С таким пониманием мы доказали
Теорема 6.3.
Если предикат P ( t, x ₁,…, x _n ) принадлежит некоторому классу PRC C, то предикаты ⁴
(∀t) ≤yP (t , x1,…, xn) и (∃t) ≤yP (t, x1,…, xn) ⋅
Доказательство. Нам нужно только заметить, что
(∀t) ≤yP (t, x1,…, xn) ⇔ [∏t = 0yP (t, x1,…, xn)] = 1
и
(∃t) ≤yP (t, x1,…, xn) ⇔ [∑t = 0yP (t, x1,…, xn)] ≠ 0⋅
На самом деле для универсального квантора было бы даже правильно написать уравнение
( ∀t) ≤yP (t, x1,…, xn) = ∏t = 0yP (t, x1,…, xn) ⋅
Иногда при применении теоремы 6.3 мы хотим использовать квантор
(∀t)
То, что теорема все еще верна, ясно из соотношений
(∃t)
Продолжаем наш список примеров.
12. y | x
Это предикат «y является делителем x ». Например,
3 | 12 истинно
, а
3 | 13 ложно
Предикат примитивно рекурсивен, поскольку
y | x⇔ (∃y) ≤y (y⋅t = x) ⋅
13. Prime ( x )
Предикат « x — простое число» является примитивно рекурсивным, поскольку
Prime (x) ⇔x> 1 & (∀t) ≤x {t = 1∨t = x∨∼ ( t | x)} ⋅
(Число представляет собой простое число , если оно больше 1 и не имеет делителей, кроме 1 и самого себя.)
Принцип математической индукции — MyRank
Что такое индукция по математике?
Математическая индукция — это особый метод или техника для доказательства утверждений, данных при рассмотрении.Как правило, он используется для доказательства утверждений о множестве натуральных чисел. Принцип математической индукции:
Математическая индукция используется, чтобы доказать, истинно данное утверждение или нет. Чтобы доказать это, требуется 2 шага.
Первый принцип математической индукции :
Базовый случай : Данное утверждение верно для первого натурального числа, то есть для n = 1 верно p (1).
Индуктивный шаг : Если данное утверждение верно для любого натурального числа, такого как n = k, тогда оно будет правильным и для n = k + 1, то есть, если p (k) истинно, то p (k + 1) будет тоже быть правдой.Первый принцип математической индукции гласит, что если оба вышеуказанных шага доказаны, то p (n) истинно для всех натуральных чисел.
Второй принцип математической индукции: Он более мощный, чем первый принцип. Иногда это называют сильной индукцией. В особом случае базовый вариант не требуется, в противном случае может потребоваться показать более одного базового случая. На рекурсивном шаге, чтобы доказать, что k + 1 истинно, сначала нам нужно доказать, что утверждение также верно для всех чисел меньше k + 1.
Первый принцип математической индукции :
Математическая индукция может быть доказана в четыре этапа:
1. Шаг : Показать значение p (1) верно. Пусть n = 1 и решите.
2. Шаг : (гипотеза индукции ) Предположим, что p (k) верно. Пусть n = k и решите.
3. шаг : (индукция ) Показать, если p (k) истинно, то p (k + 1) также истинно. Пусть n = k + 1 и решит.
Напишите доказательство того, что p (n) истинно.
Пример: Докажите, что для любого натурального числа n сумма n натуральных чисел равна \ (\ frac {n (n + 1)} {2} \)
Решение: Учитывая утверждение, которое нам нужно доказать
\ (1 + 2 + 3 + …………… .. + n = \ frac {n (n + 1)} {2} \)
Шаг 1: Базовый шаг
Покажите, что утверждение верно для n = 1
\ (1 = \ frac {1 (1 + 1)} {2} = \ frac {2} {2} = 1 \)
Поскольку LHS = RHS
Это показывает, что p (1) верно.