Большая Энциклопедия Рефератов от А до Я
Рефераты, курсовые, шпаргалки, сочинения, изложения
Дипломы, диссертации, решебники, рассказы, тезисы
Конспекты, отчеты, доклады, контрольные работы
(7)
А интересующее нас
число e2n равно, очевидно, 2cn–1 (рис. 2д).

а) c1
= 1
|

б) a1
= 2
|

в) an+1
= 2an + 2cn
|

г) cn+1
= an + 2cn
|

д) e2n
= 2cn–1
|
Рис. 2.
а)
|
Из A в
C за два прыжка можно попасть только одним способом: c1 = 1.
|
б)
|
Из A в
A за два прыжка можно попасть двумя способами: a1 = 2.
|
в)
|
В A
можно попасть из C двумя способами и из A двумя способами: an+1 =
2an + 2cn.
|
г)
|
В C
можно попасть из A одним способом и из C — двумя: cn+1 = an
+ 2cn.
|
д)
|
В E
можно попасть из C двумя способами: e2n = 2cn–1.
|
Как же найти
явную формулу для an и cn? Запишем наше рекуррентное
соотношение (7) так: