Метод математической индукции – МАТЕМАТИКА
При доказательстве тождеств или тождественных неравенств, обе части которых зависят от натурального аргумента, часто применяют метод математической индукции.
В основе этого метода лежит принцип математической индукции.
Если первый человек в очереди — женщина, и за каждой женщиной стоит женщина, то все в очереди — женщины.
Рассуждение, заключенное в этом шуточном примере, часто встречается в самых разных областях математики и носит название принципа математической индукции. Более серьезная формулировка этого принципа такова:
Имеется последовательность утверждений. Если первое утверждение верно, и за каждым верным утверждением следует верное, то все утверждения в последовательности верны.
Пример 1. Пусть нужно доказать формулу .
Эта формула содержит целую последовательность утверждений:
1) ;
2) ;
3) ;
4) ;
Первое утверждение, разумеется, верно.
Пусть утверждение k) верно, то есть равенство справедливо.
Теперь прибавим к обеим частям равенства число . Получим
.
Но это как раз и есть утверждение , которое следует за утверждением .
Мы доказали, таким образом, что за каждым верным утверждением следует верное. В силу принципа математической индукции, наша формула верна при любом .
Эту же задачу можно решить и без использования метода математической индукции. обозначим сумму, которую мы хотим найти, через . Напишем два равенства
(в нижней строке написана та же сумма, что и в первой, но записанная в обратном порядке). Если сложим почленно строки, то получим
,
и наше равенство доказано.
Приведем еще одну формулировку принципа математической индукции, немного отличную от первой.
Пусть имеется какое-нибудь предположение, или, как еще говорят, гипотеза, и мы хотим проверить справедливость этой гипотезы для всех натуральных .
Допустим, что удалось доказать такие два утверждения:
а) Наша гипотеза справедлива при .
б) Из того, что эта гипотеза верна при , где — произвольное натуральное число, следует, что она верна и при .
Принцип математической индукции состоит в том, что из утверждения а) и б) следует справедливость нашей гипотезы для всех натуральных чисел .
Утверждение б) носит условный характер. В нем не утверждается, что гипотеза верна для . Оно состоит лишь в том, что если наша гипотеза верна, для , то она верна и для .
Мы будем называть б) индуктивным предположением.
Пример. Докажем, что для любого натурального число делится на .
Проведем доказательство методом математической индукции.
а) При выражение равно нулю и, значит, делится на .
б) Пусть — произвольное натуральное число. Покажем, что если при число делится на , то тоже делится на .
Используя равенство
,
представим число в виде
.
Мы представили число в виде суммы двух слагаемых. Первое их них, , делится на 5 по нашему предположению. Второе слагаемое , также делится на 5. Сумма двух чисел делится на 5, так как каждое слагаемое делится на 5, т.е. делится на 5.
Итак, утверждения а) и б) доказаны. Значит, по принципу математической индукции число делится на 5 при всех натуральных .
Существуют другие формулировки принципа математической индукции, эквивалентные данным нами. Вот одна из них:
Если:
а) некоторое утверждение верно при ;
б) из того, что оно верно для всех , следует, что оно верно и для , то это утверждение верно для всех .
Отличие этой формулировки от предыдущей состоит в следующем.
В пункте б) мы требуем, чтобы наше утверждение было справедливо для всех , а не только для .
Легко сообразить, что обе формулировки принципа математической индукции эквивалентны в том смысле, что всякая теорема, которую можно доказать, применяя метод индукции в одной форме, может быть доказана и с помощью другой его формы.
Заметим также, что доказательство утверждения а) нужно, так сказать, лишь для «затравки». Если вместо него доказать утверждение
а’) о том, что наша гипотеза справедлива, скажем, для , а пункт б) оставить неизменным, то из утверждений а’) и б) будет следовать, что наша гипотеза верна для всех натуральных , начиная с восьми.
Метод математической индукции позволит нам более основательно познакомиться с арифметической и геометрической прогрессией, выводом многих формул. Также метод математической индукции часто встречается при решении олимпиадных задач.
Метод математической индукции
Разве ты не заметил, что способный к математике
изощрен во всех науках в природе?
Древнегреческий философ Платон
Метод математической индукции
В математической подготовке старшеклассников слабым местом является неумение учащихся доказывать теоремы, неравенства и другие утверждения.
Главное объяснением этому является отсутствие задач на доказательство в заданиях вступительных испытаний. Так как среднее образование ориентировано, в первую очередь, на успешное решение заданий ЕГЭ (Россия) и ЦТ (Беларусь), то изучению различных методов доказательства в общеобразовательной школе уделяется, в лучшем случае, мало внимания.
К числу «классических» методов доказательства относится метод математической индукции, который может успешно применяться во многих разделах как школьной, так и высшей математики. Знание метода математической индукции является неотъемлемой частью математической культуры выпускников современных школ и гимназий.
Описание метода
Метод математической индукции является одним из наиболее часто встречающихся методов в математике. Допустим требуется доказать некоторое утверждение , которое содержит целочисленный (индукционный) параметр , где . Наиболее часто в качестве параметра используются натуральные числа.
Непосредственная проверка утверждения для каждого конкретного значения невозможна, поскольку множество натуральных чисел бесконечно.
Метод математической индукции выполняется в три этапа.
На первом этапе необходимо убедиться в справедливости утверждения для начального значения параметра , т.е. необходимо убедиться в справедливости утверждения . Данный этап метода называется базой (базисом) индукции.
На втором этапе предполагается, что утверждение справедливо при условии, что . Этот этап метода называется индукционным предположением.
Если на третьем этапе будет доказано утверждение , то справедливость утверждения будет иметь место для произвольного значения . Отметим, что выполнение третьего этапа метода обычно является наиболее трудоемкой частью метода.
Ниже предлагаются примеры задач, решение которых осуществляется методом математической индукции.
Примеры решения задач
Пример 1.
Доказать, что
, (1)
где .
Доказательство. Обозначим .
Пусть , тогда и из формулы (1) следует .
Предположим, что
. (2)
Теперь требуется убедиться в том, что формула (1) выполняется и при , т.е. надо показать, что
. (3)
Из формул (1) и (2) получаем
, или .
Отсюда следует формула (3). Следовательно, утверждение (1) доказано.
Пример 2. Доказать, что
, (4)
где .
Доказательство.
Обозначим .
Пусть , тогда и .
Пусть и справедлива формула
. (5)
Пусть . Докажем, что или
. (6)
Так как , то с учетом индукционного предположения (5) получаем
.
Следовательно, формула (6) является доказанной, а рассматриваемое равенство (4) справедливо для произвольных значений .
Пример 3. Доказать, что
, (7)
где .
Доказательство. Обозначим .
Если , то и .
Предположим, что
. (8)
Докажем, что .
Из формул (7) и (8) следует, что
.
Отсюда вытекает справедливость формулы (7) для произвольных значений .
Пример 4. Если числовая последовательность является геометрической прогрессией, знаменатель которой равен , то
(9)
Доказательство. Обозначим .
Если , то и
Пусть Необходимо показать, что
Так как и , то с учетом индукционного предположения имеем
,
или
Отсюда следует справедливость формулы (9).
Пример 5. Доказать, что
, (10)
где .
Доказательство.
Обозначим левую часть равенства (10) как .
Если , то и .
Пусть . Покажем, что .
Из определения и равенства следует, что
. (11)
Если воспользоваться известной формулой ,
то из равенства (11) получим ,
или .
Отсюда, согласно принципу математической индукции, следует справедливость формулы (10).
Пример 6. Доказать, что
, (12)
где .
Доказательство. Обозначим .
Пусть . Тогда и .
Предположим, что , и покажем, что .
Поскольку , то ,
или .
Формула (12) доказана.
Пример 7.
Доказать неравенство
, (13)
где .
Доказательство. Обозначим .
Если , то , т.е. неравенство (13) выполняется.
Предположим, что . Покажем, что .
Так как и , то .
Очевидно, что для решения задачи требуется доказать неравенство
, (14)
которое выполняется для произвольных натуральных .
Доказательство неравенства (14) будем вести методом от противного. Допустим, что существуют такие значения , при которых выполняется противоположное неравенство, т.е. имеет место неравенство
. (15)
Преобразуем неравенство (15) следующим образом:
, или .
Поскольку получили числовое противоречие , то неравенство (14) верно. Тем самым доказано, что и неравенство (13) выполняется для любых значений , где .
Примечание. Проведя аналогичные рассуждения, можно доказать: если , то .
Пример 8. Доказать, что выражение кратно (делится на число без остатка), где .
Доказательство. Если , то . Очевидно, что в данном случае требуемое утверждение выполняется.
Пусть кратно . Покажем, что выражение также будет делиться на число без остатка.
Так как , то
, или . (16)
Согласно индукционному предположению, выражение кратно , поэтому из формулы (16) следует, что таковым будет и выражение .
В этой связи утверждение задачи доказано.
Пример 9.
Доказать, что для любого натурального выражение кратно .
Доказательство. Если , то и кратно . Предположим, что кратно . Убедимся в том, что также будет кратно .
Так как , то , или . (17)
Поскольку натуральное число, то выражение всегда принимает только четные значения. В этой связи выражение кратно . Согласно индукционному предположению кратно и поэтому из формулы (17) следует, что делится на число без остатка.
Утверждение задачи доказано.
Пример 10. Доказать, что число диагоналей выпуклого угольника равно
, (18)
где .
Доказательство. Из формулы (18) следует, что и . Действительно, треугольники диагоналей не имеют, а выпуклый четырехугольник имеет только две диагонали.
Следовательно, формула (18) выполняется для начальных значений индукционного параметра .
Предположим, что . Требуется доказать, что
. (19)
Рассмотрим выпуклый угольник , приведенный на следующем рисунке.
Нетрудно видеть, что или . Однако, согласно индукционному предположению угольник имеет диагоналей. В этой связи или . Отсюда вытекает формула (19).
Таким образом, доказана справедливость утверждения (18).
Для более глубокого изучения метода математической индукции, а также для решения задач, связанных с применением этого метода в различных разделах школьной математики, можно использовать учебные пособия, приведенные в списке рекомендуемой литературы.
Рекомендуемая литература
1. Виленкин Н.Я. Индукция. Комбинаторика. – М.: Просвещение, 1976. – 48 с.
2. Соминский И.С. Метод математической индукции. – М.: Наука, 1974. – 64 с.
3. Супрун В.П. Математика для старшеклассников: задачи повышенной сложности. – М.: КД «Либроком» / URSS, 2017. – 200 с.
Остались вопросы?
Чтобы получить помощь репетитора – зарегистрируйтесь.
© blog.tutoronline.ru, при полном или частичном копировании материала ссылка на первоисточник обязательна.
Математическая индукция — TOK RESOURCE.ORG
Рафаэль (1509–1511) Евклид Деталь из Афинская школа. Фреска. Апостольский дворец, Ватикан
«Математика, если ее правильно рассматривать, обладает не только истиной, но и высочайшей красотой — красотой холодной и суровой, как красота скульптуры, не затрагивающей ни одной части нашей слабой натуры, без великолепных атрибутов живописи или музыки, но возвышенно чистой и способный к суровому совершенству, которое может показать только величайшее искусство.— Рассел, Бертран (1919: 60) Мистицизм и логика: и другие очерки. Лонгман, Лондон.Истинный дух восторга, экзальтации, ощущение того, что ты больше, чем человек, что является пробным камнем высочайшего совершенства, можно найти в математике так же несомненно, как и в поэзии. Д
ЗАДАНИЕ ДЛЯ КЛАССА I: ПОСМОТРЕТЬ ТРЕУГОЛЬНИК ПАСКАЛЯ
Начните с того, что повторите вместе со всем классом закономерности, которые мы нашли в треугольнике Паскаля в пари Паскаля в разделе «Вера как путь познания». Все изображения с веб-сайта Math is fun.
ЗАДАНИЕ II КЛАССА: ПОСТРОИТЬ КАРТОЧНЫЙ ДОМИК
2, 5, 8… Количество карт, необходимых для каждого из первых трех уровней (рядов) Карточного домика.
Фото WikiHow
Заранее приготовьте несколько колод игральных карт и большое количество черновой/шероховатой бумаги.
Учащиеся должны работать в парах, чтобы построить классический Карточный домик.
Небольшой приз должен быть вручен паре с наибольшим количеством уровней, которые могут стоять в одиночестве не менее 10 секунд!
Следующие пары учащихся должны попытаться выполнить следующие задания:
1. Напишите, используя как можно меньше слов, грамматический абзац, содержащий подробные инструкции по сборке классического карточного домика.
2. Какой самый большой карточный домик можно построить из одной колоды карт?
3. Какой самый длинный ряд можно составить из одной колоды карт? (Не забудьте о горизонтальных крышках.)
4. Придумайте или откройте универсальную формулу для общего количества карт, необходимых для построения карточного домика из n рядов. Есть несколько подходов к этому. Будьте строги. Нарисуйте схему и представьте свое доказательство кратко и ясно. Будьте готовы представить свои выводы всему классу.
ГЛУБЖЕ
«Когда я еще ел на высоком стульчике, мой отец после обеда играл со мной в игру.— Фейнман, Ричард П.Он купил много странной прямоугольной плитки для пола в ванной где-то в Лонг-Айленд-Сити. Мы поставили их на один конец рядом с другим, и мне разрешили нажать на крайний и смотреть, как все это рушится…
Далее игра улучшилась. Плитка была разного цвета. Я должен поставить одну белую, две голубые, одну белую, две голубые и еще одну белую, а потом две голубые… Вы уже узнаете обычную коварную ловкость; сначала доставьте ему удовольствие игрой, а затем постепенно вводите материал, имеющий воспитательную ценность! Ну, а моя мать, женщина гораздо более чувствительная, начала осознавать коварство его стараний и сказала: «Мел, пожалуйста, пусть бедный ребенок положит синюю плитку, если он хочет». Мой отец сказал: «Нет, я хочу, чтобы он обращал внимание на закономерности. Единственное, что я могу сделать, это математика на этом самом раннем уровне». Если бы я выступал с докладом на тему «Что такое математика?» Я бы уже ответил вам. Математика ищет закономерности. Д
(1999) Удовольствие от выяснения вещей: лучшие короткие произведения Ричарда П. Фейнмана. Персей, Кембридж, Массачусетс. СПЕЦИАЛЬНЫЙ СЛУЧАЙ МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
Студенты уже встречались с нобелевским лауреатом по физике Ричардом Фейнманом в теории неведения и воображения (с ограничениями) и жизни в сослагательных наклонениях, как в способах познания. Студент-волонтер должен прочитать вслух свою ироничную цитату о том, как он учился математике в раннем детстве. Спросите учащихся, откликнулось ли на них его определение математики, когда они работали над заданием «Карточный домик».
По крайней мере, две группы студентов-добровольцев изложат свое мнение о расследовании «Карточного домика». Будет интересно увидеть различные стратегии, принятые сотрудничающими парами, и то, как они уложились в отведенное время.
Интригующий ключ к нахождению общего правила для Карточного домика скрыт в диагоналях треугольника Паскаля. Числа треугольника являются ключом к разгадке головоломки.
Вполне вероятно, что некоторые студенты обнаружат это, и это всплывет во время презентаций и обсуждений. На первый взгляд нет ничего проще, чем треугольные числа. Вы получаете их, складывая счетные числа. Общая формула:
Вы можете найти выражение вспышкой блестящего озарения или, что более вероятно, упорным методом проб и ошибок! Когда вы систематически выкладываете числовые закономерности, вы должны в конце концов заметить, что если вы возьмете любое счетное число: прибавите к нему единицу, умножите его само на себя, а затем разделите все на два, вы получите правильную совокупную сумму (вашего числа и его предшественники) каждый раз.
Но пробы и ошибки, конечно, не доказательство! Это обычное индуктивное рассуждение, когда мы начинаем с множества отдельных случаев и создаем общее правило. Проблема с регулярной индукцией заключается в том, что она работает психологически, но ей не хватает достоверности надежной логики.
Правило рушится, как только найден единственный контрпример. Как бы тривиально это ни звучало в случае сложения счетных чисел, просто нецелесообразно проверять каждый случай. Пример с черным лебедем, который мы рассмотрели в разделе «Индукция и дедукция», был яркой иллюстрацией ловушек индукции. Это было проблематично для предварительных знаний о реальном мире естественных наук и вряд ли послужит строгому совершенству абстрактной математики
К счастью, на помощь приходит частный случай математической индукции! Это несколько сбивает с толку, потому что математическая индукция на самом деле представляет собой особый вид дедуктивных рассуждений с некоторыми очень специфическими приложениями, такими как арифметические ряды, и очень удобна для исследований, таких как Карточный домик.
Доказательство с помощью математической индукции состоит из двух частей:
1. Показать , что выражение верно для основного (наименьшего) случая.
2.
Предположим , что выражение верно для любого случая n. Постройте на этом предположении , показывая , который действителен для случая n + 1.
Это видео Академии Кана содержит тщательное и удовлетворительное изложение доказательства.
РАЗЛОЖЕНИЕ КАРТОЧНОГО ДОМИКА
Теперь должно быть ясно, что каждый ряд в Карточном домике требует n пар подставок плюс n — 1 горизонтальных крышек. Поскольку нас интересует общее количество карт, оно сводится к n-му количеству треугольников пар плюс n — 1 треугольному количеству крышек:
PDF-файл с цитатами и задачами Фейнмана для печати.
Фрагмент «Элементов» Евклида: из Оксиринхского папируса, извлеченного из древнеегипетской свалки!
|
Предыдущая: Резюме Следующая: Основные случаи |
Что должен знать каждый студент CMPT 225 о математической индукции
— Брэд Барт, Университет Саймона Фрейзера | |
| |
||
Часть 1: Обзор индукции
|
Часть 1: Обзор математической индукции
Вы завершили последний раздел незавидной задачей доказать ваша претензия: . Как бы вы ни были убеждены в шаблоне, Брэд в этом не уверен.
К счастью, вы помните математический трюк, который вы видели в исчислении, известный как метод разностей . Поскольку вы считаете, что ваш вывод верен, вы считаете н 2 , и рассчитать значение, которое вам нужно добавить к нему, чтобы достичь ( n + 1) 2 . То есть, разница ( n + 1) 2 − n 2 . Поскольку разница 2 n + 1, что именно п + 1 ст член в сумме, у вас есть доказано, что ваша закрытая форма сохраняется для постепенного увеличения целые числа п . Итак, вы идете в класс CMPT 225 зная, что вы не только решили проблему, но и полностью Бред тоже.
Что вы действительно сделали, используя метод разностей, так это
своего рода доказательство по индукции , которое, если вы помните
вступительный абзац, работает со структурами, которые
самоподобный .
Технический термин для этого — индуктивный шаг : , чтобы использовать проверенные меньшие структуры для проверки больших структуры. Каждая из меньших структур называется индуктивная гипотеза . В простой индукции , такой как эта, индуктивная шаг показывает, что n th если вы проверить будет означать № + 1 st кейс. | |
| В сильной индукции индуктивный шаг может использовать любое сочетание подтвержденных случаев, т. е. 1 ст , 2 й , 3 рд , . . ., n th дел, для того, чтобы подразумевать н + 1 ст кейс. |
Ясно, что простая индукция есть частный случай сильной индукции.
| |
. . О математической индукции 
Проверка в каждом конкретном случае, т. е. путем подстановки
n = 1, 2, 3, . . .,
не будет
быть эффективным методом доказательства, если только
у вас есть бесконечное количество времени в ваших руках.
В данном случае вы использовали
n -term сумма
для создания
( n + 1)-членная сумма
добавив
н + 1 ст срок. Или, алгебраически,