A360724 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.

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, 70, 76, 84, 94, 106, 120, 136, 151, 165, 178, 190, 201, 211, 220, 228, 235, 241, 246, 250, 253, 255, 256, 256, 258, 262, 268, 276, 286, 298, 312, 328, 346, 366, 388

Offset

0,4

Comments

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

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

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

References

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..20000

Formula

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.

Maple

a:= proc(n) option remember; `if`(n<2, n, (h->
      (1+2*m)*a(h)+(3-2*m)*a(h-1))(iquo(n, 2, 'm')))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Feb 18 2023

Mathematica

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 *)

Crossrefs

Sequence in context: A351371 A280448 A100692 * A089640 A086659 A265887

Adjacent sequences: A360721 A360722 A360723 * A360725 A360726 A360727

Keyword

nonn,look

Author

Jeffrey Shallit, Feb 18 2023

Status

approved