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

Terms

a(0) =1a(1) =1a(2) =4a(3) =19a(4) =55a(5) =220a(6) =793a(7) =2845a(8) =10480a(9) =37963a(10) =138259a(11) =503608a(12) =1831969a(13) =6669865a(14) =24276892a(15) =88362451a(16) =321640831a(17) =1170726484a(18) =4261339801a(19) =15510894949a(20) =56458080328a(21) =205502135851a(22) =748007984827