A207644 a(n) = 1 + (n-1) + (n-2)*[(n-3)/2] + (n-3)*[(n-4)/2]*[(n-5)/3] + (n-4)*[(n-5)/2]*[(n-6)/3]*[(n-7)/4] +... where [x] = floor(x), with summation extending over the initial [n/2+1] products only.

1, 1, 2, 3, 4, 8, 10, 17, 30, 42, 55, 116, 172, 220, 391, 683, 1024, 1616, 2050, 3675, 6520, 9504, 12505, 22421, 35572, 56918, 85701, 138110, 202765, 326231, 503632, 860497, 1376870, 1927446, 2818531, 4892966, 7784671, 11432772, 17287295, 30423457, 46453786, 71810414

Offset: 0

Author

Paul D. Hanna, Feb 19 2012

Keywords

• nonn
• nice

Comments

Radius of convergence of g.f. A(x) is near 0.637..., with A(1/phi) = 23.059250143... where phi = (sqrt(5)+1)/2.

Compare the definition of a(n) with the binomial sum:

Fibonacci(n) = 1 + (n-1) + (n-2)*((n-3)/2) + (n-3)*((n-4)/2)*((n-5)/3) + (n-4)*((n-5)/2)*((n-6)/3)*((n-7)/4) +...

with summation extending over the initial [n/2+1] products only.

Examples

			a(3) = 1 + 2 = 3;
a(4) = 1 + 3 + 2*[1/2] = 4;
a(5) = 1 + 4 + 3*[2/2] = 8;
a(6) = 1 + 5 + 4*[3/2] + 3*[2/2]*[1/3] = 10;
a(7) = 1 + 6 + 5*[4/2] + 4*[3/2]*[2/3] = 17;
a(8) = 1 + 7 + 6*[5/2] + 5*[4/2]*[3/3] + 4*[3/2]*[2/3]*[1/4] = 30;
a(9) = 1 + 8 + 7*[6/2] + 6*[5/2]*[4/3] + 5*[4/2]*[3/3]*[2/4] = 42; ...
		

Links

• Paul D. Hanna, Table of n, a(n) for n = 0..500

Crossrefs

Cf. A075885, A207643, A207645, A207646, A207647.

Programs

Mathematica

a[n_] := 1 + Sum[ Product[ Floor[ (n-k-j+1)/j ], {j, 1, k}], {k, 1, n/2}]; Table[a[n], {n, 0, 41}] (* Jean-François Alcover, Mar 06 2013 *)

PARI

{a(n)=1+sum(k=1,n\2,prod(j=1,k,floor((n-k-j+1)/j)))}
for(n=0,60,print1(a(n),", "))

Formula

a(n) = 1 + Sum_{k=1..[n/2]} Product_{j=1..k} floor( (n-k-j+1) / j ).

Equals the antidiagonal sums of triangle A207645.