A141001 a(n) = number of different landings of a grasshopper after n hops.

1, 1, 1, 2, 3, 4, 7, 11, 16, 21, 26, 32, 38, 44, 51, 59, 67, 75, 84, 94, 104, 114, 125, 137, 149, 161, 174, 188, 202, 216, 231, 247, 263, 279, 296, 314, 332, 350, 369, 389, 409, 429, 450, 472, 494, 516, 539, 563, 587, 611, 636, 662, 688, 714, 741, 769, 797

Offset: 0

Author

David Applegate and N. J. A. Sloane, Jul 21 2008

Keywords

• nonn
• easy

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

Examples

			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.
		

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

Crossrefs

Cf. A141000, A141002.

Programs

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

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

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)