a(n) = floor(9^n/4^n).

Terms

a(0) =1a(1) =2a(2) =5a(3) =11a(4) =25a(5) =57a(6) =129a(7) =291a(8) =656a(9) =1477a(10) =3325a(11) =7481a(12) =16834a(13) =37876a(14) =85222a(15) =191751a(16) =431439a(17) =970739a(18) =2184164a(19) =4914369a(20) =11057332a(21) =24878997a(22) =55977744a(23) =125949925a(24) =283387333a(25) =637621500a(26) =1434648375a(27) =3227958844a(28) =7262907400a(29) =16341541651