A087640 To obtain a(n+1), take the square of the n-th partial sum, minus the sum of the first n squared terms, then divide this difference by a(n); for all n>1, starting with a(0)=1, a(1)=1.

1, 1, 2, 5, 10, 23, 48, 107, 228, 501, 1078, 2353, 5086, 11067, 23972, 52087, 112936, 245225, 531946, 1154685, 2505298, 5437407, 11798616, 25605539, 55563980, 120581981, 261668382, 567850345, 1232273510, 2674156163, 5803126348

Offset: 0

Author

Paul D. Hanna, Sep 15 2003

Keywords

• nonn

Comments

For n > 0, a(n) counts the number of walks of length n-1 starting at vertex A in the undirected graph with edge set {(A, B), (A, C), (B, C), (C, D)}. - Noah Niederklein, Jun 07 2025

Links

• Sean A. Irvine, Walks on Graphs
• Index entries for linear recurrences with constant coefficients, signature (1,3,-1).

Crossrefs

Cf. A052973.

Programs

Mathematica

CoefficientList[Series[(1-2x^2+x^3)/(1-x-3x^2+x^3),{x,0,40}],x] (* or *) LinearRecurrence[{1,3,-1},{1,1,2,5},40] (* Harvey P. Dale, Dec 06 2015 *)

PARI

{a(n) = if(n<=1,1,( sum(k=0, n-1, a(k))^2 - sum(k=0, n-1, a(k)^2) )/a(n-1))}
for(n=0,40,print1(a(n),", "))

Formula

a(n) = a(n-1) + 3a(n-2) - a(n-3) for n>3.

G.f.: (1-2x^2+x^3)/(1-x-3x^2+x^3).

G.f.: A052973(x)/(1+x-x^2).