Смекни!
smekni.com

Возвратные задачи (стр. 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 = (x1x2)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), а оно выполняется.