Soal matematika informatika tentang relasi rekursif

1. Diketahui suatu barisan c0, c1, c2, … didefinisikan secara rekursif sebagai berikut :

Untuk semua bilangan bulat k ≥ 2, Ck = (ck-1 + k) (ck-2 + 1). Dengan kondisi awal c0 = 1 dan c1 =2.

Ditanya : Hitunglah c5 !

Pembahasan :

Oleh karena barisan didefinisikan secara rekursif, maka c5 tidak bias dihitung secara langsung, tetapi harus terlebih dahulu menghitung c2, c3 dan c4.

c2 = c1 + 2 c0 + 1 = 2 + 2.1 + 1 = 5

c3 = c2 + 3 c1 + 1 = 5 + 3.2 + 1 = 12

c4 = c3 + 4 c2 + 1 = 12 + 4.5 + 1 = 33

c5 = c4 + 5 c3 + 1 = 33 + 5.12 + 1 = 94

Jadi, c5 = 94

2. Solusi homogen dari relasi rekurensi bn + bn-1 – 2 bn-2 = 0 dengan kondisi batas b0 = 2 , b1 = 3 adalah…

Pembahasan :

bn + bn-1 – 2 bn-2 = 0

= a2 + a- 2 = 0

= (a+ 2) (a- 1) = 0

a1 = -2     a2 = 1.

Solusi homogen = bn(h)= A1 a1n+ A2 a2n       =>bn(h)= A1 (-2)n+ A2 . (1)n

Dengan kondisi batas b0= 2 dan b1= 3 ,maka:

b0(h) = A1 (-2)(2) + A2 . 1(2) =>  0  = -4 A1 + 2 A2

b1(h) = A1 (-2)(3) + A2 . 1(3) =>  1 =  -6 A1 +  3A2

-4 A1 + 2 A2 = 0       x  3       -12A1 +  6 A2  =  0

-6 A1 + 3A2 =  1       x 2        -12A1 +  6 A2  =  2    +
6A2 = 2

A2 = 1/3

-4A1 + 2A2 = 0

-4A1 + 2(1/3) = 0; A1 = 1/6

Maka akan diperoleh harga A1 = 1/6 dan A2 =1/3.

Jawab homogen dari relasi rekurensi bn + bn-1 – 2bn-2 = 0 adalah

bn(h) =  1/6(-2)n + 1/3. (1)n

3. Mana diantara berikut yang merupakan solusi dari relasi rekurensi  dari :

a_n + 4 a_n-1 + 4 a_n-2 = 0

Pembahasan :

Relasi rekurensi homogen :                        a_n + 4 a_n-1 + 4 a_n-2 =0.

Persamaan karakteristiknya adalah             a²  +  4 a  + 4 = 0

(a+ 2) (a + 2) = 0

Akar-akar karakteristik   a₁ = a₂ = -2 ,  m = 2, Oleh karena akar-akar karakteristiknya ganda, maka solusi homogennya berbentuk:

                    a_n^(h)  = (A₁ n^m-1 + A₂ n^m-2) a₁ⁿ  ,a_n^(h)  = (A₁ n + A₂ ) (-2)ⁿ

4. Tentukan solusi homogen dari :
bn + 2bn-1 – 8bn-2 = 0; dengan batas b0 = 4 & b1 = 3

Pembahasan :

Kita ubah dulu bn menjadi α maka
α² + 2α – 8 = 0
(α – 4) (α + 2)
α1 = 4 & α2 = -2 maka
an = A1a1^n + A2a2^n
= A1(4)^n + A2(-2)^n
b0 = 4 = A1(4)^0 + A2(-2)^0
4 = A1 + A2
b1 = -2 = A1(4)^1 + A2(-2)^1
-2 = 4A1 – 2A2

Proses eliminasi:
4    =  A1   +   A2  | x2 |    8   =  2A1 + 2A2
-2  =  4A1 – 2A2   | x1 |   -2   =  4A1 – 2A2
—————- +
6   =  6A1
A1  =  1
A2  =  3  sehingga
an  =  A1a1^n + A2a2^n
=  1(4)^n + 3(-2)^n

5. 3an – 5an-1 + 2an-2 = n²+ 5
Diketahui : a₃ = 3 , a₄ = 3
Tentukan : a₅ = ?

Pembahasan :

C0 = 3
C1 = -5
C2 = 2
K = 2
F(n) = n² + 5

6. Tentukan solusi dari relasi rekurensi an + 6an-1 + 9an-2 = 0 !

Pembahasan :

Relasi rekurensi homogen : an + 6an-1 + 9an-2 = 0.
Persamaan karakteristiknya adalah
a2 + 6a + 9 = 0
(a + 3) (a + 3) = 0
Hingga diperoleh akar-akar karakteristiknya a1 = a2 = -3, m = 2.
Oleh karena akar-akar karakteristiknya ganda, maka solusi homogennya berbentuk
an (h) = (A 1 n m-1 + A 2 n m-2 ) a1n
an (h) = (A 1 n + A 2) (-3) n .

7. Tentukan solusi homogen dari relasi rekurensi bn + bn-1 – 6 bn-2 = 0 dengan kondisi batas b0 = 0 , b1 = 1 .
a. bn(h) = (-3)n + .2n
b. bn(h) = 3n + .2n
c. bn(h) = (-2)n + .3n
d. bn(h) = (-3)n + .2n
e. bn(h) = 3n + .3n

Pembahasan :

Relasi rekurensi tersebut adalah relasi rekurensi homogen, karena f(n)=0.
Persamaan karakteristik dari relasi rekurensi bn + bn-1 – 6 bn-2 = 0 adalah a2 + a – 6 = 0 atau (a+ 3) (a – 2) = 0 hingga diperoleh akar-akar karakteristik a1 = -3 dan a2 = 2.
Oleh karena akar-akar karakteristiknya berbeda, maka solusi homogennya berbentuk bn(h) = A1a1n + A2 a2n Þ bn(h) = A1 (-3)n + A2 . 2n.
Dengan kondisibatas b0 = 0 dan b1 = 1 ,maka:
b0(h) = A1 (-3)0 + A2 . 20 Þ 0 = A1 + A2 .
b1(h) = A1 (-3)1 + A2 . 21 Þ 1 = -3 A1 + 2 A2 .
Bila diselesaikan maka akan diperoleh harga A1 = (-1/5) dan A2 = 1/5 , sehingga jawab homogen dari relasi rekurensi bn + bn-1 – 6 bn-2 = 0 adalah bn(h) = (-3)n + .2n

8. Tentukan solusi homogen dari relasi rekurensi 4 a_n - 20 a_n-1 + 17 a_n-2 – 4 a_n-3 = 0. 

Penyelesaian :

Persamaan karakteristiknya:                       4 a³  - 20 a² + 17 a  - 4 = 0

Akar-akar karakteristiknya:                          ½ , ½  dan   4

Solusi homogennya berbentuk:                     a_n^(h)  = (A₁ n + A₂ ) (½)ⁿ + A₃ . 4ⁿ.

9. Selesaikan relasi rekurensi an = 7an -1 , n > 1, a2= 98

Jawab:

Untuk n = 1 maka a₁ = 7 a₀  a₂ = 7 a₁ = 7  (7 a₀) = 72a₀ dari a₂ = 98 maka 98 = 49 a₀

sehingga diperoleh a₀ = 2. Jika relasi rekurensi tersebut dideretkan terus akan diperoleh :

a₃ = 7 a₂ = 7 (7² a₀) = 7³ a₀ ……….dan seterusnya

sehingga penyelesaian umum dari relasi rekurensi di atas adalah:

an= 7n (2) , n > 0

10. an = an – 2 – an – 1 untuk n > 2
a0 = 10 dan a1 = 5 Tentukan a2 dan a4.

Jawab :
an = an – 2 – an – 1
a2 = a2 – 2 – a2 – 1
= a0 – a1
= 10 – 5
a2 = 5

a4 = a2 – a3
= 5 – a2
= 5 – 5
= 0