Latihan 13.
String terner adalah barisan yang terdiri atas angka 0, 1, dan 2. String ini seperti string bit, tetapi menggunakan tiga simbol.
Sebut suatu string terner baik jika string itu tidak pernah memuat angka 2 yang langsung diikuti angka 0. Misalkan \(G_n\) adalah banyaknya string baik dengan panjang \(n\text{.}\) Sebagai contoh, \(G_1 = 3\) dan \(G_2 = 8\) (karena dari 9 string terner dengan panjang 2, hanya satu yang tidak baik).
Tentukan, disertai alasan, rumus rekursif untuk \(G_n\text{,}\) lalu gunakan rumus itu untuk menghitung \(G_5\text{.}\)
Petunjuk.
Pertimbangkan tiga kasus: angka terakhir adalah 0, 1, atau 2. Dua kasus mudah dicacah, tetapi string yang berakhir dengan 0 tidak boleh didahului oleh 2, sehingga kasus ini memerlukan sedikit usaha tambahan.