6 § Rekurrent munosabatlar metodi va Fibonachchi sonlari

6.2-Teorema. Aytaylik, ₁, ₂, …, _k sonlar (6.1) chiziqli rekurrent munosabatni P(x) xarakteristik ko’phadi sodda (karrali bo’lmagan) ildizlari bo’lsin. U holda bu rekurrent munosabatning umumiy yechimi quyidagi ko’rinishga ega bo’ladi:
u_n = c₁ + c₂ + … + c_k (6.3)
Isbot. Yuqoridagi 6.1-Teorema va 6.2-Tasdiqlardan (6.3) ko’rinishidagi ketma-ketlik (6.1) rekurrent munosabatni qanoatlantirishi kelib chiqadi.
Endi (6.1) rekurrent munosabatni qanoatlantiruvchi ixtiyoriy ketma-ketlik (6.3) ko’rinishda ekanligini ko’rsatamiz.
Faraz qilaylik, {v_n} ketma-ketlik (6.1) rekurrent munosabatni qanoatlantirsin. Ma’lumki, v_n = u_n tenglikni ko’rsatish uchin u₀ = v₀, u₁ = v₁, …, u_k-1 = v_k-1 tengliklarni ko’rsatish yetarli.
Ushbu tenglamalar sistemasini qaraymiz

₁, ₂, …, _k sonlar turli bo’lganligi uchun yuqoridagi sistemaning asosiy determinanti

noldan farqli bo’ladi.
Demak, v₀, v₁, …, v_k-1 larning ixtiyoriy qiymatida u_i=v_i, 0  i  k-1 tenglik o’rinli bo’ladigan c₁, c₂, …, c_k sonlari mavjud. Bundan esa v_n=u_n tenglik kelib chiqadi. 
6.1-Misol. u₀ = 1, u₁ = 1 boshlang’ich shartlar u_n = u_n–1 + u_n–2 rekurrent munosabat bilan berilgan ketma-ketlikni qaraylik.
Ushbu ketma-ketlik
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …
ko’rinishga ega bo’lib, Fibonachchi sonlari deb ataladi.
Ushbu u_n = u_n–1 + u_n–2 rekurrent munosabatning xarakteristik ko’phadi P(x) = x² – x – 1 ko’rinishda bo’lib, uning idizlari bo’ladi. Bundan Fibonachchi sonlarining umumiy ko’rinishini hosil qilamiz:
.
_u0 =1 va u₁=1 ekanligidan

sistemaga ega bo’lamiz. Bu sistemadan kelib chiqadi.
Agar (6.1) chiziqli rekurrent munosabatning P(x) xarakteristik ko’phadi mos ravishda r₁, r₂, …, r_s karrali ₁, ₂, …, _s ildizlarga ega bo’lsa, quyidagi teorema o’rinli.