6 § Rekurrent munosabatlar metodi va Fibonachchi sonlari

6 - § Rekurrent munosabatlar metodi va Fibonachchi sonlari

Kombimatorikaning ba’zi masalalari rekurrent munosabatlar deb nomlanuvchi, n ta elementli to’plam yoki munosabatlar uchun qo’yilgan masala elementlar soni n dan kichikroq to’plam yoki munosabatlar uchun qo’yilgan masalaning yechimi orqali ifodalanuvchi metod yordamida yechiladi.

6.1 - Ta’rif. Agar x₀, x₁, …, x_n, … sonlar ketma-ketlikning x_n hadi o’zidan oldingi x_n-1, x_n-2, …, x_n-k hadlar orqali x_n = F(x_n-1, x_n-2, …, x_n-k), ko’rinishida ifodalansa, {x_n} ketma-ketlik k-tartibli rekurrent munosabatni qanoatlantiradi deyiladi, bu yerda F – k-o’rinli funksiya.
Ma’lumki, x₀, x₁, …, x_k-1 sonlar berilgan bo’lsa, u holda n  k uchun barcha x_n hadlar bir qiymatli aniqlanadi.
Agar F funksiya chiziqli funksiya bo’lsa, ya’ni
x_n = a₁x_n-1 + a₂x_n-2 + … + a_kx_n-k (6.1)
bo’lsa, u holda rekurrent munosabat chiziqli deyiladi.
6.2 - Ta’rif. {x_n} ketma-ketlik (6.1) ko’rinishdagi k-tartibli chiziqli rekurrent munosabat bo’lsin.
P(x) = x^k – a₁x^k-1– a₂x^k-2– … – a_k (6.2)
ko’phad k-tartibli chiziqli rekurrent munosabatning xarakteristik ko’phadi deyiladi.
Aytaylik  soni P(x) xarakteristik ko’phadning ildizi bo’lsin.
6.1-Teorema. Agar  soni x_n = a₁x_n-1 + a₂x_n-2 + … + a_kx_n-k chiziqli rekurrent munosabatning P(x) xarakteristik ko’phadi ildizi bo’lsa, {cⁿ} ketma-ketlik chiziqli rekurrent munosabatni qanoatlantiradi.
Isbot. Ketma-ketlikning x_n = cⁿ hadlarini rekurrent munosabatga qo’ysak,
x_n – a₁x_n-1 + a₂x_n-2 + … + a_kx_n-k = cⁿ – a₁c^n-1 – a₂c^n-2 – … – a_kc^n-k =
= c^n-k(^k– a₁^k-1 – a₂^k-2 – … – a_k) = 0,
tenglikka ega bo’lamiz. Bundan esa {cⁿ} ketma-ketlik chiziqli rekurrent munosabatni qanoatlantirishi kelib chiqadi. 
6.1-Tasdiq. Agar {u_n} va {v_n} ketma-ketliklar (6.1) ko’rinishdagi k-tartibli chiziqli rekurrent munosabatni qanoatlantirsa, u holda {αu_n + βv_n} ketma-ketlik ham ushbu rekurrent munosabatni qanoatlantiradi.