OFFSET
0,4
COMMENTS
Consider a grasshopper (cf. A141000) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraint that it must always land on a point x >= 0; sequence gives number of different places x where it can land after the n-th jump.
Here, unlike A141000, there is no restriction on how large x can be (of course x <= n(n+1)/2).
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).
FORMULA
a(n) = floor(n * (n+1) / 4 - 1) for n >= 9. The induction proof for A141000 shows that for n >= 21, you hit all numbers of the right parity except n(n+1)/2-2 and n(n+1)/2-4. The floor expression handles the various parity cases. - David Applegate.
G.f.: (1 - 2*x + 2*x^2 - x^3 + x^5 + x^6 - x^7 + 2*x^8 - 2*x^9 - x^12 + x^13) / ((1 - x)^3*(1 + x^2)). - Colin Barker, May 21 2013
From Colin Barker, Aug 06 2017: (Start)
a(n) = (1/8+i/8) * ((-5+5*i) + (-i)^(1+n) + i^n + (1-i)*n + (1-i)*n^2) for n>8 where i=sqrt(-1).
a(n) = 3*a(n-1) - 4*a(n-2) + 4*a(n-3) - 3*a(n-4) + a(n-5) for n>9.
(End)
EXAMPLE
For example, for n=3 the grasshopper can hit 0=1+2-3 or 6=1+2+3; for n=4 it can hit 2=1+2+3-4, 4=1+2-3+4, or 10=1+2+3+4.
MATHEMATICA
LinearRecurrence[{3, -4, 4, -3, 1}, {1, 1, 1, 2, 3, 4, 7, 11, 16, 21, 26, 32, 38, 44}, 60] (* Harvey P. Dale, Mar 26 2023 *)
PROG
(PARI) Vec((1 - 2*x + 2*x^2 - x^3 + x^5 + x^6 - x^7 + 2*x^8 - 2*x^9 - x^12 + x^13) / ((1 - x)^3*(1 + x^2)) + O(x^60)) \\ Colin Barker, Aug 06 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
David Applegate and N. J. A. Sloane, Jul 21 2008
STATUS
approved