- Udin sudah bisa menjumlah bilangan, tetapi baru saja belajar menulis angka. Udin baru bisa menulis angka 1, 2, 3 dan 4. Tetapi dia tidak menyadari bahwa angka 1 dan 4 berbeda, bagi Udin “angka 4 adalah cara lain untuk menuliskan angka 1.” Selain itu bilangan beberapa dijit seperti 132 adalah bilangan yang bernilai sama dengan hasil penjumlahan dari digit-digit itu sendiri. Contoh : 132 = 1 + 3 + 2 = 6 dan 112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (ingat, Udin menganggap 4 adalah 1). Sekarang, Udin ingin tahu berapa banyak cara yang dapat dilakukannya untuk menuliskan sebuah bilangan bernilai tertentu. Misalnya 2, Udin dapat menuliskan 5 bilangan yaitu : 11, 14, 41, 44 dan 2. Ada berapa banyak kemungkinan bilangan beberapa digit yang menurut Udin bernilai 3?
Misalkan f(n) adalah fungsi untuk menghitung banyaknya cara menuliskan suatu bilangan bernilai n.
f(1) = 2, karena angka 1 dapat dituliskan dengan ‘1’ atau ‘4’.
Untuk menuliskan bilangan 2, Udin bisa menuliskannya diawali dengan ‘1’ yang mana sisa bilangan menjadi 1,
dengan ‘2’ ataupun dengan ‘4’ yang menyisakan 1 nilai. Jadi f(2) dapat dihitung dengan
f(1) + 1 + f(1) = 2 + 1 + 2 = 5.
Sedangkan jika n = 3, Udin dapat menuliskannya diawali dengan ‘1’ atau ‘4’ dengan sisa 2, menuliskan ‘2’ dengan sisa nilai 1 ataupun ia dapat langsung menuliskannya dengan 3. Jadi f(3) = 2*f(2) + f(1) + 1 = 10 + 2 + 1 = 13.
Secara umum:
f(n) = 2*f(n-1) + f(n-2) + f(n-3), untuk n >= 4.
f(1) = 2
f(2) = 5
f(3) = 13
