a(n) = 2*a(n-1) + 2*a(n-2) + a([n/2]), where a(0) = 1, a(1) = 1, a(2) = 1.

Terms

a(0) =1a(1) =1a(2) =1a(3) =5a(4) =13a(5) =37a(6) =105a(7) =289a(8) =801a(9) =2193a(10) =6025a(11) =16473a(12) =45101a(13) =123253a(14) =336997a(15) =920789a(16) =2516373a(17) =6875125a(18) =18785189a(19) =51322821a(20) =140222045a(21) =383095757a(22) =1046652077a(23) =2859512141a(24) =7812373537a(25) =21343816457a(26) =58312503241a(27) =159312762649a(28) =435250868777