Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

СПРАВОЧНЫЕ СВЕДЕНИЯ

Пусть множество M R таково, что: 1) 1 M; 2) каково бы ни было натуральное число n M, то и число n+1 M (таким образом N M). Тогда, при выполнении условия M N следует, что М = N.

Следовательно, если мы установим, что утверждение A(x) справедливо при x = 1, и, если из того, что A(x) справедливо при произвольном k N, вытекает его справедливость при k+1, то утверждение A(x) будет верно при всех n N.

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

Теорема 1. Утверждение справедливо для n = 1.

Теорема 2. Если утверждение справедливо для некоторого натурального числа n, то оно справедливо для n + 1.

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

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

S_n = + + + …+ = .

Теорема 1. Для n=1 гипотеза верна, так как S₁ = = .

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

S_k = + + + …+ = ,

Докажем, что тогда гипотеза обязана быть верной и для n = k+1, т.е. что S_k+1 = .

Действительно, S_k+1 = S_k + , следовательно, по условию теоремы,

S_k+1 = + = .

Обе теоремы доказаны. Теперь на основании принципа математической индукции мы имеем право утверждать, что S_n = при всяком натуральном n.

Замечание 1. Необходимо подчеркнуть, что доказательство методом математической индукции, безусловно, требует доказательства обеих теорем 1 и 2.

Решая пример 1, мы выдвинули гипотезу S_n = , которая (как было доказано выше) оказалась верной.

Интересно рассмотреть случай «неверной гипотезы»: S_n = (2)

При n=1 формула (2) верна, так как S₁ = .

Предположим, что формула (2) верна при n = k,т. е. S_k = и вычислим S_k+1:

S_k+1 = + = + = .

Вычисленное значение S_k+1 отлично от требуемого (S_k+1= ), т.е. из справедливости формулы (2) при n=kне следует её справедливость при n= k+1.

Замечание 2. Если рассматриваемое утверждение верно не только при n=1, но и в целом ряде частных случаев, то это еще не означает, что утверждение справедливо при всех n N. Действительно, рассмотрим функцию :

Вычислим несколько первых значений этой функции:

Наблюдательный читатель сразу заметит, что полученные числа (43, 47, 53, 61, 71, 83, 97) являются простыми (т.е. такими, которые делятся без остатка только на 1 и на само себя). Продолжим вычисления: . Числа 113, 131 и 151 так же являются простыми и вполне естественно возникновение гипотезы: «Для любого натурального числа число является простым числом».

Более того, большинство читателей абсолютно уверено, что обозначенная гипотеза уже доказана. Хотя простая проверка разрушает это предположение.

Рассмотренный пример позволяет сделать простой и в то же время важный вывод: Если утверждение справедливо в целом ряде частных случае, то это не означает, что оно справедливо всегда.

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

ПРИМЕРЫ С РЕШЕНИЯМИ

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

Решение. Обозначим искомую сумму S_n, т. е.

S_n = 1+3+5+7+…+(2n-1).

Придаём nпоследовательно значения 1, 2, 3,... до тех пор, пока у нас не накопится достаточно материала, чтобы на основе его построить более или менее надёжную гипотезу. Имеем

S₁ = 1, S₂ = 4, S₃ = 9, S₄ = 16, S₅ = 25, S₆ = 36.

Теперь всё зависит от наблюдательности решающего задачу и от его способности за частными результатами увидеть общий.

Полагаем, что в данном случае легко заметить, что

S₁= 1², S₂= 2², S₃= 3², S₄= 4², S₅= 5².

На основе этого можно предположить, что S_n= n².

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

Теорема 1. При n=1 гипотеза справедлива, т.к. S₁ = 1 = 1²

Теорема 2. Допустим, что гипотеза верна для n = k, т.е. S_k= k². Докажем, что тогда гипотеза должна быть верна и для n = k + 1, т.е. S_k+1 = (k + 1)²

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

S_k+1 = S_k + (2k + 1) = k² + (2k + 1) = (k + 1)²,

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

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

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

Обозначим искомую сумму S_n, т. е. S_n =1+2+3+4+…+n.

Теорема 1. При n = 1 гипотеза верна.

Теорема 2. Пусть S_k =1 + 2 + 3 + 4+…+k = . Покажем, что S_k+1 = . Действительно,

S_k+1 = S_k +(k + 1)= + (k + 1)= .

Задача решена.

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

Решение. Сумма 1³ + 2³ + 3³ делится на 9. Значит, утверждение справедливо, когда первым из трёх последовательных натуральных чисел является 1.

Пусть сумма k³+(k+1)³+(k+2)³, где k-некоторое натуральное число, делится на 9. Выражение

(k + 1)³ + (k + 2)³ + (k + 3)³ = (k + 1)³ + (k + 2)³ + k³ + 9k² + 27k + 27 = [k³ + (k + 1)³ + (k + 2)³] + 9(k² + 3 +3) представляет собой сумму двух слагаемых, каждое из которых делится на 9, а следовательно, и вся сумма тоже делится на 9.

ЗАДАЧИ

Задача 1. Найти сумму

S_n= 1 + 2 + 2² + 2³ +… +2^n-1.

Задача 2. Доказать, что для каждого натурального n верно равенство

1×2+2×5+…+n(3n-1)= n² (n+1).

Задача 3. Доказать, что для каждого натурального n верно равенство

1² +2² +3² +…+n² =

Задача 4. Доказать, что для каждого натурального n верно равенство

1² +3² +5² +…+(2n-1)² = .

Задача 5. Доказать, что для каждого натурального n верно равенство

1×2+2×3+3×4+…+(n-1)n= .

Задача 6. Доказать, что для каждого натурального n верно равенство

1³ +2³ +3³ +…+n³ = ()².

Задача 7. Доказать, что при каждом натуральном n число 5×2^3n-2 + 3^3n-1 делится на 19.

Задача 8. Доказать, что при каждом натуральном n число n(2n²-3n+1) делится на 6.

Задача 9. Доказать, что при каждом натуральном n число n⁵ –n делится на 5.

Задача 10. Доказать, что для каждого натурального n верно равенство

+ + …+ = .

Задача 11. Доказать, что для каждого натурального n верно равенство

+ + + …+ = .

Задача 12. При каких натуральных n справедливо неравенство 2ⁿ > n² ?

Задача 13. Доказать неравенство: (неравенство Бернулли).

Задача 14. Доказать, что

Задача 15. Доказать, что

Варианты заданий,