Составители:
Рубрика:
37
К сожалению, задачу нельзя считать решенной, так как, хотя получено выражение,
зависящее от n, его вычисление оказывается даже сложнее рекуррентных расчетов.
Желаемую формулу можно получить совсем другим способом.
Решение рекуррентных соотношений
Рекуррентное соотношение имеет порядок k, если оно позволяет выразить f(n+k)
через f(n), f(n+1), …, f(n+k-1).
Пример.
f(n+2)=f(n)f(n+1)-3f
2
(n+1)+1 – рекуррентное соотношение второго порядка.
f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.
Если задано рекуррентное соотношение k-го порядка, то ему могут удовлетворять
бесконечно много последовательностей, так как первые k элементов последовательности
можно задать произвольно – между ними нет никаких соотношений. Но если первые k
членов заданы, то все остальные элементы определяются однозначно.
Пользуясь рекуррентным соотношением и начальными
членами, можно один за
другим выписывать члены последовательности, при этом рано или поздно мы получим
любой её член. Однако если необходимо узнать только один определенный член
последовательности, то нерационально вычислять все предыдущие. В этом случае удобнее
иметь формулу для вычисления n-го члена.
Решением рекуррентного соотношения называется любая последовательность, для
которой данное соотношение выполнено тождественно.
Пример.
Последовательность 2, 4, 8, …, 2n является решением для соотношения
f(n+2)=3·f(n+1) – 2·f(n).
Доказательство:
Общий член последовательности имеет вид f(n)=2
n
. Значит, f(n+2)= 2
n+2
, f(n+1)= 2
n+1
.
При любом n имеет место тождество 2
n+2
=3·2
n+1
– 2·2
n
. Следовательно, при подстановке
последовательности 2
n
в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется
тождественно. Значит, 2
n
является решением указанного соотношения.
Решение рекуррентного соотношения k-го порядка называется общим, если оно
зависит от k произвольных постоянных α
1
, α
2
, … α
k
и путем подбора этих постоянных
можно получить любое решение данного соотношения.
Пример.
Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее
решение имеет вид: f(n)= α
2
n
+ β3
n
.
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
