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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



Метод математической индукции – универсальный способ доказательства утверждений, зависящих от натурального аргумента n. Он основан на следующем принципе математической индукции: утверждение справедливо для любого натурального n, если: 10 оно справедливо для n = 1;

20 из того, что оно верно для всех n £ k (k ³ 1) следует его справедливость для n = k + 1.

Этот принцип, являющийся одной из аксиом натурального ряда можно перефразировать так: если в цепочке утверждений Р(n) первое утверждение Р(1) верно, а из справедливости Р(k) следует справедливость Р(k + 1), то вся цепочка состоит из вер-ных утверждений.

Пример 1. Найти сумму .

Решение. Имеем: ; ; ; . Есть подозрение, что . Докажем эту формулу.

10. При n = 1 – формула верна.

20. Предположим, что для произвольного k ³ 1 для всех n £ k . В частности, для n = k . Найдем . Имеем . По предположению это равно

= = = ,

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

Слово “индукция” переводится как “наведение”. Во многих отраслях науки используют метод простой (не математической) индукции – вывод, полученный после рассмотрения ряда частных случаев (согласно принципу простой индукции – от частного к общему). В основном так поступают, обобщая результаты каких-то экспериментов. Так, в предыдущем примере, при выводе возможной формулы для Sn, предварительно были найдены значения S1, S2, S3, …. Однако индуктивное утверждение может быть неверным, простая индукция позволяет лишь выдвинуть гипотезу, которую надо доказать, например, с помощью математической (полной) индукции. Можно привести много примеров, когда простая ндук-ция приводит к ошибочным выводам. Например, анализируя числа 1, 3, 5, 7 можно прийти к неверноиу заключению, что все не-четные числа являются простыми.

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

Пример 2. “Докажем”, что все натуральные числа равны между собой. Предположим, что k = k + 1. Прибавим по 1 к обеим частям этого равенства. Получим k + 1 = k + 2, что и требовалось доказать. Ошибка этого “доказательства” состоит в отсутствии проверки утверждения при n = 1.

КОНТРОЛЬНЫЕ ВОПРСЫ И ЗАДАНИЯ

1*. Доказать формулу Sn = 12 + 22 + 32 + … + n2 =

= n(n +1)(2n +1) /6.

2*. Доказать неравенство 2n > 2n + 1 при n ³ 3.

3*. Обозначим Hn = 1 + 1/2 + 1/3 +…+ 1/n – гармонические числа. Доказать, что Нn неограниченно сверху, т.е. что Нn ® +¥.

4*. Доказать, что любую сумму денег более 7 копеек можно уплатить монетами достоинством 3 и 5 копеек.

5*. Доказать, что для любого n ³ 0 число 11n + 2 + 122n + 1 делится на 133.

Доказать формулы и утверждения (6 – 13).

6. .

7. При любом х ¹ 1, .

8. Сумма кубов трех последовательных натуральных чисел n3 + (n + 1)3 + (n + 2)3 делится на 9.

9. Число диагоналей выпуклого n-угольника k = n(n –2) /2.

10. Последовательность аn = (n корней) возрастает.

11. cos a×cos 2a×… ×cos 2na = .

12. .

13. .

Примеры решения

Задача 1.

, т.е. при n = 1 формула верна. Sk + 1 = Sk + (k+1)3 = = = .

Задача 2.

2k + 1 = 2×2k > 2(2k + 1) = 4k + 2 = (2k + 3) + (2k – 1) > 2k + 3.

Задача 3. Докажем, что .

10. m = 1, Н2 = 1 + = 1 + .

20. > + + = > 1 + = 1 + .

Это означает, что при достаточно большом n значение Нn может стать больше любого числа.

Задача 4.

10. 3 + 5 = 8 – верно.

20. Пусть уплатили k копеек. Возможны два случая.

а) Вся сумма оплачена только 3-копеечными монетами, т.е. k=3n, где n³3. Тогда k+1=3(n-3)+9+1=3(n-3)+2×5. В этом случае надо 9 копеек (3+3+3) заменить на 5 + 5.

б) Использована хотябы одна 5-копеечная монета. Тогда надо 5 копеек заменить на 3 + 3 – снова получим сумму k + 1.

Задача 5.

10. 112 + 121 = 133 – верно при n = 0.

20. 11k +3 + 122(k + 1) +1 = 11×11k + 2 + 144×122k + 1 = (144–133) ´ ´11k + 2 + 144×122k + 1 = 144 × (11k + 2 + 122k + 1) – – 133×11k + 2.

В полученной разности уменьшаемое делится на 133 по предположению, а вычитаемое содержит множетель 133. Следо-вательно, все выражение делится на 133.

Библиографический список

1. Бугаев, Ю. В. Об одном методе отбора эффективных реше-ний на итерациях поиска [Текст] / Ю. В. Бугаев // Математич. моделирование информационных и технологич. систем: межвуз. сб. науч. тр. Воронеж: ВГТА, 2000. Вып. 4. С. 211 – 215.

2. Новиков, Ф. А. Дискретная математика для программистов [Текст] / Ф. А. Новиков. СбП: Питер, 2000. 304 с.

3. Саати, Т. Аналитическое планирование организации систем [Текст] / Т. Саати, К. Кернс / Пер. с англ. М.: Радио и связь, 1991. 223 с.

4. Юдин, Д. Б. Вычислительные методы теории принятия решений [Текст] / Д. Б. Юдин. М.: Наука, 1989. 320 с.

5. Яблонский С. В. Введение в дискретную математику: Учебное пособие для Вузов [Текст] / С. В. Яблонский. М.: Высш. шк., 2001. 384 с.

[mmtc1]

[mmtc2]



Поделиться:


Последнее изменение этой страницы: 2017-01-26; просмотров: 255; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.64.8 (0.007 с.)