146101220076616226243270535984 n

Twierdzenie 2

Niech <s_n) będzie ciągiem spełniającym zależność rekuren-cyjną postaci

$2n =2 ’S„ + f(n) dla n € F.

Wtedy

52"

dla 771 e N.

W szczególności, jeśli

•*2n = 2 • Sn -f >1 4* B - Tl dla pewnych stałych .4 i S. to

D

.*2" = 2^m • 5! + (2^m - 1) • A + - • 2"' • m. Zatem, jeśli n — 2^m. to w tym przypadku mamy s_n = nsj + (n - 1)j4 + — • n • log₂ n.

xtr. 13/15