(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) так: