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

Метод математической индукции Вступление Основная часть 1. Полная и неполная индукция 2. Принцип математической индукции 3. Метод математической индукции 4. Решение примеров 5. Равенства 6. Деление чисел 7. Неравенства Заключение Список использованной литературы Вступление В основе всякого математического исследования лежат дедуктивный

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

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

Основная часть По своему первоначальному смыслу слово индукция применяется к рассуждениям, при помощи которых получают общие выводы, опираясь на ряд частных утверждений. Простейшим методом рассуждений такого рода является полная индукция. Вот пример подобного рассуждения. Пусть требуется установить, что каждое натуральное чтное число n в пределах 4 n 20 представимо в виде суммы двух простых чисел.

Для этого возьмм все такие числа и выпишем соответствующие разложения 422 633 853 1073 1275 1477 16115 18135 20137. Эти девять равенств показывают, что каждое из интересующих нас чисел действительно представляется в виде суммы двух простых слагаемых. Таким образом, полная индукция заключается в том, что общее утверждение доказывается по отдельности в каждом из конечного числа возможных случаев. Иногда общий результат удатся предугадать после рассмотрения не всех, а достаточно большого числа частных

случаев так называемая неполная индукция. Результат, полученный неполной индукцией, остается, однако, лишь гипотезой, пока он не доказан точным математическим рассуждением, охватывающим все частные случаи. Иными словами, неполная индукция в математике не считается законным методом строгого доказательства, но является мощным методом открытия новых истин. Пусть, например, требуется найти сумму первых n последовательных нечтных чисел. Рассмотрим частные случаи 1112 13422 135932 13571642 135792552

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

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

нужно доказать, что сумма первых n нечтных чисел равна n2. Непосредственная проверка этого утверждения для каждого значения n невозможна, поскольку множество натуральных чисел бесконечно. Чтобы доказать это утверждение, проверяют сначала его справедливость для n1. Затем доказывают, что при любом натуральном значении k из справедливости рассматриваемого утверждения при nk вытекает его справедливость и при nk1. Тогда утверждение считается доказанным для всех n.

В самом деле, утверждение справедливо при n1. Но тогда оно справедливо и для следующего числа n112. Из справедливости утверждения для n2 вытекает его справедливость для n13. Отсюда следует справедливость утверждения для n4 и т.д. Ясно, что, в конце концов, мы дойдм до любого натурального числа n. Значит, утверждение верно для любого n. Обобщая сказанное, сформулируем следующий общий принцип.

Принцип математической индукции. Если предложение Аn, зависящее от натурального числа n, истинно для n1 и из того, что оно истинно для nk где k-любое натуральное число, следует, что оно истинно и для следующего числа nk1, то предположение Аn истинно для любого натурального числа n. В ряде случаев бывает нужно доказать справедливость некоторого утверждения не для всех натуральных чисел, а лишь для n p, где p-фиксированное натуральное число.

В этом случае принцип математической индукции формулируется следующим образом. Если предложение Аn истинно при np и если АkАk1 для любого k p, то предложение Аn истинно для любого n p. Доказательство по методу математической индукции проводиться следующим образом. Сначала доказываемое утверждение проверяется для n1, т.е. устанавливается истинность высказывания А1. Эту часть доказательства называют базисом индукции.

Затем следует часть доказательства, называемая индукционным шагом. В этой части доказывают справедливость утверждения для nk1 в предположении справедливости утверждения для nk предположение индукции, т.е. доказывают, что АkAk1. ПРИМЕР 1 Доказать, что 1352n-1n2. Решение 1 Имеем n112. Следовательно, утверждение верно при n1, т.е.

А1 истинно. 2 Докажем, что АkAk1. Пусть k-любое натуральное число и пусть утверж-дение справедливо для nk, т.е. 1352k-1k2. Докажем, что тогда утверждение справедливо и для следующего натурального числа nk1, т.е. что 1352k1k12. В самом деле, 1352k-12k1k22k1k12. Итак, АkАk1. На основании принципа математической индукции заключаем, что предпо-ложение Аn истинно для любого nN. ПРИМЕР 2 Доказать, что 1хх2х3хnхn1-1х-1, где х1

Решение 1 При n1 получаем 1хх2-1х-1х-1х1х-1х1 следовательно, при n1 формула верна А1 ис-тинно. 2 Пусть k-любое натуральное число и пусть формула верна при nk, т.е. 1хх2х3хkхk1-1х-1. Докажем, что тогда выполняется равенство 1хх2х3хkxk1xk2-1х-1. В самом деле 1хх2x3хkxk11xx2x3xkxk1 xk1-1x-1xk1xk2-1x-1. Итак, АkAk1. На основании принципа математической индукции заключаем, что форму-ла верна для любого

натурального числа n. ПРИМЕР 3 Доказать, что число диагоналей выпуклого n-угольника равно nn-32. Решение 1 При n3 утверждение спра- А3 ведливо, ибо в треугольнике А333-320 диагоналей А2 А3 истинно. 2 Предположим, что во всяком выпуклом k-угольнике имеет- А1 ся Аkkk-32 диагоналей. Аk Докажем, что тогда в выпуклом Аk1 k1-угольнике число диагоналей Аk1k1k-22. Пусть

А1А2А3AkAk1-выпуклый k1-уголь-ник. Проведм в нм диагональ A1Ak. Чтобы под-считать общее число диагоналей этого k1-уголь-ника нужно подсчитать число диагоналей в k-угольнике A1A2Ak, прибавить к полученному числу k-2, т.е. число диагоналей k1-угольника, исходящих из вершины Аk1, и, кроме того, следует учесть диагональ А1Аk. Таким образом, k1kk-21kk-32k-1k1k-22. Итак, АkAk1.

Вследствие принципа математической индукции утверждение верно для любого выпуклого n-угольника. ПРИМЕР 4 Доказать, что при любом n справедливо утвер-ждение 122232n2nn12n16. Решение 1 Пусть n1, тогда Х1121112161. Значит, при n1 утверждение верно. 2 Предположим, что nk Хkk2kk12k16. 3 Рассмотрим данное утвержде-ние при nk1 Xk1k1k22k36. Xk1122232k2k12kk12k16 k12kk12k16k126k1k2k1 6k16k12k27k66k12k32k 26k1k22k36.

Мы доказали справедливость равенства и при nk1, следовательно, в силу метода математиче-ской индукции, утверждение верно для любого на-турального n. ПРИМЕР 5 Доказать, что для любого натурального n спра-ведливо равенство 132333n3n2n124. Решение 1 Пусть n1. Тогда Х1131211241. Мы видим, что при n1 утверждение верно. 2 Предположим, что равенство верно при nk Xkk2k124. 3

Докажем истинность этого ут-верждения для nk1, т.е. Хk1k12k224. Xk11323k3k13k2k124k13k2k124k134k12k24k44 k12k224. Из приведнного доказательства видно, что ут-верждение верно при nk1, следовательно, равен-ство верно при любом натуральном n. ПРИМЕР 6 Доказать, что 23123-133133-1n31n3-13nn12n2n1, где n 2. Решение 1 При n2 тождество выглядит 23123-132322221, т.е. оно верно.

2 Предположим, что выражение верно при nk 23123-1k31k3-13kk12k2k1. 3 Докажем верность выражения при nk1. 23123-1k31k3-1k13 1k13-13kk12k2k1k2k 12-k11kk12k113k1k22 k12k11. Мы доказали справедливость равенства и при nk1, следовательно, в силу метода математиче-ской индукции, утверждение верно для любого n 2 ПРИМЕР 7 Доказать, что 13-2333-432n-13-2n3-n24n3 для любого натурального n. Решение 1 Пусть n1, тогда 13-23-1343 -7-7. 2 Предположим, что nk, тогда 13-2333-432k-13-2k3-k24k3. 3

Докажем истинность этого ут-верждения при nk1 13-232k-13-2k32k13-2k23-k24k3 2k13-2k23-k134k13. Доказана и справедливость равенства при nk1, следовательно утверждение верно для лю-бого натурального n. ПРИМЕР 8 Доказать верность тождества 12132235n22n-12n1nn122n1 для любого натурального n. Решение 1 При n1 тождество верно 1213111221. 2 Предположим, что при nk 1213k22k-12k1kk122k1. 3 Докажем, что тождество верно при nk1. 1213k22k-12k1k122k12k3kk122k1k122k12k3k1 2k1k2k12k3k1k2 2k122k12k3k1k222k11.

Из приведнного доказательства видно, что ут-верждение верно при любом натуральном n. ПРИМЕР 9 Доказать, что 11n2122n1 делится на 133 без остатка. Решение 1 Пусть n1, тогда 1131231112112-13212223133. Но 23133 делится на 133 без остатка, значит при n1 утверждение верно А1 истинно. 2 Предположим, что 11k2122k1 делится на 133 без остатка.

3 Докажем, что в таком случае 11k3122k3 делится на 133 без остатка. В самом деле 11k3122л31111k2122122k1k2 11133122k1k2122k1133122k1. Полученная сумма делится на 133 без остатка, так как первое е слагаемое делится на 133 без ос-татка по предположению, а во втором одним из множителей выступает 133. Итак, АkАk1. В силу метода математической индукции утвержде-ние доказано.

ПРИМЕР 10 Доказать, что при любом n 7n-1 делится на 6 без остатка. Решение 1 Пусть n1, тогда Х171-16 де-лится на 6 без остатка. Значит при n1 утвержде-ние верно. 2 Предположим, что при nk 7k-1 делится на 6 без остатка. 3 Докажем, что утверждение справедливо для nk1. Xk17k1-177k-7677k-16. Первое слагаемое делится на 6, поскольку 7k-1 делится на 6 по предположению, а вторым слага-емым является 6.

Значит 7n-1 кратно 6 при любом натуральном n. В силу метода математической ин-дукции утверждение доказано. ПРИМЕР 11 Доказать, что 33n-124n-3 при произвольном на-туральном n делится на 11. Решение 1 Пусть n1, тогда Х133-124-3322111 делится на 11 без остат-ка. Значит, при n1 утверждение верно. 2 Предположим, что при nk Xk33k-124k-3 делится на 11 без остатка. 3 Докажем, что утверждение верно для nk1.

Xk133k1-124k1-333k224k13333k-12424k-3 2733k-11624k-3161133k-11624k-31633k-1 1133k-11624k-31633k-124k-31133k-1. Первое слагаемое делится на 11 без остатка, поскольку 33k-124k-3 делится на 11 по предположе-нию, второе делится на 11, потому что одним из его множителей есть число 11. Значит и сумма де-лится на 11 без остатка при любом натуральном n. В силу метода математической индукции утвер-ждение доказано.

ПРИМЕР 12 Доказать, что 112n-1 при произвольном нату-ральном n делится на 6 без остатка. Решение 1 Пусть n1, тогда 112-1120 делится на 6 без остатка. Значит при n1 утвержде-ние верно. 2 Предположим, что при nk 112k-1 делится на 6 без остатка. 3 Докажем, что утверждение верно при nk1 112k1-1121112k-1120112k112k-1. Оба слагаемых делятся на 6 без остатка пер-вое содержит кратное 6-ти число 120, а второе де-лится на 6

без остатка по предположению. Значит и сумма делится на 6 без остатка. В силу метода математической индукции утверждение доказано. ПРИМЕР 13 Доказать, что 33n3-26n-27 при произвольном натуральном n делится на 262676 без остатка. Решение Предварительно докажем, что 33n3-1 делится на 26 без остатка. 1 При n0 33-126 делится на 26 2 Предположим, что при nk 33k3-1 делится на 26 3

Докажем, что утверждение верно при nk1. 33k6-12733k3-12633л333k3-1 делится на 26 Теперь проведм доказательство утвер-ждения, сформулированного в условии задачи. 1 Очевидно, что при n1 утвер-ждение верно 333-26-27676 2 Предположим, что при nk выражение 33k3-26k-27 делится на 262 без остатка. 3 Докажем, что утверждение верно при nk1 33k6-26k1-272633k3-133k3-26k-27.

Оба слагаемых делятся на 262 первое делится на 262, потому что мы доказали делимость на 26 выражения, стоящего в скобках, а второе делится по предположению индукции. В силу метода мате-матической индукции утверждение доказано. ПРИМЕР 14 Доказать, что если n 2 и х 0, то справедливо неравенство 1хn 1nх. Решение 1 При n2 неравенство справед-ливо, так как 1х212хх2 12х.

Значит, А2 истинно. 2 Докажем, что АkAk1, если k 2. Предположим, что Аk истинно, т.е что справедливо неравенство 1хk 1kx. 3 Докажем, что тогда и Аk1 истинно, т.е что справедливо неравенство 1xk1 1k1x. В самом деле, умножив обе части неравенства 3 на положительное число 1х, получим 1xk1 1kx1x. Рассмотрим правую часть последнего неравен- ства имеем 1kx1x1k1xkx2 1k1x.

В итоге получаем, что 1хk1 1k1x. Итак, АkAk1. На основании принципа математической индукции можно утверждать, что неравенство Бернулли справедливо для любого n 2. ПРИМЕР 15 Доказать, что справедливо неравенство 1aa2m 1mamm12a2 при а 0. Решение 1 При m1 1аа21 1а22а2 обе части равны. 2 Предположим, что при mk 1aa2k 1kakk12a2 3 Докажем, что при mk1 не-равенство верно 1aa2k11aa21aa2k 1aa21ka kk12a21k1akk12k1a2 kk12ka3kk12a4 1k1a

k1k22a2. Мы доказали справедливость неравенства при mk1, следовательно, в силу метода математиче-ской индукции, неравенство справедливо для лю-бого натурального m. ПРИМЕР 16 Доказать, что при n 6 справедливо неравенство 3n n2n1. Решение Перепишем неравенство в виде 32n 2n. 1 При n7 имеем 37272187128 1427 неравенство верно. 2 Предположим, что при nk 32k 2k. 3 Докажем верность неравен-ства при nk1. 3k12k13k2k32 2k323k 2k1.

Так как k 7, последнее неравенство очевидно. В силу метода математической индукции неравен-ство справедливо для любого натурального n. ПРИМЕР 17 Доказать, что при n 2 справедливо неравенство 11221321n2 1,7-1n. Решение 1 При n3 неравенство верно 1122132245180 2461801,7-13. 2 Предположим, что при nk 11221321k21,7-1k. 3 Докажем справедливость не- равенства при nk1 11221k21k12 1,7-1k1k12. Докажем, что 1,7-1k1k12 1,7-1k1 1k121k1 1kk2k12 1k kk2 k12k22k k22k1.

Последнее очевидно, а поэтому 11221321k12 1,7-1k1. В силу метода математической индукции не-равенство доказано. Заключение Вчастности изучив метод математической индукции, я повысил свои знания в этой облас-ти математики, а также научился решать задачи, которые раньше были мне не под силу. В основном это были логические и занима-тельные задачи, т.е. как раз те, которые повы-шают интерес

к самой математике как к науке. Решение таких задач становится заниматель-ным занятием и может привлечь в математиче-ские лабиринты вс новых любознательных. По-моему, это является основой любой науки. Продолжая изучать метод математической индукции, я постараюсь научиться применять его не только в математике, но и в решении проблем физики, химии и самой жизни. МАТЕМАТИКА ЛЕКЦИИ, ЗАДАЧИ, РЕШЕНИЯ Учебное пособие

В.Г.Болтянский, Ю.В.Сидоров, М.И.Шабунин. ООО Попурри 1996. АЛГЕБРА И НАЧАЛА АНАЛИЗА Учебное пособие И.Т.Демидов,А.Н.Колмогоров, С.И.Шварцбург,О.С.Ивашев-Мусатов, Б.Е.Вейц. Просвещение 1975.