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

Чрезвычайное расширение предмета математики привлекло в XIX веке усиленное внимание к вопросам ее «обоснования», т. е. критического пересмотра ее исходных положений (аксиом), построения строгой системы определений и доказательств, а также критического рассмотрения логических примеров, употребляемых при этих доказательствах.

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

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

Таким образом, было обнаружено, что понятие математической теории в смысле теории, охватываемой единой системой аксиом теоретико-множественного типа, существенно шире, чем логическое понятие дедуктивной теории.

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

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

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

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

1. Все учащиеся 6 «А» класса перешли в следующий класс.

2. Иванов – ученик 6 «А» класса.

3. Иванов перешел в 7-ый класс.

Из общего утверждения (1) при помощи утверждения (2) получено частное утверждение (3).

Переход от частных утверждений к общим называется индукцией. Индукция может привести как к верным, так и к неверным выводам. Например:

4. 140 делится на 5.

5. Все числа, оканчивающиеся нулем, делятся на 5.

Из частного утверждения (4) получено общее утверждение (5). Утверждение (5) верно.

6. 140 делится на 5.

7. Все трехзначные числа делятся на 5.

Из частного утверждения (6) получено общее утверждение (7). Утверждение (7) неверно.

Данную индукцию в математике называют несовершенной, она не обеспечивает полного знания, может приводить к неверным выводам. В противоположность ей, полной или совершенной называют метод математической индукции. Данный метод есть дедуктивный метод доказательства, поэтому он приводит только к верным выводам. Название «математическая индукция» обусловлено тем, что этот метод просто ассоциирует в нашем сознании с традиционными «индуктивными» умозаключениями.

Задача I

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

Решение:

(Возможно, Вы уже угадали ответ или совсем решили задачу, но мы очень подробно разберем ее решение, чтобы проиллюстрировать новую систему рассуждений). После первого шага мы по условию получаем 2 части. На втором шаге мы одну часть оставляем без изменений, а вторую – делим на 2 части и получаем 3 части. На третьем шаге мы две части оставляем без изменений, а последнюю (третью) делим на две части и получаем 2+2 = 4 части. На четвертом шаге мы три части оставляем без изменений, а последнюю делим на две части и получаем 3 + 2 = 5 частей. На пятом шаге Но, наверно, уже и так ясно, что на пятом шаге мы получим (проверьте!) 6 частей.

На I шаге получаем 2 части.

На II шаге получаем 3 части.

На III шаге получаем 4 части.

На IV шаге получаем 5 частей.

И какое же предложение напрашивается?

Правильно, через n шагов мы получим (n + I) часть. мы можем подтвердить это предложение, еще проверив при n = 6,7,8. А значит, можно и закончить решение? Но в дальнейшем мы увидим, что такой вывод может оказаться поспешным, неправильны. Итак, надо думать, как же доказать наше предположение, чтобы быть уверенным, что и через I00 шагов мы получим I0I часть.

Но предположим на мгновение, что через I00 шагов на самом деле получим I0I часть. Тогда на I0I шаге мы I00 частей оставляем без изменения, а последнюю делим на 2 части и получаем на I0I шаге

I00 + 2 = I02 части. Подумаем, что же мы получим, если бы нам как – то удалось проверить, что через I00 шагов квадрат разобьется на

I0I часть, то только что проведенное рассуждение служило бы строгим доказательством того, что через I0I шаг квадрат разобьется на I02 части. А еще заметим, что похожее рассуждение можно провести, поставив вместо число I00 произвольное натуральное число. Или, как говорится в математике, можно провести для произвольного натурального к.

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

Проанализируем, что же мы сейчас доказали? Попробуем в это доказательство вместо к поставить 3. Но через 3 шага и ненужно предполагать, что квадрат разобьется на 4 части – это нами уже было точно проверено в начале решения – а значит, из последнего доказательства (при к = 3), получим, что через 4 шага квадрат на самом деле разобьется на 5 частей; попробуем в это доказательство вместо к поставить 5. Но через 5 шагов квадрат действительно

Заметили, что так можно рассуждать как угодно долго, до бесконечности? То есть, теперь наше предположение, что через n шагов квадрат разобьется на (n + I) часть, становится доказанным.

Индукция в арифметике и алгебре

Метод математической индукции (по-своему существу, связанный с понятием числа), имеет наибольшее применение в арифметике, алгебре и теории чисел.

Пример 1. Вычислите сумму

S = + +. +.

1) Найдем S = , S = , S =. По аналогии можно предположить, что S =.

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

3) Докажем тогда, что гипотеза верна и для n = k + 1, т. е.

S = + +. + + = S + = + + = = =.

Следовательно, для любого натурального числа n

Пример 2. Вычислите сумму первых n нечетных чисел

S= 1 + 3 + 4 + 5 + + (2n-1).

Имеем S = 1, S = 4, S = 9, S= 16. Легко заметить, что S = 1,

S = 2, S = 3, S= 4. На этом основании можно предположить, что формула для S = n. Докажем это.

1) Для n = 1 формула верна.

2) Предположим, что для n = k формула также верна, то есть

S= 1 + 3 + 5 + + (2k - 1) = k.

3) Докажем тогда, что формула верна и для n = k + 1, т. е.

S = 1 + 3 + + (2k(k+1)-1) = S+ 2k + 1 = k + 2k + 1 =

= (k+1).

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

Ответ: S = n.

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

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

1) Для n = 1: S = = 1 – формула верна.

2) Пусть она верна для некоторого n = k, т. е.

3) Докажем, что формула верна и для n = k +1

S = + k + 1 = = = =

Для n = k +1 формула также верна. Следовательно, для любого натурального числа n S =.

Пример 4. Вычислите

S = 11! + 22! + 33! + + nn!

Решение:

S=11! = 1, S = 11! + 22! = 5, S = 11! + 22! + 33! = 23.

Можно записать, что

S = 2! – 1, S = 3! – 1, S = 4! – 1.

Это дает возможность высказать гипотезу, что

S = (n + 1)! – 1.

1) Проверим это для n = 1: S = 2! – 1 = 1 верно.

2) Пусть выполняется для n = k.

3) Докажем для n = k + 1.

S = (k + 1)! – 1 + (k +1)(k + 1)! = (k + 1)!(1 + k + 1) – 1 =

= (k + 2)(k + 1)! – 1 = (k + 2)! – 1, что и требовалось доказать.

Упражнения для самостоятельной работы

Вычислите сумму или произведение:

5. при

6. при

Доказательство тождеств

Пример 1. Доказать, что при любом натуральном n справедливо равенство

1) Проверим, что это тождество верно при n = 1.

- верно.

2) Пусть тождество верно и для n = k, т. е.

3)Докажем, что это тождество верно и для n = k + 1, т. е.

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

Пример 2. Докажите тождество

22 + 32 + 42 + + n2 = (n - 1)2

1) Проверим, что это тождество верно при n = 2.

22 = (2 - 1)2

4 = 4 – верно

2) Пусть тождество верно для n = k, т. е.

22 + 32 + 42 + + k2 = (k - 1)2

3) Докажем, что это тождество верно и для n = k + 1, т. е.

22 + 32 + 42 + + k2 + (k + 1)2 = k2

22 + 32 + 42 + + k2 + (k + 1)2 = (k - 1)2+ (k + 1)2 =

= (k –1 + k + 1)2 = 2k2 = k2

Пример 3. Докажите, что при любом натуральном n справедливо равенство

1) Проверим, что это тождество верно n = 1.

- верно.

2) Пусть формула верна для n = k, т. е.

3) Докажем, что эта формула верна и для n = k + 1, т. е.

Пример 4. Докажите тождество

При n 2

1) Проверим, что это тождество верно для n = 2

- верно

2) Пусть формула верна для n = k, т. е.

3) Докажем, что эта формула верна и для n = k + 1, т. е.

Пример 5. Докажите тождество

1 + 2 + 3 + + n =

1) Проверим, что это тождество верно n = 1.

1= - верно.

2) Пусть это тождество верно и для n = k, т. е.

+++ + =

3) Докажем, что это тождество верно и для n = k + 1, т. е.

+++ + ()=

+++ + + ()= + ()= ===

Д = 49 – 48 = 1

Пример 6. Докажите тождество

1) Проверим, что это тождество верно при n = 1.

- верно.

2) Пусть тождество верно и для n = k, т. е.

3)Докажем, что это тождество верно и для n = k + 1, т. е.

М – сумма 2) и 3).

М = = =

= = == =

= = =

Пример 7. Докажите тождество

1) Проверим, что эта формула верна для n = 1.

- верно.

2) Пусть формула верна для n = k, т. е.

3) Докажем, что это тождество верно и для n = k + 1, т. е.

М = == =

Д = 25 – 16 = 9

Пример 8. Докажите, что для любого справедливо равенство

Обозначим произведение в левой части равенства через , т. е.

Мы должны доказать, что.

1) Проверим, что эта формула верна для n = 2.

-верно.

2) Пусть формула верна для n = k, т. е.

3) Докажем, что это тождество верно и для n = k + 1, т. е.

Заметим, что

По принципу математической индукции равенство справедливо для любого натурального.

Упражнения для самостоятельной работы

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

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

Пример 1. Докажите, что если a >b и a, b – положительные числа, то a>b.

При n = 1 утверждение очевидно, a>b.

Предположим, что a>b.

Докажем, что тогда a>b. Умножив неравенства a>b и a >b почленно, получаем a>b. Следовательно, a>b.

Пример 2. Докажите, что 2>2n + 1 при любом натуральном n3.

Доказательство. При n = 3 неравенство верно. 2>23 + 1.

Предположим, что 2>2k + 1 (k3). Докажем, что 2> 2(k + 1) + 1.

В самом деле,

2 = 22>2(2k + 1) = (2k + 3)(2k - 1) > 2k + 3, так как 2k – 1>0 при любом натуральном значении k. Следовательно, 2>2n + 1 при всех n3.

Пример 3. Доказать, что при любом натуральном n справедливо неравенство

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

Обозначим сумму в левой части неравенства через , тогда нам требуется доказать, что

При n = 1 неравенство верно.

или - верно.

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

Докажем, что равенство верно и для n = k+1, т. е.

Для доказательства рассмотрим разность

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

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

Пример 4. Доказать, что при любом натуральном n справедливо неравенство

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

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

При n = 1 неравенство верно.

- верно.

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

Докажем, что равенство верно и для n = k+1, т. е.

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

Пример 5. Докажите, что для любого n7 справедливо неравенство

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

При n неравенство не выполняется.

При n 7 неравенство верно.

или 64 > 56 – верно.

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

Докажем, что равенство верно и для n = k+1, т. е.

Для завершения доказательства достаточно проверить, что неравенство при справедливо. Это неравенство эквивалентно неравенству

, верному при , а значит и тем более при.

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

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

При неравенство верно.

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

Докажем, что равенство верно и для n = k+1, т. е.

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

Упражнения для самостоятельной работы

Докажите неравенства.

2. для.

3. для.

6. для

8. для

10. для

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

Условимся вместо фразы «делится на» пользоваться знаком «».

Пример 1. Докажите, что

(11 + 12)133

Доказательство. Пусть n = 1. Тогда

11 + 12 = (11 + 12)(11 - 1112 + 12) = 23133. (23133) 133

Предположим, что (11 + 12)133.

Докажем, что в таком случае и (11 + 12)133.

В самом деле,

11 + 12 = 1111 + 1212 = 11(11 + 12) + 13312.

Полученная сумма делится на 133. итак, утверждение доказано.

Пример 2. Докажите, что

(3 + 40n - 67) 64.

Доказательство. Если n = 1, то

3 + 40 – 67 = 0. 0 64.

Пусть уже доказано, что (3 + 40k - 67) 64.

Докажем, что тогда (3 + 40k - 67) 64.

В самом деле

3 + 40(k + 1) – 67 = 93 + 40k – 27 = 9(3 + 40k - 67) – 320k +

+ 576 = 9(3 + 40k - 67) – 64(5k - 9).

Но (9(3 + 40k - 67) – 64(5k - 9)) 64. Справедливость данного утверждения доказана.

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

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

1) Проверим, что это выражение верно при n = 1.

2) Пусть формула верна для n = k, т. е.

3) Докажем, что формула верна и для n = k + 1, т. е.

Кратно 6 по 2) кратно 6 по 1)

Значит и все выражение делится на 6.

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

1) Проверим, что это выражение верно при n = 1.

2) Пусть эта формула верна для n = k, т. е.

3) Докажем, что формула верна и для n = k + 1, т. е.

Значит, и все выражение делится на 5.

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

1) Проверим, что эта формула верна при n = 1.

2) Пусть эта формула верна для n = k, т. е.

3) Докажем, что формула верна и для n = k + 1, т. е.

Если члены кратны 16, то и все выражение кратно 16.

Пример 6. Докажите методом математической индукции делится на без остатка, т. е.

1) Проверим, что эта формула верна при n = 1.

2) Пусть эта формула верна для n = k, т. е.

3) Докажем, что формула верна и для n = k + 1, т. е.

4) Проверим, что эта формула верна при n = 1.

5) Пусть эта формула верна для n = k, т. е.

6) Докажем, что формула верна и для n = k + 1, т. е.

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

1) Проверим, что эта формула верна при n = 1.

2) Пусть эта формула верна для n = k, т. е.

3) Докажем, что формула верна и для n = k + 1, т. е.

(Чтобы получить в скобках выражение, кратное 16, прибавили и вычли число ). Наше выражение представляет собой сумму трех слагаемых, каждое из которых делится на 16. Значит, истинно.

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

Докажем утверждение: «Для любого натурального числа выражение »

1) Проверим, что эта формула верна при n = 1.

2) Пусть эта формула верна для n = k, т. е.

3) Докажем, что формула верна и для n = k + 1, т. е.

Полученное выражение содержит два слагаемых, каждое из которых делится на 9, таким образом, формула для n = k + 1 верна.

По принципу математической индукции наше утверждение справедливо для любого натурального числа n.

Упражнения для самостоятельной работы

Докажите, что при любом натуральном n:

Заключение

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