Элементы дискретной математики - 38 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

38
1.
Сначала докажем, что последовательность f(n)=α
2
n
+ β3
n
является решением
рекуррентного соотношения. Подставим данную последовательность в рекуррентное
соотношение.
f(n)= α 2
n
+ β 3
n
, значит, f(n+1)= (α 2
n+1
+ β
3
n+1
), f(n+2)= α 2
n+2
+ β 3
n+2
, тогда
5f(n+1)-6f(n)=5·( α 2
n+1
+ β
3
n+1
)-6·( α 2
n
+ β 3
n
)= α (5 2
n+1
–6 2
n
)+ β (5 3
n+1
–6 3
n
)=
=α2
n
·(10–6)+ β 3
n
·(15
– 6)= α 2
n+2
+ β 3
n+2
= f(n+2).
Рекуррентное соотношение выполняется, следовательно, α 2
n
+ β 3
n
является решением
данного рекуррентного соотношения.
2.
Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в
виде f(n)= α 2
n
+ β 3
n
. Но любое решение рекуррентного соотношения второго порядка
однозначно определяется значениями первых двух членов последовательности.
Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что
2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для
любых значений а и b.
Таким образом, f(n)= α 2
n
+ β 3
n
является общим решением рекуррентного соотношения
f(n+2)=5f(n+1)–6f(n).
Линейные рекуррентные соотношения с постоянными коэффициентами
Для решения рекуррентных соотношений общих правил нет, но существует часто
встречающийся класс рекуррентных соотношений, для которых известен алгоритм их
решения. Это – линейные рекуррентные соотношения с постоянными коэффициентами, т.е.
соотношения вида:
f(n+k)=c
1
f(n+k-1)+c
2
f(n+k-2)+…+c
k
f(n).
Найдем решение общего линейного рекуррентного соотношения с постоянными
коэффициентами первого порядка.
Линейное рекуррентное соотношение с постоянными коэффициентами первого
порядка имеет вид: f(n+1)=c f(n).
Пусть f(1)=а, тогда f(2)=c·f(1)=c·a, f(3)=c·f(2)=c
2
·a, аналогично f(4)=c
3
·a и так далее,
заметим, что f(n)=c
n-1
·f(1).
Докажем, что последовательность c
n-1
·f(1) является решением рекуррентного
соотношения первого порядка. f(n)=c
n-1
·f(1), значит, f(n+1)=c
n
f(1). Подставляя это выражение
в соотношение, получим тождество c
n
f(1)=с· c
n-1
·f(1).
Рассмотрим теперь подробнее
линейные рекуррентные соотношения с
постоянными коэффициентами второго порядка, то есть соотношения вида

Страницы