%I #22 Feb 24 2023 20:47:25

%S 0,1,1,3,4,4,6,10,13,15,16,16,18,22,28,36,43,49,54,58,61,63,64,64,66,

%T 70,76,84,94,106,120,136,151,165,178,190,201,211,220,228,235,241,246,

%U 250,253,255,256,256,258,262,268,276,286,298,312,328,346,366,388

%N Hajnal's recurrence: a(2n) = a(n) + 3*a(n-1); a(2n+1) = 3*a(n) + a(n-1), with initial values a(0) = 0, a(1) = 1.

%C liminf a(n)/n^2 = 1/10; in fact a(n) >= (n^2+3n)/10 for all n, and this bound is tight.

%C limsup a(n)/n^2 = 1/7; in fact a(n) <= (n^2+3n+3)/7 for all n, and this bound is tight.

%C Although it is not immediately obvious from the definition, the sequence is increasing (but not strictly increasing).

%D Message from Peter Hajnal to the author, June 22 2008.

%H Alois P. Heinz, <a href="/A360724/b360724.txt">Table of n, a(n) for n = 0..20000</a>

%F a(n) = 10*4^i + (n+1)(n+2) - (6n+9)*2^i, if 3*2^i <= n < 4*2^i; a(n) = (6n+9)*2^i - 14*4^i - (n+1)(n+2)/2, if 4*2^i <= n < 6*2^i.

%p a:= proc(n) option remember; `if`(n<2, n, (h->

%p (1+2*m)*a(h)+(3-2*m)*a(h-1))(iquo(n, 2, 'm')))

%p end:

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Feb 18 2023

%t nn = 120; Array[Set[a[#], #] &, 2, 0]; Do[Set[a[n], If[EvenQ[n], a[#] + 3 a[# - 1] &[n/2], 3 a[#] + a[# - 1] &[(n - 1)/2]]], {n, 2, nn}]; Array[a, nn + 1, 0] (* _Michael De Vlieger_, Feb 18 2023 *)

%K nonn,look

%O 0,4

%A _Jeffrey Shallit_, Feb 18 2023