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,3

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.

Links

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

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.

Example

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

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

Prog

(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), ", "))

Crossrefs

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

Sequence in context: A308811 A295296 A186417 * A114854 A127279 A106131

Adjacent sequences: A207641 A207642 A207643 * A207645 A207646 A207647

Keyword

nonn,nice

Author

Paul D. Hanna, Feb 19 2012

Status

approved