Lewati ke konten utama

Latihan 9.9 Latihan

1.

Tuliskan setiap persamaan rekurensi berikut sebagai persamaan operator pemajuan.
  1. \(\displaystyle r_{n+2} = r_{n+1}+2r_n\)
  2. \(\displaystyle r_{n+4}=3r_{n+3} - r_{n+2}+2r_n\)
  3. \(\displaystyle g_{n+3} = 5 g_{n+1} - g_n + 3^n\)
  4. \(\displaystyle h_n = h_{n-1} - 2h_{n-2} + h_{n-3}\)
  5. \(\displaystyle r_n = 4r_{n-1} + r_{n-3} - 3 r_{n-5} + (-1)^n\)
  6. \(\displaystyle b_n = b_{n-1} + 3b_{n-2} + 2^{n+1} - n^2\)

2.

Selesaikan persamaan rekurensi \(r_{n+2} = r_{n+1} + 2r_n\) jika \(r_0=1\) dan \(r_2=3\) (Ya, kita menetapkan nilai \(r_2\text{,}\) tetapi tidak menetapkan nilai \(r_1\)).

3.

Tentukan solusi umum persamaan rekurensi \(g_{n+2} = 3g_{n+1}-2g_n\text{.}\)

4.

Selesaikan persamaan rekurensi \(h_{n+3} = 6h_{n+2}-11h_{n+1} + 6h_n\) jika \(h_0=3\text{,}\) \(h_1=2\text{,}\) dan \(h_2=4\text{.}\)

5.

Tentukan rumus eksplisit untuk bilangan Fibonacci ke-\(n\text{,}\) yaitu \(f_n\text{.}\) (Lihat Subbagian 9.1.1.)

6.

Untuk setiap persamaan operator pemajuan di bawah ini, berikan solusi umumnya.
  1. \(\displaystyle (A-2)(A+10)f=0\)
  2. \(\displaystyle (A^2-36)f=0\)
  3. \(\displaystyle (A^2-2A-5)f=0\)
  4. \(\displaystyle (A^3-4 A^2-20 A+48)f=0\)
  5. \(\displaystyle (A^3 +A^2-5A+ 3)f=0\)
  6. \(\displaystyle (A^3+3 A^2+3 A+1)f=0\)

7.

Selesaikan persamaan operator pemajuan \((A^2+3 A-10)f=0\) jika \(f(0)=2\) dan \(f(1)=10\text{.}\)

8.

Berikan solusi umum untuk setiap persamaan operator pemajuan di bawah ini.
  1. \(\displaystyle (A-4)^3(A+1)(A-7)^4(A-1)^2 f =0\)
  2. \(\displaystyle (A+2)^4(A-3)^2(A-4)(A+7)(A-5)^3g=0\)
  3. \(\displaystyle (A-5)^2(A+3)^3(A-1)^3(A^2-1)(A-4)^3h=0\)

9.

Untuk setiap persamaan operator pemajuan nonhomogen, tentukan solusi umumnya.
  1. \(\displaystyle (A-5)(A+2)f=3^n\)
  2. \(\displaystyle (A^2+3A-1)g = 2^n + (-1)^n\)
  3. \(\displaystyle (A-3)^3 f = 3n+1\)
  4. \(\displaystyle (A^2+3A-1)g = 2n\)
  5. \(\displaystyle (A-2)(A-4)f=3n^2 + 9^n\)
  6. \(\displaystyle (A+2)(A-5)(A-1)f = 5^n\)
  7. \(\displaystyle (A-3)^2(A+1)g= 2\cdot 3^n\)
  8. \(\displaystyle (A-2)(A+3)f=5n2^n\)
  9. \(\displaystyle (A-2)^2(A-1)g=3n^22^n + 2^n\)
  10. \(\displaystyle (A+1)^2(A-3)f = 3^n + 2n^2\)

10.

Tentukan dan selesaikan persamaan rekurensi untuk banyaknya \(g_n\) untai terner sepanjang \(n\) yang tidak memuat \(102\) sebagai subuntai.

11.

Ada sebuah teka-teki terkenal bernama Menara Hanoi yang terdiri atas tiga pasak dan \(n\) cakram bundar yang semuanya berbeda ukuran. Mula-mula, cakram-cakram tersebut berada pada pasak paling kiri, dengan cakram terbesar di bawah, cakram terbesar kedua tepat di atasnya, dan seterusnya hingga cakram terkecil di puncak. Tujuannya adalah memindahkan cakram-cakram itu sehingga tersusun dalam urutan yang sama pada pasak paling kanan. Namun, Anda hanya boleh memindahkan satu cakram setiap kali, dan cakram yang lebih besar tidak pernah boleh diletakkan di atas cakram yang lebih kecil. Misalkan \(t_n\) menyatakan jumlah minimum perpindahan (satu perpindahan berarti mengambil sebuah cakram dari satu pasak dan meletakkannya pada pasak lain) yang diperlukan untuk mencapai tujuan. Tentukan rumus eksplisit untuk \(t_n\text{.}\)

12.

Sebuah pengenal basis data sah sepanjang \(n\) dapat dibentuk dengan tiga cara:
  • Diawali dengan \(A\text{,}\) lalu diikuti sebarang pengenal sah sepanjang \(n-1\text{.}\)
  • Diawali dengan salah satu untai dua karakter \(1A\text{,}\) \(1B\text{,}\) \(1C\text{,}\) \(1D\text{,}\) \(1E\text{,}\) atau \(1F\text{,}\) lalu diikuti sebarang pengenal sah sepanjang \(n-2\text{.}\)
  • Diawali dengan \(0\text{,}\) lalu diikuti sebarang untai terner (\(\{0,1,2\}\)) sepanjang \(n-1\text{.}\)
Tentukan rekurensi untuk banyaknya \(g(n)\) pengenal basis data sepanjang \(n\text{,}\) lalu selesaikan rekurensi tersebut untuk memperoleh rumus eksplisit bagi \(g(n)\text{.}\) (Anda boleh menganggap untai kosong sepanjang \(0\) sebagai pengenal basis data yang sah, sehingga \(g(0)=1\text{.}\) Anggapan ini akan menyederhanakan perhitungannya.)

13.

Misalkan \(t_n\) merupakan banyaknya cara menutupi persegi panjang \(2\times n\) menggunakan ubin \(1\times 1\) dan ubin berbentuk \(L\text{.}\) Ubin berbentuk \(L\) adalah ubin \(2\times 2\) yang persegi \(1\times 1\) di kanan atasnya dihilangkan. (Ubin berbentuk \(L\) boleh diputar sehingga persegi yang “hilang” berada di salah satu dari keempat posisi.) Tentukan rumus rekursif untuk \(t_n\) beserta syarat awal yang cukup untuk memulai rekursinya. Gunakan rumus rekursif tersebut untuk menentukan rumus tertutup bagi \(t_n\text{.}\)

14.

Buktikan Lema 9.22 tentang persamaan operator pemajuan dengan akar berulang.

15.

Gunakan fungsi pembangkit untuk menyelesaikan persamaan rekurensi \(r_n=r_{n-1}+6r_{n-2}\) untuk \(n\geq 2\) dengan \(r_0=1\) dan \(r_1=3\text{.}\)

16.

Misalkan \(a_0=0\text{,}\) \(a_1=2\text{,}\) dan \(a_2=5\text{.}\) Gunakan fungsi pembangkit untuk menyelesaikan persamaan rekurensi \(a_{n+3} = 5a_{n+2} - 7a_{n+1}+3a_n + 2^n\) untuk \(n\geq 0\text{.}\)

17.

Misalkan \(b_0=1\text{,}\) \(b_2=1\text{,}\) dan \(b_3=4\text{.}\) Gunakan fungsi pembangkit untuk menyelesaikan persamaan rekurensi \(b_{n+3} = 4b_{n+2}-b_{n+1}-6b_n + 3^n\) untuk \(n\geq 0\text{.}\)

18.

Gunakan fungsi pembangkit untuk menentukan rumus tertutup bagi bilangan Fibonacci \(f_n\text{.}\)

19.

Ada berapa pohon berakar, tak berlabel, biner, dan terurut (RUBOT) dengan \(6\) daun? Gambarlah \(6\) RUBOT berbeda yang masing-masing memiliki \(6\) daun.

20.

Dalam bab ini, kita mengembangkan fungsi pembangkit bagi bilangan Catalan. Kita pertama kali menjumpai bilangan Catalan dalam Bab 2, ketika kita mempelajari bahwa bilangan tersebut mencacah lintasan kisi tertentu. Kembangkan rekurensi untuk banyaknya \(l_n\) lintasan kisi yang serupa dengan rekurensi
\begin{equation*} c_n = \sum_{k=0}^n c_k c_{n-k}\qquad \text{untuk } n\geq 2 \end{equation*}
bagi RUBOT dengan memikirkan cara menguraikan lintasan kisi dari \((0,0)\) ke \((n,n)\) yang tidak melintasi diagonal \(y=x\) menjadi dua lintasan kisi yang lebih kecil dari jenis yang sama.
SblmKe AtasLnjt