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

Terms

a(0) =1a(1) =4a(2) =16a(3) =65a(4) =268a(5) =1120a(6) =4737a(7) =20244a(8) =87280a(9) =379073a(10) =1656348a(11) =7272896a(12) =32060673a(13) =141775396a(14) =628505296a(15) =2791696705a(16) =12419264300a(17) =55315472416a(18) =246607247233