Relasi Rekurensi Linear, Tak Linear, Homogen dan Tidak Homogen

martha yunanda kombinatorika

Berbagai ragam permodelan counting dengan mengaplikasikan relasi rekurensi bisa diselesaikan dengan iterasi atau teknik lainnya. Sebuah relasi rekurensi bisa diselesaikan dengan eksplisit dan sistematik. Relasi rekurensi semacam ini adalah rekurensi yang menyataka suku barisan sebagai kombinasi linear suku sebelumnya.

Pengertian dan defenisi Relasi rekurensi linear homogen adalah Rekurensi Linear Homogen dengan derajat k dengan koefisien tetapan merupakan rekurensi dengan bentuk,

$a_n = c_1a_{n-1} + c_2a_{n-2} + \ldots + c_ka_{n-k}+ f(n)$
dengan

$c_1,c_2,…,c_k$ adalah bilangan real,

$c_k$ ≠0, dan f(n) adalah fungsi n.

Relasi Rekurensi dari pengertian di atas dikenal dengan linear karena tak ada pangkat atau perkalian

$a_j$ .

Sebuah relasi rekurensi disebut homgen jika f(n)=0, sementara untuk f(n)≠0 disebut nonhomogen.

Tetapan

$c_1,c_2,…,c_n$ tidak bergantung nilai n. Orde k terjadi jika

$a_n$ diekspresikan dalam k suku sebelumnya.

Dari prinsip kedua induksi matematika, barisan yang memenuhi relasi rekurensi pada pengertian diatas ditentukan dengan cara tunggal oleh relasi rekurensi ini dengan k syarat awal

$a_0=C_0,a_1=C_1,…,a_{k−1}=C_{k−1}$

Artinya syarat awal relasi rekurensi menentukan ketunggalan solusi dari relasi rekurensi. Perhatikan 2 contoh relasi rekurensi di bawah ini,

Contoh Relasi Rekurensi :

Relasi rekurensi $P_n=(1,11)P_{n−1}$ adalah relasi rekurensi linier homogen dengan orde satu.
Relasi rekurensi $f_n=f_{n−1}+f_{n−2}$ adalah relasi rekurensi linier homogen dengan orde dua. Relasi rekurensi $a_n=a_{n−5}$ merupakan relasi rekurensi linier homogen dengan orde lima.
Relasi rekurensi $a_n=a_{n−1}+a^2_{n−2}$ tidak linier.
Relasi rekurensi $H_n=2H_{n−1}+1$ tidak homogen.
Relasi rekurensi $B_n=nB_{n−1}$ tidak memiliki koefisien yang konstan.