Метод математичної індукції є важливим способом докази пропозицій (тверджень), що залежать від натурального аргументу.
Метод математичної індукції полягає в наступному:
Пропозиція (твердження) P (n), залежне від натурального числа n. справедливо для будь-якого натурального n якщо:- P (1) є істинним пропозицією (затвердженням);
- P (n) залишається істинним пропозицією (затвердженням), якщо n збільшити на одиницю, тобто P (n + 1) - істинне речення (твердження).
- Етап перевірки: перевіряється, чи істинно пропозиція (твердження) P (1).
- Етап докази: передбачається, що пропозиція P (n) істинно, і доводиться істинність пропозиції P (n + 1) (n збільшено на одиницю).
Зауваження 1. У деяких випадках метод математичної індукції використовується в такій формі:
Нехай m - натуральне число, m> 1 і P (n) - пропозиція, залежне від n. n ≥ m.
якщо- P (m) справедливо;
- P (n) будучи істинним пропозицією, тягне істинність пропозиції P (n + 1) для будь-якого натурального n. n ≥ m. тоді P (n) - істинне речення для будь-якого натурального n. n ≥ m.
Надалі розглянемо приклади застосування методу математичної індукції.
Приклад 1. Довести наступні рівності
g) формула бінома Ньютона:
Рішення. a) При n = 1 рівність набуде вигляду 1 = 1, отже, P (1) істинно. Припустимо, що це рівність справедливо, тобто, має місце. Слід перевірити (довести), що P (n + 1), тобто істинно. Оскільки (використовується припущення індукції) отримаємо тобто, P (n + 1) - істинне твердження.
Таким чином, згідно з методом математичної індукції, вихідне рівність справедливо для будь-якого натурального n.
Зауваження 2. Цей приклад можна було вирішити й інакше. Дійсно, сума 1 + 2 + 3 +. + N є сума перших n членів арифметичної прогресії з першим членом a1 = 1 і різницею d = 1. В силу відомої формули, отримаємо
b) При n = 1 рівність набуде вигляду: 2 · 1 - 1 = 1 2 або 1 = 1, тобто, P (1) істинно. Припустимо, що має місце рівність 1 + 3 + 5 +. + (2n - 1) = n 2 і доведемо, що має місце P (n + 1): 1 + 3 + 5 +. + (2n - 1) + (2 (n + 1) - 1) = (n + 1) 2 або 1 + 3 + 5 +. + (2n - 1) + (2n + 1) = (n + 1) 2.
Використовуючи припущення індукції, отримаємо 1 + 3 + 5 +. + (2n - 1) + (2n + 1) = n 2 + (2n + 1) = (n + 1) 2.
Таким чином, P (n + 1) істинно і, отже, необхідне рівність доведено.
Зауваження 3. Цей приклад можна вирішити (аналогічно попередньому) без використання методу математичної індукції.
c) При n = 1 рівність істинно: 1 = 1. Припустимо, що істинно рівність і покажемо, що то є істинність P (n) тягне істинність P (n + 1). Дійсно, і, так як 2n 2 + 7n + 6 = (2n + 3) (n + 2), отримаємо і, отже, вихідне рівність справедливо для будь-якого натурального n.
d) При n = 1 рівність справедливо: 1 = 1. Припустимо, що має місце і доведемо, що
e) Затвердження P (1) справедливо: 2 = 2. Припустимо, що рівність справедливо, і доведемо, що воно тягне рівність Дійсно,
Отже, вихідне рівність має місце для будь-якого натурального n.
f) P (1) справедливо: 1/3 = 1/3. Нехай має місце рівність P (n):. Покажемо, що остання рівність тягне наступне:
Дійсно, з огляду на, що P (n) має місце, отримаємо
Таким чином, рівність доведено.
g) При n = 1 маємо a + b = b + a і, отже, рівність справедливо.
Нехай формула бінома Ньютона справедлива при n = k. тобто, Тоді Використовуючи рівність отримаємо
Приклад 2. Довести нерівності
a) нерівність Бернуллі: (1 + a) n ≥ 1 + n a. a> -1, n Про N.
і покажемо, що тоді має місце і (1 + a) n + 1 ≥ 1 + (n + 1) a.
Дійсно, оскільки a> -1 тягне a + 1> 0, то множачи обидві частини нерівності (1) на (a + 1), отримаємо (1 + a) n (1 + a) ≥ (1 + na) (1 + a) або (1 + a) n + 1 ≥ 1 + (n + 1) a + na 2 Оскільки na 2 ≥ 0, отже, (1 + a) n + 1 ≥ 1 + (n + 1) a + na 2 ≥ 1 + (n + 1) a.
Таким чином, якщо P (n) істинно, то і P (n + 1) істинно, отже, відповідно до принципу математичної індукції, нерівність Бернуллі справедливо.
Розглянемо наступні два випадки:
c) Нехай x1, x2. xn - довільні позитивні числа. Розглянемо наступні n позитивних чисел: Оскільки їх добуток дорівнює одиниці: згідно з раніше доведеному нерівності b), випливає, що звідки
d) P (1) - справедливе твердження: sin 2 a + cos 2 a = 1. Припустимо, що P (n) - істинне твердження: sin 2n a + cos 2n a ≤ 1 і покажемо, що має місце P (n + 1). Дійсно, sin 2 (n + 1) a + cos 2 (n + 1) a = sin 2n a · sin 2 a + cos 2n a · cos 2 a 2n a + cos 2n a ≤ 1 (якщо sin 2 a ≤ 1 , то cos 2 a 2 a ≤ 1, то sin 2 a 2n a + cos 2n ≤ 1 і знак рівності досягається лише при n = 1.
e) При n = 1 твердження справедливо: 1 3/2.
Припустимо, що і доведемо, що Оскільки з огляду на P (n), отримаємо
f) З огляду на зауваження 1. перевіримо P (10): 2 10> 10 3. +1024> 1000, отже, для n = 10 твердження справедливо. Припустимо, що 2 n> n 3 (n> 10) і доведемо P (n + 1), тобто 2 n +1> (n + 1) 3.
Оскільки при n> 10 маємо або, слід, що 2n 3> n 3 + 3n 2 + 3n + 1 або n 3> 3n 2 + 3n + 1. З огляду на нерівність (2 n> n 3), отримаємо 2 n +1 = 2 n · 2 = 2 n + 2 n> n 3 + n 3> n 3 + 3n 2 + 3n + 1 = (n + 1) 3.
Таким чином, згідно з методом математичної індукції, для будь-якого натурального n Про N. n ≥ 10 маємо 2 n> n 3.
Приклад 3. Довести, що для будь-якого n Про N
a) n (2n 2 - 3n + 1) ділиться на 6,
b) 6 2n -2 + 3 n +1 + 3 n -1 ділиться на 11.
Рішення. a) P (1) - істинне твердження (0 ділиться на 6). Нехай P (n) справедливо, тобто n (2n 2 - 3n + 1) = n (n - 1) (2n - 1) ділиться на 6. Покажемо, що тоді має місце P (n + 1), тобто, (n + 1) n (2n + 1) ділиться на 6. Дійсно, оскільки