A000128 A nonlinear binomial sum.

1, 2, 4, 8, 16, 31, 58, 105, 185, 319, 541, 906, 1503, 2476, 4058, 6626, 10790, 17537, 28464, 46155, 74791, 121137, 196139, 317508, 513901, 831686, 1345888, 2177900, 3524140, 5702419, 9226966, 14929821, 24157253, 39087571, 63245353, 102333486

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• Ralph P. Grimaldi, A generalization of the Fibonacci sequence. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 54 (1986), 123-128. MR0885268 (89f:11030). - N. J. A. Sloane, Apr 08 2012
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=1..201
• D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Index entries for linear recurrences with constant coefficients, signature (4,-5,1,2,-1).

Crossrefs

Differences are A000126.

Second differences are A000071 (Fibonacci -1).

Cf. A000045.

Programs

Maple

A000128:=(1-2*z+z**2+z**3)/(z**2+z-1)/(z-1)**3; # conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

LinearRecurrence[{4, -5, 1, 2, -1}, {1, 2, 4, 8, 16}, 40] (* Jean-François Alcover, Feb 04 2016 *)

Formula

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

a(n) = F(n+4) - n*(n+1)/2 - 3, with F(n) = A000045(n). - Ralf Stephan, Aug 19 2004

a(n) = 2*a(n-1) - a(n-3) + n - 3, n > 3, and a(1) = 1, a(2) = 2, a(3) = 4. - Chunqing Liu, Sep 23 2023

Extensions

More terms from Michel ten Voorde, Oct 06 2002