OFFSET
0,3
COMMENTS
a(n) is equal to h_4(n) as defined in A309038.
a(n) is the maximum size of an induced subtree in the graph of the black squares of an n X n checkerboard, where edges connect diagonally adjacent squares. - Andrew Howroyd, Sep 10 2019
LINKS
Stefano Spezia, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1,-2,1).
FORMULA
O.g.f.: x*(1 + 2*x^2 - 2*x^3 + x^4 + 2*x^5 - 2*x^7)/((1 - x)^3*(1 + x)*(1 + x^2)).
E.g.f.: -3*exp(-x)/8 + (2 + x)^2 + exp(x)/8*(-29 + 2*x*(7 + x)) - 3*sin(x)/2.
a(n) = 2*a(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6) for n > 8.
a(n) = (1/8)*(-29 + 12*n + 2*n^2 - 3*(-1)^n - 12*sin(n*Pi/2)) for n > 2, a(0) = 0, a(1) = 1, a(2) = 2.
Limit_{n->oo} a(n)/A000290(n) = 1/4.
EXAMPLE
Illustrations for n = 1..7:
__ __ __ __
|__| |__|__ |__|__|__|
|__| __|__|__
|__| |__|
a(1) = 1 a(2) = 2 a(3) = 5
__ __ __ __
|__|__|__| |__|__|__|
__|__|__ __|__|__ __
|__| |__|__ |__| |__|__|__|
|__| __|__|__
|__| |__|
a(4) = 6 a(5) = 9
__ __ __ __ __ __ __
|__|__|__| |__|__ |__|__|__| |__|__|__|
__|__|__ __|__| __|__|__ __|__|__
|__| |__|__|__| |__| |__|__|__| |__|
__ __|__|__ __ __|__|__ __
|__|__|__| |__|__ |__|__|__| |__|__|__|
|__| |__| __|__|__ __|__|__
|__| |__| |__| |__|
a(6) = 14 a(7) = 21
MATHEMATICA
Join[{0, 1, 2}, Table[(1/8)*(-29+12*n+2*n^2-3(-1)^n-12*Sin[n*Pi/2]), {n, 3, 57}]]
PROG
(Magma) I:=[0, 1, 2, 5, 6, 9, 14, 21, 24]; [n le 9 select I[n] else 2*Self(n-1)-Self(n-2)+Self(n-4)-2*Self(n-5)+Self(n-6): n in [1..58]];
(PARI) concat([0], Vec(x*(-1-2*x^2+2*x^3-x^4-2*x^5+2*x^7)/((-1+x)^3*(1+x)*(1+x^2))+O(x^58)))
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Stefano Spezia, Sep 10 2019
STATUS
approved