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

Terms

a(0) =1a(1) =4a(2) =13a(3) =52a(4) =133a(5) =604a(6) =1333a(7) =6772a(8) =13333a(9) =74284a(10) =133333a(11) =801892a(12) =1333333a(13) =8550364a(14) =13333333a(15) =90286612a(16) =133333333a(17) =945912844a(18) =1333333333a(19) =9846548932a(20) =13333333333a(21) =101952273724a(22) =133333333333