Лема 3
- корінь рівняння (2), тоді f (n) n - розв’язок (1)
f (n k) n k a1 n k 1 . . . ak n
k a1 k 1 a2 k 2 ... ak
11
Теорема 4 про прості корені (2)
1 , 2 , . . . , k |
прості корені хар.рівняння (2) |
|
( 1 )( |
2 )...( k ) 0 |
i j |
тоді
довільний розв’язок f(n) може бути представлений як
f (n) c1 n1 . . . ck nk |
, де |
c1 ,c2 ,..., ck |
деякі константи |
12 |
13.
ak ≠0 i ≠ 0, i=1,k
f (0), f (1), . . . . . , f (k 1)
c1 c2 |
. . . ck |
f (0) |
|||
|
|
c2 2 . . . ck k |
f (1) |
||
c1 1 |
|||||
|
|
|
. . . . . . . . . . . . . . . . . |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
k 1 |
k 1 |
f |
(k 1) |
|
c1 1 |
|
. . . ck k |
|||
13
14.
1 |
1 |
... |
1 |
|
|
||||
1 |
2 |
... |
k |
|
... |
... |
... |
... |
|
k 1 |
k 1 |
... |
k 1 |
|
1 |
2 |
k |
|
( i j )
i j
14
Співвідношення для кроликів
F(n+1)=F(n)+F(n-1), F(0)=1, F(1)=2
|
1 |
1 |
|
|
, |
2 |
1 |
|
|
|
|||||||
2 1 |
5 |
5 |
|||||||||||||||
|
|
|
|
2 |
|
|
|||||||||||
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|||||
|
|
1 |
|
n |
|
|
|
|
|
1 |
|
|
n |
||||
F (n) c1 |
5 |
c2 |
5 |
||||||||||||||
|
2 |
|
|
|
|
2 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
15
|
|
|
c1 |
|
|
|
|
|
|
c2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
5 |
|
|
|
1 |
5 |
|
||||
c |
|
c |
2 |
2 |
|||||||||
|
1 |
|
2 |
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
|
3 |
|
|
|
|
|
1 |
|
3 |
|
|
|
|||
c1 |
|
1 |
|
5 |
, c2 |
|
1 |
|
5 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
2 |
5 |
2 |
5 |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
3 |
|
|
1 |
|
n |
|
|
3 |
|
|
1 |
|
|
n |
|
1 |
5 |
5 |
1 |
5 |
|
5 |
||||||||||
|
|
5 |
|
2 |
|
|
|
5 |
|
|
2 |
|
|
||||
F (n) |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16
f(n+k)=a1f(n+k-1)+a2f(n+k-2)+……(1)
…..+ak-1 f(n+1)+akf(n)
лінійне, однорідне, k-го порядку рекурентне співвідношення
f(n) - розв’язок
k=a1 k-1+a2 k-2+……+ak |
(2) |
Характеристичне рівняння для рекурентного співвідношення (1)
17
Лема 1. Розв'язок f(n) рекурентного співвідношення
(1) однозначно визначається першими k значеннями f(0), f(1), f(2),…f(k-1).
Лема 2. Якщо f1 (n), f 2 (n), . . . , f m (n)
Розв'язки співвідношення (1), то
f (n) c1 f1 (n) . . . cm f m (n)
також розв'язок співвідношення (1)
Лема 3. Якщо корінь рівняння (2), то f(n)= n розв'язок співвідношення (1)
Теорема 4. Якщо 1, 2, …. k – всі прості корені рівняння (2), то загальний розв'язок (1) f (n) c1 n1 . . . ck nk
18
15.Теорема 5 про кратні корені (2)
1 корінь кратності k1 ,..., s ks
k1 k2 . . . ks k
(2)( 1 )k1 ....( s )ks 0
тоді
1.nj , n nj , n 2 n j , . . . , n k j 1 nj
j=1,...s, розв’язки співвідношення (1)
19
16.
2. Загальний розв’язок (1) |
f (n) |
|
s |
|
nk j 1 nj |
Cj,1 |
Cj,2 n ... Cj,k j |
|
j 1 |
|
|
C j,m - |
довільні константи |
|
j =1,...s, m =1,...k j
20