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

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

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

утверждение «для любого n∈ N вып P(n)» считается доказанным, если оно доказано для n =1 и для любого натурального числа k из предположения, что P(n) истинно для n = k , доказывается его истинность для n = k +1.

Запись принцип математической индукции в символической форме:

[P(1)∧(∀k ∈ N () P(k) ⇒ P(k +1))] ⇒(∀n ∈ N) P(n).

Для доказательства утверждений методом математической индукции используется схема рассужд, состоящая из следующих этапов:

1. База индукции. Док истинность утв P(n) для n =1(обычно это уд сделать непоср проверкой).

2. Индуктивное предпол. Доп, что утв P(n) верно для всех 1 ≤ n ≤ k

. 3. Индукц переход. Исх из индуктив предп, док истинн P(n) для n = k +1.

4. Вывод. На осн 1х 3 этапов и принц мат индукции дел вывод о справ утв для любого n∈ N .

Замеч 1.6. Если треб док утв P(n), где n ∈ N0, то база индукции нач с n = 0.

Замеч 1.7. Иногда бывает н док справедл нек утв P(n), завис от нат парам n, для всех n ≥ m , где m – фиксе нат число. В этом сл принцип мат инд м записать в виде:

[P(m) ∧ (∀k ≥ m)(P(k) ⇒ P(k +1))]⇒(∀n ≥ m) P(n)

З1. Док, что З^3 + 3 – 26n — 27 при произв нат п делится на 26² без остатка.      

Реш Предв док по инд всп утв, что 3³ⁿ⁺³ — 1 делится на 26 без остатка при п  0.

1. База индукции. При п = 0 имеем: З³ - 1 = 26 —делится на 26.

Шаг инд.Предположим, что 3^3n + 3 –1 делится на 26 при п = к, и докажем, что в этом случае утверждение будет верно при п=к +1.

но

то из индуктивного предположения заключим, что число 3^3k + 6 - 1 делится на 26.

Теперь докажем утверждение, сформулированное в условии задачи. И снова по индукции.

А)База. Очевидно, что при п = 1 утв верно: так как 3³⁺³ - 26 - 27 = 676 = 26².

Б)Шаг инд. Предположим, что при п = к 3^3k + 3 - 26k - 27 дел на 26² без остатка, и докажем, что утверждение верно при п = к + 1. В последней сумме оба слагаемых делятся без остатка на 26². 1е — потому что мы доказали делимость выражения, в скобках, на 26; 2е — по предположению индукции

Пр1. Пусть . Доказать, что

Пример 2. Доказать.

1. База индукции. При N = 1, утверждение, очевидно, верно.

2. Индуктивное предположение. Пусть N = K и

3. Индуктивный переход. Пусть N = K + 1. Докажем:

Действительно, возведем правую сторону в квадрат как сумму двух чисел:

Используем индуктивное предположение и формулулу суммы арифм прогрессии:

 , получим

Пример 3. Доказать неравенство

 для .

1)Базой индукции в этом случае является проверка истинности утверждения для , т. е. н проверка неравенства . Для этого достаточно возв неравенство в квадрат:

  или 63

2) Пусть нер-во верно для , т. е..

3)Пусть n=k+1, докажем:.Используя предположения индукции

Зная как должна выглядеть правая сторона в доказываемом неравенстве выделим эту часть

Ост устано что лишний множи . Действ,

.

2. Доказать, что при любом .

1)  кратно . 2)  кратно .3)  кратно .

4)  кратно .5)  кратно .6)  кратно 19.

3. Доказать справедливость следующих неравенств для всех натуральных .

1) .2) .3) .

7. Доказать неравенство Бернулли , 

8 Доказать, что для всех нат  справед равенство

9. при n2

10 Доказать, что для всех нат  11. Док, что сторона прав впис в окр -уг

 где  — радиус этой окружности (двоек — ).