RELASI REKURSI
DERNISI RELASI REKURSI Dalam pembahasan pada Bab 8 terdahulu mengenai pengacakan suatu himpunan bilangan bulat {1,2, ...n} diperoleh bilangan Dn yang menunjukkan jumlah pengacakan yang mungkin dilakukan untuk himpunan tersebut. Dalam hal ini Dn memenuhi relasi rekursi berikut ini: (9.1) atau On dapat juga memenuhi persamaan (9.2) Oi sini harga n berjalan dari 2,3, dan seterusnya. Penulisan On dalam bentuk di atas merupakan contoh penulisan relasi rekursi yang tergantung n. Pada rumus (9.1) di atas ditunjukkan bagaimana jumlah pengacakan dari himpunan yang terdiri dari n elemen dapat dihitung dari jumlah pengacakan dari himpunan yang terdiri dari n-l dan n-2 elemen. Bila ditentukan syarat awal bahwa 0l = 0 dan 02 = 1, maka barisan bilangan pengacakan berikutnya 03' 04' ...Dn dapa tdengan mudah dihitung. Sedangkan pada rumus (9.2) di atas, harga Dn dapat dihitung bila harga Dn_l diketahui. Dengan demikian hanya diperlukan satu harga awal saja yaitu nilai Dl = O. Berdasarkan harga ini dapat dihitung barisan bilangan pengacakan yang nilainya akan sarna dengan barisan yang dibentuk oleh persamaan (9.1) dengan dua syarat awal yang telah disebutkan sebelum ini.
Definisi 9.1 Relasi rekursi yang tergantung pada harga n adalah barisan bilangan ao, al, ~, dan seterusnya sampai an' dengan an dapat dinyatakan sebagai fungsi dari n harga aj sebelumnya. Relasi rekursi ini sangat berguna untuk menentukan jawab dari berbagai problema yang serupa dan hanya berbeda pada jumlah obyek yang ada dalam 152
problema tersebut. Biasanya jawab umum dari an yang memenuhi relasi rekursi dapat diperoleh secara eksplisit. Hal ini di antaranya dapat dilakukan dengan cara menerka bentuk umum dari jawab yang memenuhi problema tersebut. Hal ini dapat dilakukan dengan menggunakan iterasi dati relasi rekursi yang ada atau dengan menerka rumus yang ada lalu membuktikan kebenaran dari rumus tersebut dengan menggunakan induksi matematik. Cara lain yang juga dapat digunakan adalah dengan menggunkan c~ra fungsi pembangkit atau generating function.
CONTOH Contoh 9.1 Untuk n >= I misalkan an menyatakan banyaknya permutasi yang dapat diperoleh dari himpu~an bilangan {1,2,...,n}. Int berarti an_Iadalah banyaknya permutasi yang dapat dilakukan pada himpunan bilangan {I ,2,...,n-l }. Tetapi bila telah dapat diperoleh semua permutasi yang mungkin dari himpunan {1,2, ...,n-l} tersebut, maka dengan meletakkan bilangan n pada se~iappermutasi yang ada di n tempat yang mungkin, yaitu di tempat paling depan. di antara dua bilangan atau di tempat yang paling belakang, maka dapat diperoleh semua permutasi dari himpunan bilangan { 1,2,..n}. Karena untuk setiap permutasi dari n-l bilangan dapatdiletakkan bilangan n di n tempat yang berbeda maka dapat diperoleh rumus rekursi berikut ini:
Rumus ini berlaku untuk setiap n
= 2,
3, 4, dan seterusny'a.
Karena untuk harga n = 1 jelas hanya ada 1 permutasi yang mungkin maka syarat awal adalah al = I. Dan dengan menggunakan iterasi dapat diperoleh
bahwa an
=
nan_I
= = =
n(n-I )an_2 n(n-l)(n-2)an_3
n(n-1)(n-2)(n-3)...3x2xl = n!
Dari sini diperoleh bahwa an = I! , adalah banyaknya permutasi himpunan yang terdiri dari n bilangan bulat {I, 2, ...n}. 153
Cara lain yang dapat digunakan dalam memecahkan problema ini adalah dengan menerka jawab ini dengan menggunakan induksi matematik dan relasi rekursi yang terdefmisi. Dalam hal ini terkaan dilakukan setelah melakukan beberapa perhitungan dari ~ = 2, ~ = 6 dan seterusnya.
BAR/SAN RBONACC/ Kita bahas mula-mula relasi rekursi yang paling terkenal dan sering digunakan, yakni barisan Fibonacci. Relasi rekursi ini merupakan salah satu relasi rekursi yang paling tua di dunia, dibahas dalam buku Liber Abacci yang ditulis oleh Leonardo of Pisa yang lebih dikenal dengan nama Fibonacci tahun 1202. Pada saat itu dicoba dihitung jumlah pasangan kelinci yang ada, bila setiap pasangan kelinci setiap bulan dapat menghasilkan sepasang anak kelinci barn. Problema yang diberikan oleh Fibonacci pada saat itu adalah sebagi berikut. Sepasang kelinci dipelihara pada suatu waktu tertentu. Setiap bulan, kelinci betina akan melahirkan sepasang anak kelinci jantan dan betina. Pada awal bulan berikutnya setiap pasang kelinci yang telah berumur lebih dari satu bulan akan melahirkan sepasang anak kelinci barn. Yang harns ditentukan adalah jumlah pasangan kelinci yang ada setelah waktu satu tahun. Selama bulan pertama, hanya ada sepasang kelinci. Bulan kedua ada dua pasang kelinci. Sedangkan pada bulan ketiga hanya ada 3 pasang kelinci karena pasangan kelinci yang muda belum dapat melahirkan kelinci. Pada bulan ketiga ada 2 pasang kelinci yang sudah berumur lebihdari I buan, sehingga dari tiga pasang kelinci yang yang ada hanya ada dua pasang yang bisa melahirkanpasangan kelinci barn. Jadi jumlah pasangan kelinci yang ada pada bulan ketiga adalah 2+3=5. bila jumlah kelinci yang ada pada bulan ke-n adalah an' maka diperoleh a1=1'~=2, ~=3 , a4=5 dan seterusnya dan yang ditanyakan adalah a13. Cara yang paling mudah untuk menyelesaikan problema ini adalah dengan membentuk relasi rekursi untuk an' kemudian bila telah diketahui harga awal ai' ~, maka dengan mudah diperoleh a13. Pada setiap permulaan bulan ke n, ada sejumlah pasangan kelinci yang sudah ada sejak bulan ke n-l dan selain itu juga ada kelinci yang barn dilahirkan pada bulan n-l, oleh pasangan kelinci yan gtelah ada sejak bulan ke n-2. Dengan demikian pada setiap permulaan bulan ke n ada sejumlah an_I+ an_2pasangan kelinci, sehingga diperoleh relasi rekursi berikut:
154
untuk n
= 3, 4, ...
Karena telah diketabui bahwa harga a)=), ~=2, ~=3, a4= 5 maka selanjutnya 377. Jadi dengan menggunakan rumus di atas dapat dihitung bahwa an setelah satu tabun akan terdapat 377 pasang kelinci.
=
Detinisi 9.2 Bila syarat awal diberikan harga e10= 1, dan a) = 1, maka bilangan yang diperoleh dengan menggunakan rumus rekursi berikut
untuk n
= 2,
3, 4, ... disebut barisan Fibonacci, dan suku an disebut bilangan
Fibonacci. Dari perhitungan selanjutnya akan diperoleh barisan Fibonacci seperti berikut
1, 1, 2, 3, 5, 8, 13, 34, 55, 89, 144, 233, 377, 610, ...
SIFAT BARIS AN FIBONACCI Barisan Fibonacci mempunyai banyak sifat.
Sitat 9.1 Jumlah barisan Fibonacci dapat ditulis
155
Bukti Pembuktian dilakukan dengan mudah menggunakan induksi matematik. untuk
harga n. Jelas bahwa relasi benar untuk n = 0, yaitu ao = ~ - I, karena 1 = 2 -I. Untuk harga n positif lainnya misalkan bahwa rumus benar untuk harga n-I, yakni bahwa
Maka untuk setiap n 30 + a1 +
~ + ... + an =
=
[30 + a1 + ~ + ...an_l]+ an
= =
an+1 + an
=
an+2
[an+1
- I]
+ an
-1
-I
Sifat lain dari barisan Fibonacci yang sangat penting dan tidak kalah menariknya dengan sifat (9.1) di atas adalah sifat 9.2 berikut
Sifat 9.2 Bilangan Fibonacci memenuhi a
n= _1
(1 + --J5 ) n+l --J5 ( 2)
_1
(1 - --J) n+l
--J5 (
2
)
untuk setiap n = 0, 1, 2, 3, ... Kalau diperhatikan maka sifat (9.2) di atas melibatkan bentuk --J5,suatu bilangan irrasional. Tetapi hasil dari an pada rumus di atas adalah suatau barisan bilangan bulat positif. Yang menjadi problema adalah bagaimana caranya memperoleh sifat (9.2) di atas? Untuk menjawab pertanyaan ini harus dipelajari terlebih dahulu cara penyelesaian persamaan rekursi dengan menggunakan teknik akar karakteristik 156
dari suatu persamaan diferensi (differenceequation). Cara penyelesaian persamaan diferensi ini akan dipelajari pada bab lain dalam buku ini. Bilangan Fibonacci sering sekali timbul pada problema kombinatorial. Salah satu rumus penting lain yang menghubungkan harga barisan fibonacci dan jumlah koefisien binomial dapat dinyatakan dalam sifat berikut ini: Sifat 9.3 Jumlah dari koefisien binomial sepanjang diagonal segitiga Pascal bennula dari kiri dan bergerak ke atas akan membentuk barisan Fibonacci. Atau secara lebih tepat: Setiap bilangan Fibonacci an memenuhi
+ ...
dengan k
= [~ ]
Buldi Misalkan jumlahan di atas ditulis sebagai bn. dan akan ditunjukkan bahwa bn akan memenuhi relasi rekursi dari barisan Fibonacci, erta bnjuga memenuhi harga awal dari barisan Fibonacci yaitu bo = 1 dan bl.
dengan
k
= [~]
Sedangkan telah juga diketahui bahwa untuk semua harga p>n, maka (n) = O. Jadi bentuk di atas dapat juga ditambahkan beberapa suku (p) lagi ,sehingga diperooleh jumlah berikut
157
=
(~) +
(~-1)
+
(n-;) +... r-~) +... (~)
Sekarang baru akan ditunjukkan bahwa bn adalah barisan Fibonacci. Pertama-tama akan ditunjukkan dulu bahwa bo = 1 dan b t = I. Hal ini ditunjukkan karena
Berikutnya akan ditunjukkan bahwa bn akan rnernenuhi relasi rekursi Fibonacci yaitu bn_2+ bn_t = bn, Untuk ini digunakan rumus Pascal berikut untuk
n;:::2.
= (n~l)
+
(n~2) +... (~_I) +
(n~2) + (n~3) +.., (~2)
=
= Bentuk yang terakhir ini adalah sarna dengan bn. Jadi oleh bn dipenuhi juga relasi rekursi Fibonacci. 158
RELASI REKURSI
LINIER BERKOERSIEN KONSTAN
Barisan Fibonacci merupakan salah satu contoh barisan bilangan yang memenuhi suatu relasi rekursi tertentu. Secara umum relasi rekurSi yang tinier berkoetisisn konstan dapat dituliskan sebagi berikut:
di sini setiap harga Cj adalah kotlstan. Relasi rekursi ini disebut sebagi relasi rekursi derajat ke-k, jika Co dan Ck keduanya tidak bemilai O.
Contoh 9.2 Relasiberikutadalahrelasirekursi linierderajatke-l berkcietisienkonstan: 2ar + 2ar_1 = 2r, atau - 5ar_1 = 4r.
3ar
Sedangkan kedua relasi rekursi berkoetisien konstan:
atau
berikut ini adalah tinier derajat ke-2
3ar - 5ar_1+ 2~_2 = r2 + 5. ar + 7 ~-2
=0
Pada relasi rekursi berikut
yang berlaku untuk setiap harga r=2,3,4,... Bila diberikan harga ~=3 dan a4 = 6, maka dapat dihitung harga
as
=-
3
[-5 x 6 + 2 x 3 - (52 + 5) ] = 18
159
selanjutnya juga dapat dihitung harga a6 sebagai
_1
~
= -3
119
[-5 x 18 + 2 x 6 - (62 + 5)]
=- 3
dan seterusnya. Selain itu juga dapat dihitung harga ~, ai' 30 sebagai ..1 ~ = 2 [3 x 6 - 5 x 3 - (42 + 5)] 9
-
=
_1
a1 = -2 [3 x 3 - 5 x 9 - (32 + 5)] = 25 -1
30
=-2
[3 x 9
- 5 x 25 -
107
(22 + 5)]
=- 2
demikian selanjutnya. Jadi dapat disimpulkan bahwa bila diketahui relasi rekursi derajat ke-2 dan "diketahui dua harga ~ = 3 dan a4 = 6, maka dapat diperoleh hanya satu barisan bilangan yang memenuhi relasi rekursi tersebut. Secara umum, untuk suatu relasi rekursi derajat ke-k berkoetisien konstan seperti dituliskan di atas, maka bila diberikan k harga aj yang berturutan , amok' am-k-1,...am_1untuk suatu harga myang tertentu, maka setiap harga am yang lain pasti dapat ditentukan, yaitu dengan rumus
dan selanjutnya harga am+1juga dapat dihitung sebagai
demikian pula untuk semua harga ~+2' am+3dan seterusnya. Di lain pihak harga ~-k-l juga dapat dihitung sebagai
160
dan harga '\n-k-2 adalah.
Nilai am-k-3dan seterusnya juga dapat.dihitung dengan cara yang sarna. Jadi untuk setiap relasi rekursi linier derajat ke-k berkoetisien konstan, bila diketahui harga-harga k buah ai' yang berturutan maka dapat ditentukan harga-harga ~ lainnya secara unik. Dengan perkataan lain, k buah harga-harga ~, yang diberikan merupakan himpunan syarat batas yang hams dipenuhi oleh relasi rekursi tersebut untuk dapat memperoleh harga-harga yang unik. Cara lain untuk menyatakan hal ini adalah bila pada suatu relasi rekursi derajat ke k berkoetisien konstan, hanya ditentukan kurang dari k buah ~ yang berturutan. maka hal ini tidak akan dapat ~enentukan fungsi yang memenuhi relasi tadi secara unik. Sebagai contoh bila dipilih relasi berikut
kemudian diberikan salah satu syarat batas 30 == 2, maka akan ada banyak fungsi numerik yang akan memenuhi relasi rekursi tersebut dan juga memenuhi syarat batas yang diberikan. Berikut ini adalah beberapa contoh barisan bilangan yang memenuhi kedua syarat terse but 2.0.2.2,0,2.2,0.2.2.0,. .. 2.2.0.2.2.0.2.2.0.2.2.... 2.5.-3.2.5,-3,2,5.-3,2,...
Tetapi di lain pihak pada suatu relasi rekursi linier berkoetisien konstan derajat ke-k. paling banyak hanya dapat ditentukan sejumlah k buah syarat batas. Jadi kembali pada contoh di mana derajat relasi rekursi adalah derajat ke-2, maka tidak dapat ditentukan 3 buah syarat batas yang berurutan. Misalnya akan dicoba diberikan 30 = 2, at = 2 dan ~ = 2, maka ketiga harga tadi sudah tidak memenuhi relasi rekursi yang diberikan yaitu 161
Perlu diingat bahwa relasi rekursi derajat ke-k tidak linier (nonlinier) walaupun mempunyai koefisien onstan, maka walaupun telah diberikan k buah harga aj yang berturutan, maka hal ini tidak menjamin dapat diperolehnya jawab fungsi numerik se~ara unik. Hal ini dapat.ditunjukkan berikut ini di mana dipilih relasi rekursi yang tidak tinier adalah
Walaupun harga ao:: 1 sudah diberikan, tetapi semua barisan bilangan berikut ini memenuhi relasi rekursi maupun harga syarat awal yang diberikan: 1, 2, ..J3, ... I, 2, -..J3, ... I, -2, ..J7, ...
JAWAB HOMOGEN OARI RELASI REKURSI Sekarang kita mulai membahas cara menyelesaikan problema rekursi. Yang dimaksud dengan menyelesaikan problema rekursi adalah mencari bentuk umum suku aj yang dinyatakan dalam suatu fungsi numerik yang mengandung variabel i. Seperti telah diberikan sebelum ini suatu relasi rekursi tinier berkoefisien konstan derajat ke-k dapat ditutis dalam bentuk
Definisi 9.3 BHa harga f(r)
= 0, diperoleh relasi rekursi
yang disebut'relasi rekursi homogen. 162
Definisi 9.4 Jawab (solusi) homogen dari suatu relasi rekursi diperoleh dari relasi rekursi homogen.
adalah jawab yang
Dalam usaha untuk mencari jawab suatu relasi rekursi ,kita perlu mencari dua buah jawab, yaitu I. 2.
Jawab homogen dari relasi rekursi dengan mengambil f(r) = O,dan Jawab khusus yang memenuhi relasi rekursi yang sebenamya.
Di sini jawab keseluruhan dari problema yang sebenamya adalah jumlah dari kedua jawab tersebut di atas. Jadi misalkan telah diperoleh jawab homogen dan jawab khusus berupa barisan bilangan: a(h)
= (ao(h),
a/h) ,
... ) dan
a(k)
= (ao(k),
a\(k)
... )
,
maka jawab keseluruhan dari problema ini adalah a
= a(h) +
a(k)
Hal ini mudah sekali ditunjukkan karena jawab homogen memenuhi
=0 sedangkan jawab khusus memenuhi
=
f(r).
Bila persamaan ini dijumlahkan maka akan diperoleh
dan ini menunjukkan bahwa 163
a
= a(h) +
a(k)
juga memenuhi persamaan rekursi yang diminta.
Catatan Hal yang mungkin pada saat ini dapat menimbulkan pertanyaan adalah keperluan kita untuk meneari jawab homogen relasi rekursi diberikan. Hal ini patut dipertanyakan karena pertama yang seharusnya diem adalah jawab khusus yang memenuhi persamaan yang diminta, sedangkan kedua adalah bahwa jawab homogen tidak akan memenuhi relasi rekursi yang diminta, karena f(r) diberikan harga O.Sebabnya adalah ada banyak jawab yang dapat diperoleh untuk memenuhi relasi rekursi yang diberikan, tetapi hanya ada satu jawab yang juga inemenuhi syarat batas .yang ada. Sedangkan seperti nanti dilihat jawab khusus biasanya tidak memenuhi syarat batas yang diberikan, walaupun memenuhi relasi rekursi yang diberikan. Di lain pihak jaw~b homogen ada banyak, dan dapat diatur sedemikian sehinggajumlah jawab homogen dan jawab khusus seeara keseluruhan akan memenuhi baik relasi rekursi maupun syarat batas yang diberikan. Jawab homogen dari suatu persamaan diferensi linier berkoefisien konstan dapat ditulis dalam bentuk A_f, di mana -I adalah akar karekteristik dan A adalah konstanta yang akan ditentukan kemudian untuk memenuhi syarat batas yan$ diberikan. Dengan m~masukkan bentuk A_r untuk harga ar pada persamaan homogen akan diperoleh
atau dengan menyederhanakan persamaan di atas akan diperoleh
Persamaan yang terakhir ini disebut dengan persamaan karakteristik dari persamaan diferensi yang diberikan. Jadi bila al adalah akar karakteristik dari persamaan ini, maka Aa[ akan memenuhi persamaan homogen. Jadi jawab homogen yang dieari berbentuk Aaf . Tetapi suatu persamaan karakteristik derajat ke-k akan mempunyai k buah akar karakteristik. Misalkan sekarang bahwa semua akar karakteristik tersebut 164
berbeda, maka mudah untuk ditunjukkan bahwa jawab homogen dari relasi rekursi yang diberikan dapat ditulis dalam bentuk
di sini a,1 adalah akar karakteristik dari persamaan karakteristik yang diperoleh, sedangkan Ai adalah konstanta yang nantinya akan ditentukan guna memenuhi . syarat batas yang ditentukan.
Contoh 9.3 Akan diselesaikan relasi rekursi Fibonacci
persamaan karakteristik yang diperoleh adalah a,2
-
a,
- 1 =0
yang mempunyai dua akar karakteristik yang berbeda yaitu a,
= 1 - --15 2
jadi jawab homogen yang diperoleh adalah
di sini konstanta at dan A2 akan ditentukan kemudian untuk memenuhi syarat batas 110= 1 dan at = 1. Semua hal yang telah diterangkan di atas dilakukan berdasarkan suatu teorema yang menghubungkan akar karakteristik suatu persamaan karakteristik dengan suatu relasi rekursi yang linier berkoefisien konstan, seperti yang dinyatakan berikut ini. 165
Sitst 9.4 Misalkan a adalah suatu bilangan riel atau kompleks yang tidak DOl.Maka an = an adalah jawfJb dari relasi rekursi
jika dan hanya jika a adalah akar karakteristik dari polinominal
Bukti an = an adalah jawab d¥i relasi {ekursi tersebutjika dan hanya jika a memenuhi
atau dapat juga ditulis dalam bentuk
Karena diketahui bahwa _ =/, maka persamaan yang terakhir akan sarna dengan
Dengan demikian Cn = an akan memenuhi persarnaan karakteristik yang diminta atau a adalah akar dari polinominal karakteristik. Lebih jauh lagi bila ada dua akar yang berbeda a dan a yang mem~nuhi persarnaan karakteristik ~an relasi rekursi yang diberikan. Bila diketahui pula dua buah konstanta k} dan ~, maka bentuk
166
dari relasi rekursi seperti berikut Coar + Clar_1 +
... +
Ckar_k
=
Co(kl ar+k2W)+C I(k] ar-I+~W-I )+... +Ck(k] ar-k+kl ar~~
=
kl (Coar + Clar-I + ... + Ckar-k) + k2 (CoW + CIW-I + ... + CkW-k =0+0
Persamaan yang terakhirini diperoleh karena masing-masing a dan ~ telah diketahui memenuhi relasi rekursi yang diberikan. Dengan memperluas hasil yang telah diperoleh terakhir ini maka dapat ditunjukkan bahwa bila ai' ~, ..., ~ merupakan k buah akar karakteristik yang berbeda dari persamaan karakteristik
serta dl, ..., dk adalah konstanta sembarang, maka dengan mudah dapat ditunjukkan bahwa bentuk
an
= d]aj
+ d2<X2+
... + dkat akan memenuhi relasi rekursi
jawab yang terakhhir ini dikenal dengan jawab umum dari persamaan rekursi homogen. Jawab umum ini terdiri dari k buah konstanta yang belum ditentukan yaitu dl' ..., dk. Konstanta ini kelak akan ditentukan bila syarat batas dari relasi rekursi telah diberikan.
Contoh 9.4 Akan diearijawab homogenrelasi rekursi berikut
167
rnaka persamaan karakteristik yang bersangkuran dengan relasi rekursi ini adalah X3 - 2X2 - X + 2
=0
dan akar katakteristik dari persamaan ini adalah al
= I, ~ = -I dan~ = 2.
Sehingga jawab urnurn dari relasi rekursi hornogen di atas adalah
Nilai dl, d2 dan d3 akan ditentukan kernudian.
PERSAMAAN KARAKTERISTIK BERAKAR GANDA Sewaktu rnencari akar persamaan karakteristik bersangkutan dengan suatu relasi rekursi , sering kali terjadi bahwa ada akar yang tidak tunggal. Artinya rnungkin ada suatu harga a rnerupakan akar ganda dua, atau tiga atau rnungkin lebih. Sebagai contoh misalnya relasi rekursi yang akan dieari jawabnya adalah
rnaka persamaan karakteristik yang akan diperoleh adalah X2
- 4X + 4 = 0
atau akar yang diperoleh adalah 2 dan 2. Atau dengan perkataan lain angka a = 2 adalah akar ganda dua dari persarnaan karakteristik. Dalam keadaan seperti ini rnaka tidak dapat ditentukan bentuk urnurn dari jawab persarnaan hornogen sebagai
karena hal ini sarna dengan rnengatakan bahwa bentuk urnurn yang diperoleh ternyata ada salah satu akar al yang merupakan akar ganda -rn dari persamaan
karakteristik itu, maka bentuk umum dari jawab persamaan homogen yang harns dicoba adalah
Mengapa demikian? Untuk menjawab pertanyaan ini pandang bentuk Ama,f yang jelas merupakan jawab dari relasi rekursi , karena a,l adalah akar dari persamaan karakteristik
Tetapi temyata bahwa a,l juga merupakanakar dari turunan persamaan karakteristik di atas tersebut, karena a,l adalah akar ganda -m dari persamaan karakteristik tersebut. Jadi a,l juga memenuhi
Bila persamaan terakhir ini dikalikan dengan Am_IX'maka akan diperoleh persamaan berikut ini
bila sekatang dituliskan bn = Am_lnxn, dan bn_l = Am_l(n-l)xn-ldan seterusnya bn_k
= Am_l(n-k)xn-k, maka
dari persamaan terakhir akan diperoleh relasi rekursi
berarti bn = Am_l(n)a,fjuga memenuhi relasi rekursi yang homogen. Dengan cara yang sarna juga dapat ditunjukkan bahwa Am_2n2a,fjuga memenuhi relasi rekursi homogen yang diketahui, karena bilangan a,l 'juga merupakan akar dari turunan kedua dari persamaan yang berhubungan dengan relasi rekursi yang diberikan. Hal ini dapat dilanjutkan terus sampai t?entuk Alnnm-la,ln, di mana m adalah kelipatan dari akar gan~a dati persamaan karakteristik. Dengan demikian bila persamaan karakteristik dari relasi rekursi 169
yang diberikan mempunyai al sebagai akar ganda m maka bentuk berikut merupakan jawab homogen:
dari relasi rekursi homogen berikut ini
Oalam hal ini konstanta AI sampai dengan Am akan ditentukan kemudian oleh syarat batas yang diberikan.
Contoh 9.5 Padacontoh ini diberikan persamaan diferensi atau relasi rekursi berikut
dengan persamaan karakteristik berikut ini ex3+ 6a2 + 12a + 8
=0
Persamaan karakteristik ini mempunyai satu akar ganda tiga yaitu a
atau harga kelipatanakar ganda adalah m homogenadalah
= -2
= 3. Jadi bentuk umum dari jawab
Contoh 9.6 Pada contoh ini relasi rekursi mempunyai satu akar tunggal yang berlainan serta akar lain ganda 2. 4ar - 20ar_1 + 17ar_2- 4
=0
persamaan karakteristiknya adalah
170
4a3
- 20a.2 +
l,7a - 4 = 0
Dari sini diperoleh akar karakteristiknya adalah a, a, dan '4. Berarti 4 adalah akai"tunggal, sedangkan a adalah akar ganda 2. Dari hasil ini diperoleh jawab umum relasi rekursi homogen dapat ditulis sebagai
JAWAB KHUSUS HUBUNGAN REKURSI Menentukan jawab khusus relasi rekursi sulit sekali, karena tidak ada metode yang dapat menentukan jawab khusus relasi rekursi yang nonhomogen, yakni relasi rekursi dengan f(r) tidak sarna dengan DOl.Namun demikian pada dasamya untuk problema yang sederhana, jawab khusus dapat dengan mudah diterka hanya dengan melihat relasi rekursi tersebut. Seperti yang nantinya akan dilihai, untuk
menentukan jawab khusus suatu relasi rekursi dengan f(r) * 0 akan diberikan beberapa model jawab tertentu yang disesuaikan dengan bentuk f(r) itu sendiri. Model yang sering digunakan adalah model Polinomial, serta model eksponen.
Contoh 9.7
Untuk relasi rekursi ini, jawab khusus yang akan dicoba adalah bentuk Polinomial derajat 2, karena f(r) berbentuk Polinomial derajat dua juga. Misalkan jawab khusus yang akan dipilih adalah suatu polinimial derajat dua
Di sini PI' P2 dan P3 akan ditentukan.
171
Bila polinomial ini disubstitusikan ke dalam relasi rekursi yang diketahui, maka akan diperoleh bentuk PJr2 + P2r + P3 + 5PI(r-l)2 :,. 5Plr-l)
+ 5 P3 +
6PI(r-2)2 + 6P2(r-2) + 6P3
.
yang secara sederhana dapat ditulis
karena bentuk terakhir ini harus merupakan suatu polinomial derajat 2 yang besamya adalah 3r2, maka akan diperoleh tiga persamaan berikut ini
=
3
- 12P2 =
0
12PJ 34PI
29PI
- 17P2 +
12P3 = 0
yang akan menghasilkan PI
= 1/4, P2 = 17/24
dan P3 = 115/228.
Jadi bentuk khusus yang memenuhi relasi rekursi nonhomogen adalah ~(k)
= 1/4 r2 +
17/24 r + 115/228
Sifat 9.5 Secara umum dapat dikatakan bahwa bila suatu relasi rekursi mempunyai f(r) yang berbentuk polinimial derajat t
maka jawab khusus yang harus diujikan pada relasi rekursi ini adalah 172
Contoh 9.B BHapada contoh terakhirdi atas di1akukanpel1lbahanfungsi f(r) menjadi f(r)
= 3r - 2r + I, 8, + 58,_1+ 6a,_2= 3r - 2r + I
maka dalam mencoba mencari jawab khusus akan tetap digunakan suatu polinimial derajat dua dalam r yang berbentuk
dan dengan memasukkan ke dalam relasi rekursi yang diketahui maka akan diperoleh suatu persamaan baro yang akan dipenuhi oleh PI' P2 dan PJ seperti berikut ini Plr + P2r +PJ + 5PI(r-l)2 + 5P2(r-l) + 5PJ + 6PI(r-2)2 + 6P2(r-2) + 6PJ p73 yang secara sederhana dapat ditulis sebagai
bentuk terakhirini besarnyasarnadengan3r
- 2r + I. Dan dari kedua bentuk
yang sarna ini akan diperoleh
- 12P2
=3 =2
- 17P2+ 12PJ
= I
12PI 34PI 29PI
173
yang akan menghasilkan PI = 1/4,P2
= 13/24, dan P3 =
71/228.
Jadi bentuk khusus yang memenuhi relasi rekursi nonhomogen adalah
=
ar(k) 1/4 r2 + 13/24 r + 71/228
Contoh selanjutnya akan mengambil f(r) berbentuk eksponen, dan dalam contoh ini pula akan dilihat bagaimana caranya jawab khhusus dapat diterka untuk fungsi eksponen yang demikian.
Contoh 9.9 Pandang relasi rekursi berikut
Akan dicari jawab khusus persamaan diferensi nonhomogen ini dengan mencoba bentuk eksponen P4r. Bila fungsi ini disubstitusikan dalam relasi rekursi yang diketahui, maka akan diperoleh persamaan
atau dapat ditulis lebih sederhana dalam bentuk 21/8 Px4r
= 42x4r
dan ini akan memberikan hasil P relasi rekursi ini adalah a r(k)
174
= 16x4r
= 16. Dengan demikian jawab
khusus dari
Sitat 9.6 Secara umum bila f(r) yang merupakan ruas kanan relasi rekursinonhomogen berbentuk W. maka jawab khususnya akan berbentuk PW. bila 13bukan akar karakteristik dari persamaan karakteristik yang terjadi. Selanjutnya bila f(r) berbentuk
maka jawab khusus yang harus diujikan pada relasi rekursi ini adalah
bila 13 bukan akar karakteristik dari persamaan diferensi yang berbentuk. Untuk lebih jelasnya pandang contoh berikut ini:
Contoh 9.10 Pandang relasi rekursi
maka bentuk khusus yang akan dicoba digunakan adalah
Dengan mensubstitusikan bentuk ini ke dalam relasi rekursi yang diketahui maka akan diperoleh relasi
dengan membandingkan kedua ruas persamaan tersebut akan diperoleh dua persamaan yang masing-masing berhubungan dengan koefis.ienfaktor dari oar dan 2r. yaitu
175
3/2 PI 1/2 PI + 3/2 Pz
= =
3 0
=
dan dari persamaan ini diperoleh PI = 2 dan Pz 2/3. Dengan demikian jawab khusus yang diperoleh untuk relasi rekursi ini adalah
a?>
=(2r
+ 2/3) 2f
Dalam menyelesaikan problema dengan f(r) berbentuk eksponen ini tadi disinggung bahwa P bukan merupakan akar karakteristik dari persamaan karakteristik yang terjadi. pa yang harus dilakukan apabila hal ini terjadi?
Slfat9.7 Dalam hal akar persamaan karakteristik adalah Pyang merupakan akar ganda m-l dan f(r) berbentuk
maka jawab khusus yang akan dieoba untuk dieari akan berbentuk
Hal ini akan terlihat pada eontoh berikut ini:
Contoh 9.11 Pandang persamaan diferensi berikut ini 3r
- ~-l = 3x2f
=
Di sini jelas bahwa 2 adalah akar karakteristik dari P- 2 O. Di samping itu bentuk f(r) juga mengandung faktor 2f. Dengan demikian bentukjawab khusus yang akan dieoba adalah Pr.2f. 176
Dengan memasukkan bentuk ini ke dalam persamaan diferensi yang diberikan maka akan diperoleh persamaan Prx2r
- 2P(r-l )x2r-1 = 3x2r
jadi
atau diperoleh P a r(k)
= 3. Dan jawab khusus yang dieari adalah
=3rx2r
Confoh 9.12 Untukrelasirekursiberikutini ~ - 4~_1 + 4~_2
= (r+l)2r
akar dari persamaan karakteristiknya adalah 2 dan merupakan akar ganda dua. Demikian pula fungsi f(r) mengandung faktor 2r. Jadi jawab khusus yang hams dieoba akan berbentuk
yang bila dimasukkan ke dalam relasi rekursi di atas akan menghasilkan dua persamaan berikut ini
dan
177
yang akan menghasilkan harga PI diperoleh dalam hal ini adalah
= 1/6, dan P2 = 1. Dan jawab
khusus yang
Perhatikan kedua relasi rekursi berikut ini
dan ar
- 4~-1
+ ~-2
=7
Kedua relasi rekursi ini akan menghasilkandua buah persamaan karakteristik. Pada relasi rekursi yang pertama akar karakteristik yang diperoleh adalah tunggal dan nilainya 1. Sedangkan pada relasi rekursi yang kedua akar karakteristik yang diperoleh adalah ganda dua dan nilainyajuga I. Kedua relasi rekursi tersebut mempunyai ruas kanan f(r) 7xlr. Dengan demikian jawab khusus yang harus dicoba untuk relasi rekursi yang pertama adalah
=
~(k)
=Pr
yang bila disubstitusikan p~a relasi rekursi yang pertama akan menghasilkan harga P = 7. Sedangkan untuk relasi rekursi yang kedua harus dicoba fungsi berikut
~ (k)
=Pxr2
yang bila disubstitusikan pada relasi rekursi yang kedua akan menghasilkan harga P = 7/2 Contoh yang berikut akan menggambarkan cara pencarian jawab khusus, dalam hal ruas kanan f(r) mengandung suku polinomial dan juga suku eksponen.
178
Contoh 9.13 Pandang persamaan diferensi yang berbentuk
Untuk meneari jawab khusus problema ini akan dieoba fungsi yang mengandung Polinomial dan eksponen yang berbentuk
Suku pertama berhubungan dengan faktor eksponen 2f, sedangkan dua suku terakhir berhubungan dengan Polinomial derajat Satu yang terdapat pada bagian akhir dari f(r). Perlu diingat bahwa angka 2 di sini merupakan salah satu akar dari persamaan karakteristik yang ada dan juga termasuk dalam bentuk eksponen 2f. Dengan memasukkan bentuk jawab khusus ke dalam persamaan yang diketahui, maka dengan membandingkan semua suku yang sarna akan mudah dapat diperoleh jawab. P3
= 7/4
dan dengan demikian jawab khusus yang dieari adalah irk)
= _rx2f+l
+ 1/2 r + 7/4
JAWAB KESELURUHAN RELASI REKURSI Pada dua sub bab yang terdahulu telah dipelajari bagaimana cara meneari jawab persamaan homogen yang masih tergantung dari beberapa konstanta tertentu yang tergantung pada derajat relasi rekursi, dan juga jawab khusus dari persamaan nonhomogen yang telah tertentu, dan tidak tergantung pada konstanta lain. Untuk meneari jawab keseluruhan dari relasi rekursi yang diketahui, maka kedua jawab tadi harus digabungkan menjadi satu dan untuk itu diperlukan sejumlah syarat batas yang dapat digunakan untuk menemukan konstanta yang ada pada jawab umum. 179
Sitat 9.8 Misalkan relasi rekursi yang diberikan merupakan relasi rek Jrsi derajat t, dan akar persamaan fcarakteristik semuanya mempunyai sejumlah t buah harga yang saling berbeda. Maka jawab keseluruhan dari relasi rekursi tersebut dapat dituliskan sebagai
di sini p(r) adalah jawab khusus dari persamaan nonhomogen. Untuk menentukan t buah konstanta AI' ,At, perlu diberi t buah syarat batas yang dituliskan dalam harga '\0, aro+l" ..., ~t-I' Dan dengan memasukkan jawab keseluruhan tadi ke dalam t buah harga batas tadi, akandiperoleh sejumlah t buahharga batas tadi akan diperoleh sejumlah t buah persamaan yaitu
t buah persamaan linier ini dapat diselesaikan untuk t buah harga AI,
Contoh 9.14 Untuk relasi rekursi berikut ini
jawab keseluruhannya akan berbentuk
180
,At.
Bila selanjutnya diberikan dua buah syarat batas yang berbentuk 962, maka persamaan linier yang akan diperoleh adalah
dan ~
=
278
~
=278
=4At
+ 9A2 + 256 962 = -SAt - 27~ + 1024
dan dari kedua persamaan ini diperoleh At keseluruhan problema adalah ar
=(_2)r + 2(-3)r
= 1 dan ~ = 2. Jadi jawab
+ 16x4r
Catatan Yang menjadi pertanyaan utama adalah bagaimana kita dapat tabu bahwa sistem persamaaan tinier yang terjadi akan memberikan jawab yang unik. Bagaimana kalau temyata sistem persamaan tadi tidak mempunyai sarna sekali atau mungkin mempunyai.sejumlah tak hingga jawab. Hal ini dapat dibuktikan tidak mungkin terjadi. Buku ini dapat melakukan pembahasan akan hal ini dengan terlalu detail, tetapi dasar pemikirannya adalah matriks Vandermonde untuk persamman karakteristik dengan akar yang berbeda. Dalam teoti matriks telah dapat dibuktikan bahwa suatu sistem persamaan tinier dengan matriks Vandermonde pasti akan mempunyai jawab yang unik, karena matriks Vandermonde selalu non-singulir. Hal yang sarna juga dapat ditunjukan untuk relasi rekursi yang mempunyai persamaan karakteristik dengan sejumlah akar ganda.
CARA ITERASI DAN INDUKSI Kita telah mempelajari cara menyelesaikan relasi rekursi tinier berkoefisien konstan. Di situ keberhasialan cara penyelesaian sangat tergantung pada kemampuan mencari akar karakteristik dari persamaan karakteristik yang ada. Dalam beberapa hal akar-karakteristik tersebut sangat sutit untuk dieari. Bila akar karakteristik tersebut sudah berhasil ditemukan, maka biasanya masih harus diselesaikan suatu persamaan tinier yang diperoleh guna memenuhi syarat batas yang ditentukan yang banyaknya sarna dengan derajat relasi rekursi yang ada. 181
Bila relasi rekursi yang ada ada:tahderajat ke-k, maka ada k persamaan linier yang harus diselesaikan. Berikut ini akan diberikan beberapa contoh cara penyelesaian relasi rekursi tinier dengan menggunakan cara iterasi dan induksi. Hal ang dilakukan di sini adalah dengan pertama-tama melakukan terkaan awal fungsi an yang memenuhi relasi rekursi. Lalu dengan langkah induksi atau iterasi dicoba untuk membuktikan bahwa terkaan tersebut benar-benar memenuhi relasi rekursi yang diminta.
Contoh 9.15 Akan diselesaikanbentuk rekursi berikut .an
= a (1-1+
n3
dengan syarat batas 30 = o.
Dalam usaha untuk mencoba menyelesaikan relasi rekursi ini pertama-tama dilihat bentu~ iterasi yang dihasilkan seperti berikut an = a n-1+ n3 karena relasi di atas juga berlaku untuk setiap harga n, maka untuk harga n yang lain yaitu n-l, n-2 dan seterusnya relasi tersebut dapat ditulis sebagai berikut
dan dengan menggunakan syarat batas yang telah ditentukan bahwa 30
persamaanyang terakhirini dapat dituliskansebagai 182
=0, maka
= 0 + 13+ 23 + 33 + ... + (n-2)3+ (n-l)3 + n3 = 13 + 23 + 33 + ... + (n-2)3 + (n-l)3 + n3 Jadi untuk harga n~l, akan dapat diperoleh bahwa ~ adalah jumlah n suku pertama dari n pangkat 3. Persoalannyasekarangapakah dapat diperoleh bentuk yang lebih sederhana dari terkaan jawab di atas. Kalau sekarang mulai dari indeks 0, 1, dan seterusnya ditulis <10=0 at =
°+
13
= at + 23 a3
=
=
1
=
1+8=9
+ 33 =
a4 = a3 + 43 as = a4 + 53
=
9 + 27 = 36 36 + 64 = 100
= 100 + 125 = 225
maka dengan memperhatikan pola yang terjadi pada sederetan angka di atas
dapat diterka bahwahasil yang diperolehdituli$sebagai =
12
=
( 1 )2
=
32
=
( 1 + 2 )2
a3 = = a4 = as
62
=
(1+2+3)2
at
102 =
( 1 + 2 + 3 + 4 )2
152 =
(I
+2+3+4+5)2
dan bentuk jumlahan dalam kurung di atas dapat ditulis sebagai I + 2 + 3 + ... + n = n(n+1)/2 maka diperoleh terkaan jawab yang berbentuk
an =
183
Sekarang masih harus ditunjukkan secara inldusi bahwa terkaan rumus di atas benar memenuhi relasi rekursi yang diberikan. Dari percobaan beberapa harga tadi telah diketahui kebenaran dari rumus tadi untuk harga awal n 0, I, 2,3,4 dan 5. Misalkan sekarang rumus tersebut benar untuk harga n+1. Dengan menggunakan relasi rekursi yang diberikan maka dengan mudah dapat dilihat bahwa
=
~+1
= an +
_
n2(n+l)2 4
-
(n+l)3
+ (n+l)3
n2(n+I)2 + 4(n+l)3 4
= =
(n+l)2(n2+4n+4) 4 (n+l)2(n+2)2 4
dan rumus terakhir ini sarna dengan rumus untuk ~ dengan harga n diganti oleh n+ 1. Jadi dengan langkah induksi ini terkaan jawab
~=
dapat Jikatakan sebagai jawab yang sebenarnya
dari relasi rekursi yang diberikan.
Confoh 9.16 (Tower of Hanoi) Contoh ini dikenal dengan nama Tower of Hanoi yang isinya sebagai berikut. Ada papan dengan paku.tertancap pada papan tersebut. Pada salah satu paku ada setumpuk n buah piringan yang tersusun dari piringan yang terbesar di bawah dan kemudian makin ke atas makain mengecil. Yang harns dilakukan adalah memindahkan tumpukan n buah piringan te..sebut dari paku yang satu ke paku yang lain dengan syarat sebagai berikut: 184
I. 2.
Setiap l&I1gkahhanya boleh diambil dan dipindahkan 1 piringan saja. Tidak boleh ada piringan yang keeil berada di bawah piringan yang besar.
Yang ditanyakan adalah jumlah langkah pemindahan piril1ganyang harns dilakukan dari satu paku ke. paku yang lain. Untuk menjawab problema ini dimisalkan bahwa ~ adalah jumlah langkah yang diperlukan untuk memindahkan n buah piringan tersebut dari paku yang satu ke paku yang lain, dengan n =0,1,2,... . Makauntukmeneobamenyelesaikan problema tersebut untuk 0 buah piringan jelas <10 =O.Sedangkan untuk 1 piringan makaa, = I dan untuk 2 piringan ~ = 3. Sekarang harns dieari relasi rekursi yang dipenuhi oleh proses tersebut. Kita tahu bahwa untuk dapat memindahkan n buah piringan dari paku satu ke paku yang lain maka harns dilakukan hal berikut ini: 1. Pertama-tama hams dipindahkan n 1 piringan ke paku yang ke-2. 2.
Lalu piringan yang paling besar yang masih ada di paku yang ke-l tadi, dipindahkan ke paku yang ke-3
3.
Terakhir hams dipindahkan.n-I piringan yang ada di paku ke-2 ke paku yang ke-3.
Jelas bahwa pada ketiga langkah ini langkah pertama dan ketiga menyalahi ketentuan pertama yang diberikan di atas, yaitu hanya boleh memindahkan hanya 1 piringan pada setiap pemindahan. Sedangkan langkah yang kedua tidak menyalahi ketentuan yang diberikan. Tapi kalau dilihat lebih teliti maka langk~ pertama dan ketiga di atas merupakan langkah untuk menjawab problema p73 Tower of Hanoi ini dengan menggunakan n-l piringan saja. Dengan demikian maka diperoleh relasi rekursi berikut ini yaitu:
untuk harga n
= 1, 2, 3, dan seterusnya.
Suku pertama pada rumus di atas merupakan langkah pertama yaitu memindahkan n-l piringan daTi paku ke paku kedua, suku kedua merupakan langkah ke dua dan suku ketiga merupakan langkah ketiga.
185
Re1a.sirekursi ini adalah linier berkoefisien konstan dan akan diselesaikan dengan ca~a iterasi dan induksi. Caranya adalah dengan mencoba sekali lagi menerka bentuk jawab yang memenuhi relasi di atas sepeti berikut ini an
karena
=
2an_1+ 1
=
2 [2an_2+ l] + I
= =
22 [2a~3 + I] + 2 + I
= =
2n-1[2ao + I] + 2n-2+ ... + 22 + 2 + 1
= 22an_2+ 2
= 23a~3
+I + 22 + 2 + I
2n-1+ ... + 22 + 2 +1
= O. Dengan demikian diperoleh terkaan rumus sebagai jawab
<10
dari
problema Tower of Hanoi ini sebagai berikut
an = 2n-1+ 2n-2+ ... + 22 + 2 + 1 dan dengan menggunakan rumus jumlahan untuk deret ukur dapat diperoleh jawab 2n -1
= 2n -
1
2- I yang berlaku untuk semua harga n
= 0,
1, 2, ...
Langkah yang selanjutnya harus dilakukan adalah dengan membuktikan secara induksi matematik bahwa rumus di atas benar-benar berlaku untuk setiap n.
Untuk dasar induksi, jelas bahwa <10= 0, jadi memenuhi syarat batas yang ditentukan. Misalkan sekarang rumus di atas benar untuk harga n, yaitu an
= 2n - I
Dengan menggunakan relasi rekursi yang diberikan yaitu 88t
= 2~
an+l
+ 1
diperoleh bahwa an+l
= 2(2n-l)
+ 1
atau dengan perkataan lain
= 2n+2 - 1
~+l
jadi rumus ini benar untuk harga n+1, dan berdasarkan induksi matematik ini dapat dikatakan bahwa jawab dari relasi rekursi dari problema Tower of Hanoi adalah an
= 2n - I
Contoh 9.17 Contoh ini berhubungan dengan cara mengalikan n buah bilangan yaitu xl' x2' ..., xn. Akan ditentukan berapa banyak cara perkalian dapat dilakukan untuk melakukan hal tersebut. Misalkan ~ adalah banyaknya cara mengalikan n buah bilangan tersebut di atas. Pertama-tama akan dilihat dulu banyaknya cara mengalikah sejurnlah kecil bilangan-bilangan. Misalnya untuk n 2, maka dapat dilakukan ,dua macam perkalian yaitu
=
Jadi ~
= 2, sedangkan al jelas
Untuk n yaitu
sarna dengan 1.
= 3 maka dapat dilakukan sebanyak 12 macarn perkalian bilangan
Xl x ( x2 X x3 ),
( Xl X ~ ) x X3
XI X ( x3 X x2 ),
( Xl X X3 ) X X2
x2 X ( x3 X Xl ),
( X2 X X3 ) X Xl
'187
X2 x ( XI X X3 ),
( X2 X XI ) X X3
X3 X ( XI X X2 ),
( X3 X XI ) X X2
X3 X ( X2 X XI ),
( X3 X X2 ) X X I
Ternyata dalam usaha menghitung ~ dapat dilakukan hal berikut ini. Dari tiga bilangan yang akan dikalikan, ambil dua bilangan dari tiga bilangan Xl' ~, dan x3' kemudian kalikan ,dua bilangan tersebut. Hal ini dapat dilakukan dalam 3 pilihan . Untuk setiap pasangan bilangandapat dilakukan perkalian sebanyak ~ = 2 kali. Sisanya dapat diperoleh dengan mengalikan di kiri atau kanan dari pasangan yang dipilih. Hal ini dapat dilihat dalam cara perkalian berikut ini XI X ( x2 X x3 )
X2 X (xI
X xj)
X3 X (xI
X x2)
XI X ( x3 X x2 )
x2 X (x3
X xI)
x3 X (~
X xI)
( x2 X x3 ) X XI
(xI
( x3 X x2 ) X XI
(x3 X xI) X x2)
X x3) X x2
jadi relasi yang diperoleh adalah a3
( xi
X x2) X x3
( x2 X xI) X x3
= (3x2)~ = 12
Hal ini diperluas sehingga dapat berlaku untuk sembarang perkalian n bilangan. Perkalian ini n bilangan xl' ",xn' dapat dilakukan sebagai n-l perkalian dari 2 bilangan. Pandang salah satu bentuk perkalian n-l bilangan xl' ..., xn_1 yang banyaknya ada an_I'Untuk dapat mengalikan hasil kali ini dengan bilangan
xn' dapat dilakukancara berikutini:
'
1. Kalikan xndi setiap ruas setiap faktor dari n-2 perkalian yang dlgunakan pada perkalian xi' ... xn_l. 2. Kalikan xndi muka hasil perkalian XI' ..., xn_l. 3. Kalikan xndi belakang hasil kali perkalian XI' ..., xn_J. Untuk memudahkan hal ini gunak~ contoh untuk n = 6, dan ambil salah satu hasil perkalian dari 5 bilangan xI' ""xs sebagai berikut:
188
Maka akan ada 5 - 1 = 5 perkalian dalam hasil ini. Ambil salah satu dari perkalian ini, misalkan (x3 x x4) x xs' yang merupakan hasil kali dari (x3 x x4) dan xs' Maka x6 dapat dimasukkan ke dalam perkalian ini dalam 4 eara yaitu [X6 x (x3 X x4)] X Xs
(X3 x x4) x (x6 x xs)
[(x3 x x4) x x6] x Xs
(x3 x x4) x (xs x x6)
maka hasilkali xI' ..., x6 untuk perkalian ini adalah (XI X x2)x([x6 X (x3 X x4)]x xs)
(xI X x2)x[(x3 X x4)x(x6 x. xs)]
(xI X x2)x([x3 X x4) X x6]x xs)
(xI X x2)x[(x3 X x4)x(xs X x6)]
di samping jawab tersebut masih ada lagi jawab lain yaitu dengan mengalikan x6 di depan dan di belakang hasil kali yang telah terjadi yaitu x6 X «xI X x2) x [(x3 x x4) X xs]) dan
Dari analisis ini dapat disimpulkan bahwa akan ada 4(n-2) + 1 + 1 eara atau 4n - 6 eara untuk menghubungkan xn dengan hasil kali yang telah ,diperoleh untuk xl' ..., xn_l.Jadi relasi rekursi yang dipenuhi adalah an
= (4n - 6)
an_I
dengan syarat awal yaitu al
= I. Untuk menearijawab dari ~
iterasi berikut ini yaitu: an
=
=
=
(4n - 6)(4(n-1)-6)an_2= (4n-6)(4n-lO) an_2 (4n-6)(4n-IO)(4n-14) an_3
=
(4n-6)(4n-IO)(4n-14) ...x6x2al (4n-6)(4n-IO)(4n-14) ...x6x2
= =
ini maka digunakan .
(4n - 6) a~I
189
beotuk terakhir ioi dapat dituliskan sebagai
= = =
ao
2(20-3)2(20-5)2(20-7)...2(3)2(1) 20-'(20-3)(20-5)(20-7)...(3)(1) 2°-'(1x3x5...(20-7)(20-5)(20-3» 2°-'(20-2)!
=
(2x4x6...(20-6)(20-4)(20-2»
=
2°-'(20-2)! 20-'(1x2x3...(0-3)(0-2)(0-l)
=
(20-2)!
= (0-1)!
(0-1)!
20-2
(n-I )
Jadi jawab yang diperoleh untuk cootoh ini adalah ao
= (n-I)!
uotuk harga 0
2n-2 n-I
( ) = 1, 2, 3, ...
Perlu diperhatikan di sini bahwa bila pada waktu pembentukan perkalian tersebut urutan bilangan xI' ..., Xodipertahankan, makajawab yang telah diperoleh harus dibagi dengan n!. sehingga diperoleh
dalam hal seperti ini perkalian x,x(x2xx3) diperbolehkan sedangkao perkalian x2x(x,xx3) tidak diperbolehkan. Dan relasi rekursi yang diperoleh dalam hal ini adalah
bo = 190
4n-6 n
untuk harga n=2,3, dan seterosnya. dan jawab dari relasi rekursi ini adalah
bn
= ~n
(2n-2 n-l )
Barisan bilangan bn ini dikenal dengan nama bilangan Catatan. Barisan bilangan ini sering timbul dalam berbagai problema kombinatorik. Perlu diperhatikan di sini bahwa relasi rekursi yang dipenuhi pada kedua hal ~ dan bn adalah relasi rekursi linear berkoefisien tidak konstan, karena koefisiennya tergantung dari n.
TABEL DIFERENSI Tabel diferensi yang akan dibicarakan ini biasanya dipclajari dalam mata kuliah Metode Numerik. Diberikan suatu problema numerik, yang mungkin diperoleh setelah melalui suatu eksperimen, maka tabel diferensi dapat digunakan untuk mencocokkan suatu fungsi Polinomial pada data yang diperoleh. Yang akan dipelajari pada bagian ini adalah kegunaan tabel diferensi untuk menyatakan suatu bentuk xk, dengan k adalah bilangan bulat positif, yang meropakan suatu perluasan dari bentuk koefisien binomial. Cara penulisan yang demikian ini dapat digunakan untuk melakukan perhitungan jun:liah pangkat k dari n buah bilangan asli yang pertama. Pandang suatu fungsi p yang didefinisikan pada himpunan bilangan riil x. Perhatikan contoh berikut yang menggunakan suatu Polinomial yang didefinisikan sebagai p(x) = 2x2 + 3x + 1. Akan dihitung harga p(x) untufc x = 0,1,2, dan -seterosnya. Bila harga ini ditulis dalam baris ke 0 berikut maka akan diperoleh 0: 1 6 15 28 45 66 91 ... pada baris berikutnya, yaitu baris 1, tuliskan diferensi dari suku-suku yang berturotan pada baris O.Kemudian definisikan suatu fungsi bam yaitu £\psebagai berikut 191
6p(X)
= p(x+ 1) - p(x)
Maka diferensi yang diperoleh adalah harga 6p(X)untuk x = 0,1,2,... dan seterusnya. Beda ini disebut dengan bed derajat pertama dari p. Maka baris 0 dan 1 dapat ditulis sebagai 0: 1:
1
6 5
15 9
28 13
45 66 91 17 "21 25
Pada baris kedua dituliskan diferensi dari suku yang berturutan pada baris 1. Beda ini adalah diferensi, yang diperoleh dari fungsi 6p(X), atau dituliskan dengan 62p(X)untuk harga x ==0,1, Jadi 6'lp(x) didefinisikan sebagai 62p(X)
= 6p(x+l) - 6p(X)
=
6(6p)(X)
=
p(x+2) - p(x+2) - [p(x+l) - p(x)]
=
p(x+2)
-
2p(x+l) + p(x)
Dari hasil perhitungan ini dapat diperoleh baris kedua yang berisi 0: 1: 2 :
1
6 5
15 9
4
4
28 13 4
45 17 4
66
91...
21 25,.... 4... .
Proses ini dapat terus dilanjutkan sehingga dari suatu baris yang telah ada akan diperoleh baris berikutnya yang merupakan diferensi dari bilangan baris sebelumnya. Hasil dari barisan bilangan ini disebut tabel diferensi untuk fungsi p. Untuk suatu harga k ~ 2, didefinisikan kp seeara induksi seb~gai berikut
Nilai-harga 6kp(X)untuk x = 0,1,2, Ini disebut diferensi derajat ke k dari p(x). Bilangan-bilangan ini merup,*an bilangan yang muneul pada baris ke k pada tabel diferensi. Untuk menyederhanakan problema maka didefinisikan pula besaran
192
.
dan baris ke x untuk x = 0,1,2,... dan seterusnya disebut dengan diferensi derajai o dari p. Bila dalam proses perhitungan baris ke k diperoleh bahwa seluruh harga baris ke-k tersebut adalah 0 maka baris-baris selanjutnya pasti akan berisi angka o saja. Jadi proses ini tidak perlu dilanjutkan lagi. Seperti pada contoh yang sedang dibicarakan ini maka baris ke k yang diperoleh adalah
o
:
1 : 2 : 3 :
1
6
15
28 45 66 91 ... 5 9 13 17 21 25 ... 4 4 4 4 4 ... 0 0 0 0, ...
=
Di sini terlihat karena p(x) adalah Polinomial derajat 2, p(x) 2x2 + 3x + 1, makadiferensi derajat ke-3 dari p(x) akan mempunyai baris yang terdiri dari bilangan 0 semua. Hal ini temyata berlaku 'umum untuk setiap derajat Polinomial yang dinyatakan dalarn teorema berikut yang didahului dengan 2 buah ketentuan yang tidak akan dibuktikandi sini, karena me~yangkutproblema dasar matematika.
KETENTUAN I Bila p(x) suatu Polinomial yang mempunyai harga 0 untuk sejumlah tak berhingga harga x, maka p(x) adalah sarna dengan O.
KETENTUAN
/I
Bila p(x) dan g(x) Polinomial dengan derajat paling tinggi n, serta p(x) dan g(x) mempunyai paling sedikit n+1 harga yang sarna pada n+1 titik yang sarna, maka p(x) = g(x) untuk setiap harga x.
193
Teorema 9.1 Misalkan p(x) suatu Polinomial derajat n yang OOrbentuk
maka diferensi derajat ke-(n+l) dari p(x) akan mempunyai harga 0 semua.
Bukti Hal ini akan dibuktikan dengan menggunakan induksi matematik pada n. Bila n =0 maka p(x) =30 =konstan, dengan demikian.diferensi derajat ke-l dari p(x) jelas akan mempunyai harga nol semua. Misalkan sekarang n adalah suatu harga yang:S;1,dan misalkanbahwa teorema di atas OOnaruntuk semua Polinomial dengan derajat k ~ n. Artinya untuk suatu Polinomial derajat ke-k yang kurang dari n maka baris ke-(k+l) dari diferensi derajat ke-(k+l) dari p(x) semua OOrnilai nol. Perlu /Jiperhatikan di sin bahwa jika telah diOOrikansuatu taOOldiferensi untuk suatu PoHnomial p(x), maka bila baris ke-Oatau baris pertam a dari tabel diferensi tersebut dihapus, maka akan diperoleh tabel diferensi bam untuk .
Polinomialp(x).Jadi bariske n+l dari taOOl~iferensiuntukfungsil1p(x)adalah sarna dengan baris ke-n daP tabel diferensiuntuk fungsi l1p(x).Sekarang perhatikan OOntuk l1p(x)
=
p(x+1) - p(x)
=
[an(x+1)n+ ~_l(x+l)n-l + ...a1(x+1) + 30]
- anxn+ an_1xn-1 + ... + a1x +' 30 dengan menggunakan teorema binomial maka dapat diperoleh ~(x+l)n
194
- anxn = an
Dari OOntukini dan dengan memperhatikan OOQtukterakhir dariAp(X) yang diberikan di atas, maka dapat disimpulkan bahwa Ap(X)adalah suatu Polinomial derajat paling tinggi (n-l). Jadi dengan pemisalan induksi yang telah dimisalkan di atas maka dapat disimpulkan bahwa baris n dari tabel diferensi dari AP(X) merupakan baris yang terdiri dari bilangan yang semuanya nol. Dengan demikiait baris ke n+1 dari taOOldiferensi Ap(X)terdiri dari nol semua. Dan teorema terbukti menurut induksi matematik yang digunakan. Perhatikan bahwa bila diketahui dua buah fungsi Polinomial p(x) dan q(x), dan diOOntuksuatu fungsi bam f(x) = p(x) +q(x), maka karena f(x+l)
- f(x) = =
[p(x+l) + q(x+l)] - [p(x) + q(x)] [p(x+l)- p(x)] + [q(x+l) - q(x)]
dapat disimpulkan bahwa taOOldiferensi dari f(x) dapat diperoleh dengan menjumlal}kanelemen yang bersesuaian pada taOOldiferensi dari p(x) dan q(x). Dengan perkataan lain dapat dikatakan bahwa taOOldiferensi dari f(x) adalah sama dengan jumlah dari taOOldiferensi p(x) dan q(x). Lebih dari itu; bila c dan d adalah dua buah konstanta, maka taOOldiferensi dari g(x) yang didefmisikan sebagai g(x) =c p(x) + d q(x), dapat diperoleh dengan mengalikan elemen':'elemen dari tabel p dan q dengan c dan d, dan kemudian menjumlahkan setiap elemen
yang OOrsesuaian.
.
Hal ini diperlihatkan pada contoh OOrikut.
Contoh 9.18 DiOOrikan p(x)
= x2 + x +
q(x)
= x2 - x - 2
1
dan
TaOOldiferensi dari p(x) adalah 195
1
3
7
13
21
2 4 6 8 ... 2 2 2 ...
o 0 ... sedangkantabel diferensiunutk q(x) adalah -2
-2
o
0 4
2 4 222....
10
...
6 ...
o 0... Bila didefinisikan.fungsi f(x) f(x)
=2 ( x2 + x + 1 ) + 3 ( x2 -
X- 2 )
=5x2 - X -4,
maka dengan mengalikan 2 elemen tabel diferensi p(x) dan mengalikan 3 elemen tabel diferensi q(x), kemudian menjumlahkan elemen yang bersesuaian dari hasil kali tadi, akan diperoleh tabel diferensi dari f(x) yang berbentuk -4
0
14 38 72 4 14 24 34... 10 10 10...
o
0...
Sudah barang tentu hasil ini dapat diperluas lagi untuk jumlahan dari sejumlah hingga Polinomial yang mempunyai derajat yang sarna. Hal lain yang patut diperhatikan di sini adalah bahwa ins dati tabel diferensi dari suatu fungsi f(x) ~itentukan oleh bilangan-bilangan yang berada di sisi kiri dari tabel diferensi tersebut. Dengan perkataan lain seluruh isi dari taOOldiferensi tadi ditentukan secara lengkap oleh harga f(O),M(x), ~2f«(», ... . Jadi misalkan diOOrikansebagian dari suatu tabel diferensi yang OOrisi
196
._~-
--
2
a -1
c
b r
3
v w
0 0
...
t
s u
d
-
...
...
maka dengan mudah dapat tiiperoleh bahwa a-2 = -1. atau a;: 1. Kemudian karena r-(-1) = 3. maka r = 2. Demikian pula u = 3 dan seterusnya.Dengan cara ini dapat
ditentukan semua harga dari a, r. u. w. yang merupakan harga dari f(l).
~f(1). ~2f(1). ~3f(I). dan seterusnya. Dengan cara yang sarna dapat ditentukan harga-harga dari b. s. v. ... yang merupakan harga dari f(2). M(2). ~2f(2). ~3f(2) dan seterusnya. Jadi seluruh isi dari tabel diferensi ditentukan oleh harga sisi sebelah kiri. Sekarang misal diberikan suatu Polinomial p(x) derajat n. dan sisi kiri dari
tabel diferensi dari p(x) adalah bilangan co' cl' ...cn. O. O. ...0. Untuk setiap nolai i = O. 1. 2. misalkan bahwa Pi(x~adalah suatu Polinomial sehingga sisi kiri dari tabel bedanya adalah O. O.
O. 1. O. O. ...0.
Jadi semua elemen p8da sisi
kiri tabel bedanya bemilai O. kecuali pada baris ke i bemilai 1. Jadi sisi kiri dari tabel diferensi untuk
akan bemilai co' cl' cn. O.O. O.Dengan demikian sisi kiri dari fungsi p(x) akan sarna dengan sisi kiri dari fungsi
Karena sisi kiri dari suatu tabel diferensi menentukan seluruh isi tabel diferensi. maka dapat disimpulkan bahwa p(x) dan
mempunyai tabel diferensi yang sarna, dan dengan demikian untuk setiap x.
197
Carn penulisan. yang terakhir ini rnenentukan bagairnana suatu Polinornial p(x) dapat dituliskan ke dalarn jumlah dari Polinornial po(x), p\(x), ... oleh Polinornial Pj(x)tersebut. Yang akan dijadikan sekarang adalah perhitungan P3(x), sedangkan untuk Pj(x) lainnya dapat ditentukan dengan cara yang sarna. Karena sisi kiri dari P3(x)rnernpunyai harga 0, 0, 0, 1,0,,0, ..., maka tabel diferensi dari P3(x) dapat dilengkapi dan diperoleh sebagai berikut ini
°
° °
1 4 10 20
° °
1 3 1
° 1
10
6
2 3 4 1 1 1
° °
° ° °
° ...
Perhatikan di sini bahwa kecuali untuk beberapa harga 0, maka 4 baris ertarna dari tabel diferensi ini sarna dengan 4 kolorn pertama dari suatu segitiga pascal. Dari tabel diferensi ini dapat dilihat bahwa tingkaty dari P3(x), adalah 3 dan harga plO)
= plI) = pl2)
= 0, dan pl3) = 1.
Tetapi hila diperhatikan rnaka Polinornial berikut
q3(X)
=
x(x-l)(x-2) 3!
=
(; )
Maka harga q3(x) di antaranya Q3(0)
=Q3(1)=.Q3(2)= ° danQl3) = 1.Dari
harga ini juga dapat dilihat dengan rnudah bahwa sisi kiri dari tabel diferensi dari Q3(x),juga rnernpunyai harga 0, 0, 0, 1, 0, 0, Karena Qlx) juga rnerupakan Polinomial derajat 3 rnaka dengan demikian dapat disirnpulkan bahwa
(; ) Secara umum dapat diperoleh bentuk Pj(x) adalah
198
=
po()
()
=1
-x
Pt(x) =
(;) = P2(x)
=
(;)
l!
=.
2! (X(X-I))
X(X-I) ... (x-k+ I)
=
k! Dan dengan demikian diperoleh p(x)
= Co
dengan p(x) adaIah suatu Polinomial derajat n dengan sisi kiri dari tabel bedanya bemilai Co' Ct, ..., Cn, 0, 0, ...
Contoh 9.19 Pandang Polinomial berikut ini p(x)
= x3 +
2x2
- 3x + 2
maka tabel bedanya adalah 2
2 o
12
38
86
10 26 48 10 16 22 6 6... o 199
Dengan .memperhatikan bagian kiri dari tabel diferensi ini, maka dapat disimpulkan bahwa
Telah diketahui koefisien binomial memenuhi rumus penjumlahan berikut ini, untuk setiap bilangan tidak negatif m dan k m+l k+l
(~) + (~) + ... + (~) = (
)
atau dalam bentuk Pj(x) dapat ditulis persamaan
Dengan menggul)akan rumus terakhir ini dapat dicari jumlahan berikut m p(Q) + p(1) + p(2) + ... + p(m)
= L
t=O
p(t)
Untuk sembarang Polinomial p(x). Untuk suatu Polinomial derajat n, pertama-tama akan dicari konstanta Co' ...,Cn, yang memenuhi
Maka jumlahan m
m
L
P(t) = L
t=O
200
t=O
CoPo(t)+ ...
+ CnPn(t)
Jadi diperoleh rumus untuk p(x) suatu Polinomial n dengan tabel bedanya mempunyai sisi kiri CO' ..., Cn, 0, 0, 0... maka m+1
( n+l ) Contoh 9.20 Hitung jumlah dari 14 + 24 + ... + m4, di sini m adalah bilangan positif. Dalam hal ini p(x) = x4, dan tabel beda dari p(x) adalah o
1
16 15
14
81 65
50
256 625 175 369
110
36
60 24
194 84
24
o Dengan demikian p(x) dapat ditulis sebagai
Jadi jumlahan yang dicari adalah m
14 + 24 + ... + m4
=L t=O
p(t) 201
Dengan cara yang sarna dapat juga dihitung 1n + 2n + ... + mn, untuk setiap bilangan bulat positif m dan n. Dalarn menyelesaikan hal ini maka pertama-tarna harus ditentukan nilai dari c(n,t), untuk n = 1, 2, ... dan t = 0, 1, 2, ..., sedemikian
sehingga n
L c(n,t)
X
() t
t=O
Mudah untuk dilihat bahwa untuk setiap bilangan bulat positif n, nilai c(n,O) = O. Bila didefinisikan suatu bilangan baru S(n,t) sehingga
S(n,t)
=
c(n,t) t!
Untuk n, dan t seperti yang tersebut di atas, maka bilangan S(n,t) yang baru didefinisikan ini dikenal dengan barisan bilangan Stirling jenis ke dua. Dengan besaran ini maka persamaan xn dapat ditulis kembali dalarn bentuk n xn
= Lt=O S(n,t)[x]t
di sini [x]t = x(x-I)(x-2) ... (x-t+I) dan [x]o = 1. Bilangan Stirling jenis ke dua ini sering muncul dalam banyak persoalan kombinatorik dan mempunyai banyak sifat kombinatorik yang menarik. Bilangan ini juga memenuhi hubungan rekursi berikut : S(n,t)
= tS(n-I,t)
+ S(n-l,t-l)
1 ~ t ~ n-I
yang pada dasarnya mirip dengan rumus Pascalpada koefisien binomial. Karena bentuk di atas adalah hubungan rekursi tingkat 2, maka dengan hubungan rekursi ini dan dua .syarat batas S(n,O)
= 1 dan
S(n,n)
= 1, yang
semua bilangan Stirling jenis kedua ini dapat dihitung. 202
berlaku untuk setiap n,
