Возвратные задачи (стр. 6 из 9)
=
Из пунктов 1 и 2 следует: при n ≥ 0
Задача 7.Пусть H(n) = J(n+1)−J(n). В силу уравнения (7) (см. теорию) H(2n) = J(2n+1)− J(2n) 
(2J(n)+1) − (2J(n)−1) = 2, aH(2n+1) = J(2n+2)− −J(2n+1) = (2J(n+1)−1)−(2J(n)+1) = 2H(n)−2 при всех n≥1. Поэтому представляется возможным доказать индукцией по n, что H(n)=2 при всех n. Что здесь не верно?
Решение. Ошибка заключается в том, что в данном рассуждении хотят доказать по индукции, что H(n)=2 при всех n (показали, что данное равенство выполняется для чисел вида 2nи 2n+1, т.к. любое натуральное число можно представить в таком виде), но при этом не проверили базу индукции (т.е. когда n принимает свое наименьшее значение: n = 1).
H(1) = J(2) − J(1) = 2J(1) −1 − J(1) = 2∙1−1−1 = 0
H(1) 
2 база индукции не выполняется, следовательно равенство H(n)=2 верно не при всех n.Задача 8.Решите рекуррентное соотношение
Q0 = α, Q1 = β,
Qn = 
при n>1.
Примите, что Qn ≠ 0 при всех n ≥ 0.
Решение.
; 
; 
; 
; 
; 
; 
; 
.
Получили:
; 
; 
; 
; 
.Обобщая, приходим к выводу, что данная последовательность периодическая: если n = 5k+r (
), тогда 
(для n ≥ 5)Докажем методом математической индукции:
1) База: n=5
(верно, показано выше);n=6
(верно, показано выше);n=7
(верно, показано выше);n=8
(верно, показано выше);n=9
(верно, показано выше);2) Индуктивный переход: пусть верно для всех чисел t≤(n−1). Докажем для t=n: n= 5k + 0, тогда
;· n = 5k + 1, тогда
;· n = 5k + 2, тогда
;· n = 5k + 3, тогда
;· n = 5k + 4, тогда
.Из пунктов 1 и 2 следует: для n ≥ 5
.Ответ:
при всех n ≥ 0 и k, r 
Z+.Задача 9.Иногда возможно использование «обратной индукции», т.е. доказательства от n к n−1, а не наоборот. К примеру, рассмотрим утверждение
P(n): 
≤ 
, если x1,x2,…,xn ≥ 0
Оно справедливо для n=2, так как 
(x1+x2)2 − 4x1x2 = (x1−x2)2 ≥ 0.
a) Полагая 
, докажите, что P(n) влечет P(n−1) при всяком n > 1.
b) Покажите, что P(n) и P(2) влекут P(2n).
c) Объясните, почему отсюда следует справедливость P(n) при всех n.
Решение.а) подставим
в P(n):P(n):
≤ 
преобразуем правую скобку:
= 
получили:
≤ 
разделим левую и правую части неравенства на
(эта скобка не равна нулю, т.к. x1,x2,…,xn>0 и n > 1, т.к. случай всех хi=0 тривиальный, поэтому мы его не рассматриваем 
)получим P(n−1):
≤ 
.Следовательно, при
P(n) влечет P(n−1) при всяком n>1.b) запишем P(n) для двух конечных последовательностей чисел.
P(n):
≤ (для nпервых членов) 
≤ 
(для nчленов начиная с 
)перемножим эти два неравенства, используя свойство неравенств: если 0<a<bи 0<c<d, то ac<bd. Получим:
≤ 
.Преобразуем правую скобку неравенства, используя утверждение Р(2)
P(2):
,возведем левую и правую части неравенства в n-ую степень, получим
≤ 
Таким образом, получили:
P(2n):
≤ .Следовательно, P(n) и P(2) влекут P(2n).
c) Выше было показано, что из P(n) следует P(n−1), а из P(n) и P(2) следует P(2n). Следовательно, мы можем утверждать, что P(n) выполняется для любого n > 1, т.к. P(от нечетного числа n) следует из P(от четного числа (n−1)), а P(от четного числа) следует из P(2) и P(от четного или нечетного числа) и т.д., в конечном итоге приходим к P(2), а оно выполняется.