Sebuah basis data menggunakan pengenal rekaman berupa string alfanumerik, dengan \(10\) digit desimal dan \(26\) huruf kapital sebagai simbol yang valid. Kriteria yang mendefinisikan pengenal rekaman valid bersifat rekursif. Pengenal rekaman valid sepanjang \(n\geq 2\) dapat dibentuk dengan cara berikut:
diawali huruf kapital apa pun selain \(D\text{,}\) lalu diikuti pengenal rekaman valid sepanjang \(n-1\text{;}\)
Misalkan \(r(n)\) menyatakan banyaknya pengenal rekaman valid sepanjang \(n\text{.}\) Kita tetapkan \(r(0)=1\) dan perhatikan bahwa \(r(1) = 26\text{.}\) Tentukan rekursi untuk \(r(n)\) ketika \(n\geq 2\text{,}\) lalu gunakan rekursi tersebut untuk menghitung \(r(5)\text{.}\)
Perhatikan papan kotak-kotak berukuran \(1\times n\text{.}\) Petak-petaknya akan diwarnai putih dan emas, tetapi tidak boleh ada dua petak berurutan yang keduanya berwarna putih. Misalkan \(p(n)\) menyatakan banyaknya cara mewarnai papan tersebut dengan memenuhi aturan ini. Tentukan rumus rekursif untuk \(p(n)\) yang berlaku bagi \(n\geq 3\text{.}\)
Papan kotak-kotak berukuran \(2\times n\) akan dipasangi dua jenis ubin. Jenis pertama adalah ubin persegi berukuran \(1\times 1\text{.}\) Jenis kedua disebut ubin-\(L\) dan dibentuk dengan membuang petak \(1\times 1\) di kanan atas dari ubin berukuran \(2\times 2\text{.}\) Ubin-\(L\) dapat digunakan dalam keempat orientasi hasil rotasinya. (Artinya, “petak yang hilang” dapat berada di salah satu dari empat posisi.) Misalkan \(t(n)\) menyatakan banyaknya cara memasang ubin pada papan \(2\times n\) menggunakan ubin \(1\times 1\) dan ubin-\(L\text{.}\) Tentukan rumus rekursif untuk \(t(n)\text{,}\) lalu gunakan rumus tersebut untuk menentukan \(t(7)\text{.}\)
Misalkan \(S\) adalah himpunan string atas alfabet \(\{0,1,2,3\}\) yang tidak memuat \(12\) maupun \(20\) sebagai blok berurutan. Berikan rekursi untuk banyaknya string \(h(n)\) dalam \(S\) yang panjangnya \(n\text{.}\)
Misalkan \(a\text{,}\)\(b\text{,}\)\(m\text{,}\) dan \(n\) adalah bilangan bulat dan andaikan \(am+bn=36\text{.}\) Apa yang dapat Anda simpulkan mengenai \(\gcd(m,n)\text{?}\)
(Soal menantang) Untuk setiap rumus, berikan pembuktian menggunakan Prinsip Induksi Matematika sekaligus pembuktian kombinatorial. Salah satu dari kedua pembuktian tersebut akan lebih mudah, sedangkan yang lain akan lebih menantang.
Ternyata, jika \(a\) dan \(b\) adalah bilangan bulat positif dengan \(a>b+1\text{,}\) terdapat bilangan bulat positif \(M>1\) sedemikian sehingga \(a^n-b^n\) habis dibagi \(M\) untuk setiap bilangan bulat positif \(n\text{.}\) Tentukan \(M\) dalam suku \(a\) dan \(b\text{,}\) lalu buktikan bahwa bilangan tersebut merupakan pembagi \(a^n-b^n\) untuk setiap bilangan bulat positif \(n\text{.}\)
Berikan pembuktian induktif untuk Teorema Binomial (Teorema 2.30). Menurut Anda, bagaimana perbandingannya dengan argumen kombinatorial yang diberikan dalam Bab 2?
Perhatikan rekursi \(f(n) = 2f(n-1) - f(n-2) + 6\) untuk \(n\geq 2\text{,}\) dengan \(f(0)=2\) dan \(f(1)=4\text{.}\) Gunakan induksi matematika untuk membuktikan bahwa \(f(n) = 3n^2-n+2\) bagi setiap bilangan bulat \(n\geq 0\text{.}\)
Perhatikan rekursi \(f(n) = f(n-1)+f(n-2)\) untuk \(n\geq 3\text{,}\) dengan \(f(1)=f(2)=1\text{.}\) Buktikan bahwa \(f(n)\) habis dibagi \(3\) jika dan hanya jika \(n\) habis dibagi \(4\text{.}\)
Buktikan bahwa terdapat konstanta positif \(c\) sedemikian sehingga setiap algoritma pengurutan berbasis perbandingan untuk barisan yang terdiri atas \(n\) bilangan bulat positif, dalam kasus terburuk, memerlukan setidaknya \(cn\log n\) operasi perbandingan.
Petunjuk: Terdapat \(n!\) permutasi dari suatu himpunan yang terdiri atas \(n\) bilangan bulat berbeda. Setiap operasi perbandingan memiliki dua kemungkinan hasil, sehingga pada setidaknya satu cabang, pecahan kemungkinan yang tersisa paling sedikit \(1/2\text{.}\) Jadi, jika terdapat \(t\) operasi perbandingan, maka \(2^t\ge n!\text{.}\) Sekarang, carilah pendekatan Stirling untuk \(n!\text{,}\) lalu lanjutkan dari sana.
