Докажите что следующее утверждение верно для любого натурального значения n

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

Метод математической индукции состоит в следующем. Пусть нужно доказать справедливость некоторого утверждения А(n) для любого натурального числа n (например, нужно доказать, что сумма первых nнечётных чисел равна n 2 ). Сначала проверяют справедливость утверждения для n= 1 (базис математической индукции). Затем доказывают, что для любого натурального числа k верно следующее утверждение: если справедливо A(k), то справедливо и A(k+1) (индукционный шаг). Тогда утверждение А(n) считается доказанным для любого n. В самом деле, утверждение справедливо для n = 1 (это проверялось отдельно). Но если верно А(1), то верно и А(2); поскольку верно А(2), то верно и А(3); из справедливость А(3) следует, что утверждение верно и для n = 4 и т.д., т.е. утверждение верно для любого n.

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

Утверждение, зависящее от натурального числа n, справедливо для любого n, если выполнены два условия:

А) утверждение верно для n=1;

Б)из справедливости утверждения для n=к, где к – любое натуральное число, вытекает справедливость утверждения и для следующего натурального числа n= к+1.

Так же, если предложение А(n), зависящее от натурального числа n, истинно для n=1 и из того, что оно истинно для n=k (где k-любое натуральное число), следует, что оно истинно и для следующего числа n=k+1, то предположение А(n) истинно для любого натурального числа n.

Алгоритм (он состоит из четырех этапов):

1.база(показываем, что доказываемое утверждение верно для некоторых простейших частных случаев (п= 1));

2.предположение(предполагаем, что утверждение доказано для первых к случаям);

3.шаг(в этом предположении доказываем утверждение для случая п= к + 1);

4.вывод (утверждение верно для всех случаев, то есть для всех п).

Второй вариант метода математической индукции.

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

Утверждение верно при всех натуральных значениях п ≥ р, если: 1)оно верно при п =р (а не при п = 1, как было сказано выше);

2)из справедливости этого утверждения при п = k_, где k ≥ р (а не k ≥ 1, как сказано выше), вытекает, что оно вер­но и при п = k + 1.

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

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

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

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

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

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

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

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

Глава 2. Задачи на использование метода математической индукции

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

Пример 1.

Доказать, что при любом натуральном n>1

.

Обозначим левую часть неравенства через .

, следовательно, при n=2 неравенство справедливо.

Пусть при некотором k. Докажем, что тогда и . Имеем , .

Сравнивая и , имеем , т.е. .

При любом натуральном k правая часть последнего равенства положительна. Поэтому . Но , значит, и .

Пример 2.

Докажем, что 2 n +1 >2n+1 для любого n <\displaystyle x\in \mathbb >∈ N.

Пусть n=1. Тогда 2 2 >2+1; 4>3 – истина.

Пусть k – истина, т.е. 2 k +1 >2k+1.

Докажем, что тогда и k+1 – истина, т.е. 2 k +2 >2k+3.

По индуктивному предположению 2 k +1 >2k+1.

Умножим обе части неравенства на 2:

Отметим, что если a > b + c, то a > b при c > 0.

Следовательно, 2k−1 > 0. Тогда при k > 1 2 k +2 >2k+3.

Итак, доказано что при n=1и k – истина следует, что k+1 – истина.

Таким образом, для любого n <\displaystyle x\in \mathbb >∈ N2 n +1 >2n+1 истина

Пример 3.

Доказать, что , где >-1, , n – натуральное число,

При n=2 неравенство справедливо, так как .

Пусть неравенство справедливо при n=k, где k – некоторое натуральное число, т.е.

. (1)

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

. (2)

Действительно, по условию, , поэтому справедливо неравенство

, (3)

полученное из неравенства (1) умножением каждой части его на . Перепишем неравенство (3) так: . Отбросив в правой части последнего неравенства положительное слагаемое , получим справедливое неравенство (2).

Пример 4.

1. Если n = 1, то по условию х₁ = 1 и, следовательно, можно написать x₁ ≥ 1, т. е. для n = 1 утверждение верно.

Могут представиться два случая: либо все эти числа равны 1, и тогда их сумма равна k+1 и неравенство доказано, либо среди этих чисел есть хотя бы одно число, не равное единице, и тогда обязательно есть, по крайней мере, еще одно число, не равное единице, причем если одно из них меньше единицы, то другое больше единицы. Не ограничивая общности, можно считать, что х_k > 1, а х_{k + 1} n > 1 + nα, где

(1+α) 2 > 1+2α; α 2 > 0, значит n = 2 – истина.

Пусть k – истина, т.е. (1+α) k > 1+kα.

По индукционному предположению (1+α) k > 1+kα.

Умножим обе части неравенства на 1+α, тогда

(1+α) k +1 > (1+kα)( 1+α) = 1+(k+1)α+ kα 2 >1+(k+1)α, так как kα 2 >0.

Итак, доказано, что при n=1и k – истина следует, что k+1 – истина.

(1+α) n > 1 + nα, где

Пример 6.

Доказать неравенство , при a и b≥0.

1) При n=1. a+b≤ 2(a+b) – верно.

2) При n=k. .

3) При n=l+1. = так как разность и, следовательно, . Что и требовалось доказать.

2. Суммирование рядов.

Пример 7.

Пусть дана последовательность (n) натуральных чисел. Найдем формулу вычисления суммы первых n чисел:

Рассмотрим S(1), S(2), S(3), S(4). Мы имеем:

Заметив, что полученные числа можно записать в виде

естественно сделать предположение, что

Применим теперь метод математической индукции для доказа­тельства полученной формулы (1).

При n = 1,

Формула верна при n = 1. Предположим, что формула верна при n = k > 1:

‘Значит, из справедливости формулы для n = k вытекает ее справедливость для n = k + 1. По принципу математической индукции отсюда вытекает справедливость формулы (1) для всех натуральных значений n.

В некоторых случаях для доказательства тождества Р(n) = Q (n)можем сначала убедиться, что Р (1) = Q (1), и, предпола­гая справедливость равенства P(k)=Q(k), k>1, доказать тож­дество P(k + 1) = Q(k + 1). Тогда из истинности равенства P(k) = Q(k) будет следовать истинность равенства P(k + 1) = Q(k + 1) и по принципу математической индукции бу­дет следовать истинность тождества P(n)=Q(n)для всех n.

Пример 8.

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

Пусть .

.

Предположим, что . Тогда

и окончательно .

Пример 9.

Доказать, что .

.

Если , то

.

Пример 10.

.

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

Пусть .

Докажем, что .

Пример 11.

Найдите сумму +

S(1)= , S(2)= , S(3)=S(2)+ , S(4)=S(3)+ , S(5)=S(4)+ , S(6)=S(5)+ Можно предположить, что S(n)=

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

Пример 12.

Доказать, что 1+x 2 +x 3 +x 4 +….+x n = , где x 1

, следовательно, при n=1 формула верна.

Пусть k- любое натуральное число и пусть формула верна при n=k, т.е.

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

Задачи на делимость.

Пример 13.

Если n – натуральное число, то число четное.

При n=1 наше утверждение истинно: — четное число. Предположим, что — четное число. Так как , a 2k – четное число, то и четное. Итак, четность доказана при n=1, из четности выведена четность .Значит, четно при всех натуральных значениях n.

Пример 14.

Доказать истинность предложения

Высказывание А(1)= <число кратно 19> истинно.

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

Пример 15.

Доказать, что 10 п + 18 п – 28 кратно 27, где п- натуральное число.

1) Проверим, что данное утверждение верно при п=1 :

10 1 + 18 – 28 = 10+18-28 = 0, 0 27,

утверждение верно при п =1.

2)Предположим, что данное утверждение верно, при п=k:

3)И, докажем, что данное утверждение верно при п=k+1:

(10 k +1 +18(k+1)-28) 27.

27 27

Так как данное утверждение верно при п=k и п = k+1 следовательно (10 п + 18 п – 28) делитсяна 27 прилюбом натуральном п.

Пример 16.

Доказать, что п 3 +11п делится на 6, где п – натуральное число.

1) Проверим, что данное утверждение верно при п=1 :

1 3 +11∙1= 1+11= 12, 12 6.

2) Предположим, что данное утверждение верно, при п=k:

(k 3 +11k) 6.

3) И, докажем, что данное утверждение верно при п=k+1:

((k+1) 3 + 11(k+1)) 6.

(k+1) 3 + 11(k+1)=(k 3 +3k 2 ∙1+3k∙1 2 +1 3 )+11k+11=k 3 +3k 2 +3k+1+11k+11=

= k 3 +3k 2 +14k+12=(k 3 +11k)+(3k 2 +3k+12)=(k 3 +11k)+3(k 2 +k)+12 =((k 3 +11k)+3k(k+1)+12), отсюда

(k+1) 3 + 11(k+1) делится на 6.

Так как данное утверждение верно при п=1 и доказано, что верно при n=k+1 следовательно n 3 +11k делится на 6 при любом натуральном n.

Пример 17.

Доказать, что (11 n +2 +12 2 n +1 ) кратно 133.

2) При n=k. (11 k +2 +12 2 k +1 ) кратно 133.

3) При n=k+1. Доказать, что (11 k +3 +12 2 k +3 ) кратно 133.

В данном выражении второе слагаемое кратно 133, а первое слагаемое кратно 133 из второго пункта. Тогда по свойству делимости полученная сумма кратна 133, значит (11 n +2 +12 2 n +1 ) кратно 133, что и требовалось доказать.

Пример 18.

Доказать, что (n 3 +3n 2 +8n) кратно 3.

1) При n=1. 1+3+8=12, 12 кратно 3 – верно.

2) При n=k. (k 3 +3k 2 +8k) кратно 3 – верно.

3) При n=k+1. Доказать, что ((k+1) 3 +3(k+1) 2 +8(k+1)) кратно 3.

(k+1) 3 +3(k+1) 2 +8(k+1)=k 3 +3k 2 +3k+1+3k 2 +k+1+8k+8=(k 3 +3k 2 +8k)+3k 2 +9k+9. Полученное выражение кратно 3, так как каждое из слагаемых кратно 3. Значит (n 3 +3n 2 +8n) кратно 3, что и требовалось доказать.

Пример 19.

Доказать, что (2 2 n +1 +1) кратно 3.

1) При n=1. 2 3 +1=8+1=9, кратно 3 – верно.

2) При n=k. (2 2 k +1 +1) кратно 3 – верно.

3) При n=k+1. Доказать, что (2 2 k +3 +1) кратно 3.

Источник