Rekurrent düstur

Rekurrent düstur və ya rekurrent münasibət — ardıcıllıqın hər hansı həddini ondan əvvəl gələn bir və ya bir neçə hədd vasitəsilə təyin edən düsturdur. Başqa sözlə, belə düstur ardıcıllığın sonrakı hədlərini əvvəlki hədlərə əsasən ardıcıl şəkildə hesablamağa imkan verir.

Ümumi halda dərəcəsi $p$ olan rekurrent düstur belə yazılır:

$a_{n}=f(n,a_{n-1},a_{n-2},\ldots ,a_{n-p}),\qquad n\geq p.$

Burada ardıcıllığın tam müəyyən edilməsi üçün adətən ilk $p$ hədd, yəni başlanğıc şərtlər ayrıca verilir. Məsələn, $a_{0},a_{1},\ldots ,a_{p-1}$ məlumdursa, düstur vasitəsilə bütün sonrakı hədləri hesablamaq olar.

Əsas anlayışlar

Rekurrent düsturun dərəcəsi və ya sırası onun neçə əvvəlki həddən asılı olduğunu göstərir. Məsələn,

$a_{n}=3a_{n-1}+2$

birinci dərəcəli,

$a_{n}=a_{n-1}+a_{n-2}$

isə ikinci dərəcəli rekurrent düsturdur.

Başlanğıc şərtlər verilmədən rekurrent düstur adətən ardıcıllığı tam müəyyən etmir. Məsələn,

$a_{n}=a_{n-1}+a_{n-2}$

münasibəti təkbaşına kifayət deyil; ardıcıllığı müəyyən etmək üçün, məsələn, $a_{0}$ və $a_{1}$ də verilməlidir.

Növləri

Rekurrent düsturlar müxtəlif əlamətlərə görə təsnif edilir.

Xətti rekurrent düsturlar

Əgər ardıcıllığın həddi əvvəlki hədlərin xətti kombinasiyası şəklində verilirsə, belə münasibət xətti rekurrent düstur adlanır. Ümumi forması

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{p}a_{n-p}+g(n)$

şəklindədir.

Əgər $g(n)=0$ olarsa, münasibət xətti bircins rekurrent düstur, əks halda isə qeyri-bircins rekurrent düstur adlanır.

Sabit əmsallı rekurrent düsturlar

Əgər $c_{1},c_{2},\ldots ,c_{p}$ əmsalları $n$-dən asılı deyilsə, belə münasibət sabit əmsallı rekurrent düstur sayılır. Bu tip düsturların həlli üçün çox vaxt xarakteristik tənlik üsulundan istifadə edilir.

Nümunələr

Ən məşhur rekurrent düsturlardan biri Fibonacci ədədləri üçün olan münasibətdir:

$F_{n}=F_{n-1}+F_{n-2},\qquad n\geq 2,$

burada

$F_{0}=0,\qquad F_{1}=1.$

Bu düsturla Fibonacci ardıcıllığının bütün hədləri ardıcıl şəkildə tapılır.

Sadə başqa nümunə həndəsi silsilənin rekurrent yazılışıdır:

$a_{n}=qa_{n-1},\qquad n\geq 1,$

burada $a_{0}$ başlanğıc həddi, $q$ isə silsilənin məxrəcidir.

Həlli

Rekurrent düsturun həlli dedikdə ardıcıllığın ümumi həddini rekursiyasız, yəni qapalı formada ifadə etmək başa düşülür. Xətti sabit əmsallı bircins rekurrent düsturlar üçün əsas üsullardan biri xarakteristik tənlik üsuludur. Daha ümumi hallarda yaradıcı funksiyalar, matris üsulu və ya iterasiya üsulu da tətbiq olunur.

Tətbiqləri

Rekurrent düsturlar diskret riyaziyyatda, kombinatorikada, ədədlər nəzəriyyəsində və alqoritmlər nəzəriyyəsində geniş istifadə olunur. Xüsusilə, rekursiv alqoritmlərin iş vaxtının təhlili çox vaxt rekurrent düsturlar vasitəsilə aparılır.

Tarixi

Rekurrent ardıcıllıqların erkən nümunələri daha qədim riyazi ənənələrdə mövcud olsa da, XVIII əsrdə Abraham de Muavrın recurrent series üzərində apardığı işlər bu sahənin formalaşmasında mühüm yer tutur.

Həmçinin bax

• Ardıcıllıq
• Fibonacci ədədləri
• Həndəsi silsilə
• Diskret riyaziyyat