A137402 a(n) = Sum_{k=0..n} binomial(floor(n-2k/3), k).

1, 1, 2, 3, 5, 9, 16, 28, 48, 81, 136, 229, 388, 661, 1129, 1928, 3287, 5594, 9510, 16164, 27484, 46757, 79577, 135454, 230552, 392355, 667620, 1135924, 1932721, 3288563, 5595805, 9522067, 16203273, 27572144, 46917243, 79834375, 135845607, 231154212

Offset: 0

Author

Don Knuth, Apr 11 2008

Keywords

• nonn
• easy

Comments

A_n + B_{n-1} + C_{n-2} in the notation of A137356.

Lim_{n->infinity} a(n+1)/a(n) = x ~= 1.7016..., with x given by the real root (A324498) of (x - 1)^3*x^2 = 1. - Hugo Pfoertner, Mar 15 2019

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1,0,1).

Crossrefs

Cf. A137356, A137357, A137358, A324498.

Programs

Magma

[(&+[Binomial(Floor(n-2*k/3), k): k in [0..n]]): n in [0..40]]; // G. C. Greubel, Mar 15 2019

Maple

f:=n->add( binomial( floor(n-2*k/3), k), k=0..n);

Mathematica

Table[Sum[Binomial[Floor[n-(2k)/3],k],{k,0,n}],{n,0,40}] (* or *) LinearRecurrence[{3,-3,1,0,1},{1,1,2,3,5},40] (* Harvey P. Dale, Aug 22 2011 *)

PARI

Vec((1-2*x+2*x^2-x^3+x^4)/(1-3*x+3*x^2-x^3-x^5) + O(x^50)) \\ Colin Barker, Dec 14 2015

PARI

a(n) = sum(k=0, n, binomial(floor(n-2*k/3), k)); \\ Altug Alkan, Dec 14 2015

Sage

[sum(binomial(floor(n-2*k/3),k) for k in (0..n)) for n in (0..40)] # G. C. Greubel, Mar 15 2019

Formula

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) + a(n-5); a(0)=1, a(1)=1, a(2)=2, a(3)=3, a(4)=5. - Harvey P. Dale, Aug 22 2011

G.f.: (1 - 2*x + 2*x^2 - x^3 + x^4) / (1 - 3*x + 3*x^2 - x^3 - x^5). - Colin Barker, Dec 14 2015