A072951 a(n) = Sum_{k=1..n} binomial(k, n mod k).

1, 2, 4, 6, 11, 15, 27, 39, 63, 100, 159, 247, 403, 641, 1023, 1644, 2653, 4264, 6872, 11081, 17895, 28899, 46680, 75420, 121918, 197113, 318728, 515420, 833592, 1348309, 2181022, 3528144, 5707568, 9233629, 14938481, 24168531, 39102324

Offset: 1

Author

Benoit Cloitre, Aug 20 2002

Keywords

• easy
• nonn

Comments

a(n) = Sum_{k>=2} z(k)*v(k)^n where v(k) is the real positive solution to x^k = x + 1 (i.e., the k-th Pisot-Vijayaraghavan number) and z(k) is the real positive root of a polynomial P(k,x) with integer coefficients of degree k.

In particular a(n) is asymptotic to (1/10)*(5 + sqrt(5))*phi^n where phi is the golden ratio.

First P(k,x) are P(2,x) = 5x^2 - 5x - 1; P(3,x) = 23x^3 - 23x^2 + 8x - 1; P(4) = 283x^4 - 283x^3 + 105x^2 - 17x + 1; P(5) = 2869x^5 - 2869x^4 + 1154x^3 - 234x^2 + 24x - 1.

a(n) is the number of compositions of n into almost equal parts. It means the difference between the largest part and the smallest part is at most 1. For example, there are 6 compositions of 4 into almost equal parts, (4), (2,2), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1). - Ran Pan, Oct 16 2015

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Programs

Magma

[&+[Binomial(k, n mod k): k in [1..n]]: n in [1..40]]; // Vincenzo Librandi, Jul 31 2017

Mathematica

Table[Sum[Binomial[k, Mod[n, k]], {k, n}], {n, 37}] (* Michael De Vlieger, Jul 30 2017 *)

PARI

a(n)=sum(k=1,n,binomial(k,n%k))

Extensions

Name from Benoit Cloitre, May 03 2003