A111500 Number of squares in an n X n grid of squares with diagonals.

1, 10, 31, 72, 137, 234, 367, 544, 769, 1050, 1391, 1800, 2281, 2842, 3487, 4224, 5057, 5994, 7039, 8200, 9481, 10890, 12431, 14112, 15937, 17914, 20047, 22344, 24809, 27450, 30271, 33280, 36481, 39882, 43487, 47304, 51337, 55594, 60079, 64800, 69761, 74970

Offset

0,2

Comments

This sequence is the sum of the number of squares with horizontal/vertical sides (whose length is a positive integer), which is equal to Sum_{j=1..n} j^2 = (n*(n + 1)*(2*n + 1))/6, and the number of squares with diagonal sides (whose length is a multiple of sqrt(2)/2), which is Sum_{j=1..n} (A111746(n - 1)) = floor((n*(4*n^2 - 1))/6). - Marco Ripà, Jan 14 2024

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Formula

a(n) = n^3 + n^2/2 - 1/4 + (1/4)*(-1)^n.

a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5) for n > 4. - Colin Barker, May 28 2015

G.f.: (x^3 + 3*x^2 + 7*x + 1) / ((x-1)^4*(x+1)). - Colin Barker, May 28 2015

From Marco Ripà, Jan 14 2024: (Start)

a(n) = Sum_{j=1..n} (A000290(j) + A111746(j-1)).

a(n) = floor(n^3 + n^2/2). (End)

Maple

seq(n^3+n^2/2-1/4+1/4*(-1)^n, n=1..65);

Prog

(PARI) Vec((x^3+3*x^2+7*x+1) / ((x-1)^4*(x+1)) + O(x^100)) \\ Colin Barker, May 28 2015

Crossrefs

Cf. A000290, A100583, A111746.

Sequence in context: A297507 A163655 A041190 * A342362 A161325 A187705

Adjacent sequences: A111497 A111498 A111499 * A111501 A111502 A111503

Keyword

nonn,easy

Author

Floor van Lamoen, Nov 16 2005

Status

approved