a(n) = Sum_{k=0..n} C(n-k, floor(k/2))*3^k.

Terms

a(0) =1a(1) =4a(2) =4a(3) =13a(4) =49a(5) =85a(6) =202a(7) =643a(8) =1408a(9) =3226a(10) =9013a(11) =21685a(12) =50719a(13) =131836a(14) =327001a(15) =783472a(16) =1969996a(17) =4913005a(18) =11964253a(19) =29694217a(20) =73911262a(21) =181589539a(22) =448837492a(23) =1114038850a(24) =2748344701a(25) =6787882129a(26) =16814231779a(27) =41549334088a(28) =102640273249