a(n) = 2*a(n-1) + 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) =4a(4) =10a(5) =25a(6) =64a(7) =157a(8) =388a(9) =943a(10) =2299a(11) =5566a(12) =13495a(13) =32620a(14) =78892a(15) =190561a(16) =460402a(17) =1111753a(18) =2684851a(19) =6482398a(20) =15651946a(21) =37788589a(22) =91234690a(23) =220263535a(24) =531775255a(25) =1283827540a(26) =3099462955a(27) =7482786070a(28) =18065113987a(29) =43613092936