A027941 a(n) = Fibonacci(2*n + 1) - 1.

0, 1, 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, 75024, 196417, 514228, 1346268, 3524577, 9227464, 24157816, 63245985, 165580140, 433494436, 1134903169, 2971215072, 7778742048, 20365011073, 53316291172, 139583862444, 365435296161, 956722026040

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy
• nice

Comments

Also T(2n+1,n+1), T given by A027935. Also first row of Inverse Stolarsky array.

Third diagonal of array defined by T(i, 1)=T(1, j)=1, T(i, j)=Max(T(i-1, j)+T(i-1, j-1); T(i-1, j-1)+T(i, j-1)). - Benoit Cloitre, Aug 05 2003

Number of Schroeder paths of length 2(n+1) having exactly one up step starting at an even height (a Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis). Schroeder paths are counted by the large Schroeder numbers (A006318). Example: a(1)=4 because among the six Schroeder paths of length 4 only the paths (U)HD, (U)UDD, H(U)D, (U)DH have exactly one U step that starts at an even height (shown between parentheses). - Emeric Deutsch, Dec 19 2004

Also: smallest number not writeable as the sum of fewer than n positive Fibonacci numbers. E.g., a(5)=88 because it is the smallest number that needs at least 5 Fibonacci numbers: 88 = 55 + 21 + 8 + 3 + 1. - Johan Claes, Apr 19 2005 [corrected for offset and clarification by Mike Speciner, Sep 19 2023] In general, a(n) is the sum of n positive Fibonacci numbers as a(n) = Sum_{i=1..n} A000045(2*i). See A001076 when negative Fibonacci numbers can be included in the sum. - Mike Speciner, Sep 24 2023

Except for first term, numbers a(n) that set a new record in the number of Fibonacci numbers needed to sum up to n. Position of records in sequence A007895. - Ralf Stephan, May 15 2005

Successive extremal petal bends beta(n) = a(n-2). See the Ring Lemma of Rodin and Sullivan in K. Stephenson, Introduction to Circle Packing (Cambridge U. P., 2005), pp. 73-74 and 318-321. - David W. Cantrell (DWCantrell(AT)sigmaxi.net)

a(n+1)= AAB^(n)(1), n>=1, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 4=`110`, 12=`1100`, 33=`11000`, 88=`110000`, ..., in Wythoff code. AA(1)=1=a(1) but for uniqueness reason 1=A(1) in Wythoff code. - N. J. A. Sloane, Jun 29 2008

Start with n. Each n generates a sublist {n-1,n-1,n-2,..,1}. Each element of each sublist also generates a sublist. Add numbers in all terms. For example, 3->{2,2,1} and both 2->{1,1}, so a(3) = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 12. - Jon Perry, Sep 01 2012

For n>0: smallest number such that the inner product of Zeckendorf binary representation and its reverse equals n: A216176(a(n)) = n, see also A189920. - Reinhard Zumkeller, Mar 10 2013

Also, numbers m such that 5*m*(m+2)+1 is a square. - Bruno Berselli, May 19 2014

Also, number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015

From Robert K. Moniot, Oct 04 2020: (Start)

Including a(-1):=0, consecutive terms (a(n-1),a(n))=(u,v) or (v,u) give all points on the hyperbola u^2-u+v^2-v-4*u*v=0 with both coordinates nonnegative integers. Note that this follows from identifying (1,u+1,v+1) with the Markov triple (1,Fibonacci(2n-1),Fibonacci(2n+1)). See A001519 (comments by Robert G. Wilson, Oct 05 2005, and Wolfdieter Lang, Jan 30 2015).

Let T(n) denote the n-th triangular number. If i, j are any two successive elements of the above sequence then (T(i-1) + T(j-1))/T(i+j-1) = 3/5. (End)

Examples

			a(5) = 88 = 2*33 + 12 + 4 + 1 + 5. a(6) = 232 = 2*88 + 33 + 12 + 4 + 1 + 6. - _Jon Perry_, Sep 01 2012
a(4) = 33 counts all nonempty submultisets of the last row: [1][2][3][4], [11][12][13][14][22][23][24][33][34], [111][112][113][122][123][124][133][134][222][223][233][234], [1111][1112][1122][1123][1222][1223][1233][1234]. - _Gus Wiseman_, Feb 10 2015
		

References

• A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 12.

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
• Russ Euler and Jawad Sadek, Problem B-912, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 39, No. 1 (2001), p. 85; From a Product to a Sum, Solution to Problem B-912 by Charles K. Cook, ibid., Vol. 39, No. 5 (2001), pp. 468-469.
• Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 7.
• Clark Kimberling, Interspersions.
• Clark Kimberling, Interspersions and dispersions, Proceedings of the American Mathematical Society, 117 (1993) 313-321.
• Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
• R. J. Mathar, Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings, arXiv:1311.6135 [math.CO], 2013, Table 60 (doubled).
• Luis A. Medina and Armin Straub, On multiple and infinite log-concavity, Annals of Combinatorics, Vol. 20, No. 1 (2016), pp. 125-138; arXiv preprint, arXiv:1405.1765 [math.CO], 2014; preprint, 2014.
• László Németh, Hyperbolic Pascal pyramid, arXiv:1511.02067 [math.CO], 2015 (2nd line of Table 1 is 3*a(n-2)).
• László Németh, Pascal pyramid in the space H^2×R, arXiv:1701.06022 [math.CO], 2016. See bn in Table 1 p.10.
• N. J. A. Sloane, Classic Sequences.
• Index entries for sequences related to Chebyshev polynomials.
• Index entries for linear recurrences with constant coefficients, signature (4,-4,1).

Crossrefs

Cf. A000045, A035507, A001906, A006318, A000032.

Related to partial sums of Fibonacci(k*n) over n: A000071, A099919, A058038, A138134, A053606; this sequence is the case k=2.

Cf. A212336 for more sequences with g.f. of the type 1/(1 - k*x + k*x^2 - x^3).

Cf. A000225 (sublist connection).

Cf. A258993 (row sums, n > 0), A000967.

Programs

Haskell

a027941 = (subtract 1) . a000045 . (+ 1) . (* 2)
-- Reinhard Zumkeller, Mar 10 2013

Magma

[Fibonacci(2*n+1)-1: n in [0..30]]; // Vincenzo Librandi, Apr 18 2011

Maple

with(combinat): seq(fibonacci(2*n+1)-1,n=1..27); # Emeric Deutsch, Dec 19 2004
a:=n->sum(binomial(n+k+1,2*k), k=0..n): seq(a(n), n=-1..26); # Zerinvary Lajos, Oct 02 2007

Mathematica

Table[Fibonacci[2*n+1]-1,{n,0,17}] (* Vladimir Joseph Stephan Orlovsky, Jul 21 2008 *)
LinearRecurrence[{4,-4,1},{0,1,4},40] (* Harvey P. Dale, Aug 17 2021 *)

Maxima

a(n):=sum(binomial(n+1,k+1)*fib(k),k,0,n); /* Vladimir Kruchinin, Oct 14 2016 */

PARI

a(n)=fibonacci(2*n+1)-1 \\ Charles R Greathouse IV, Nov 20 2012

PARI

concat(0, Vec(x/((1-x)*(1-3*x+x^2)) + O(x^40))) \\ Colin Barker, Jun 03 2016

Formula

a(n) = Sum_{i=1..n} binomial(n+i, n-i). - Benoit Cloitre, Oct 15 2002

G.f.: Sum_{k>=1} x^k/(1-x)^(2*k+1). - Benoit Cloitre, Apr 21 2003

a(n) = Sum_{k=1..n} F(2*k), i.e., partial sums of A001906. - Benoit Cloitre, Oct 27 2003

a(n) = Sum_{k=0..n-1} U(k, 3/2) = Sum_{k=0..n-1} S(k, 3), with S(k, 3) = A001906(k+1). - Paul Barry, Nov 14 2003

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

a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) with n>=2, a(-1)=0, a(0)=0, a(1)=1.

a(n) = 3*a(n-1) - a(n-2) + 1 with n>=1, a(-1)=0, a(0)=0.

a(n) = Sum_{k=1..n} F(k)*L(k), where L(k) = Lucas(k) = A000032(k) = F(k-1) + F(k+1). - Alexander Adamchuk, May 18 2007

a(n) = 2*a(n-1) + (Sum_{k=1..n-2} a(k)) + n. - Jon Perry, Sep 01 2012

Sum {n >= 1} 1/a(n) = 3 - phi, where phi = 1/2*(1 + sqrt(5)) is the golden ratio. The ratio of adjacent terms r(n) := a(n)/a(n-1) satisfies the recurrence r(n+1) = (4*r(n) - 1)/(r(n) + 1) for n >= 2. - Peter Bala, Dec 05 2013

a(n) = S(n, 3) - S(n-1, 3) - 1, n >= 0, with Chebyshev's S-polynomials (see A049310), where S(-1, x) = 0. - Wolfdieter Lang, Aug 28 2014

a(n) = -1 + (2^(-1-n)*((3-sqrt(5))^n*(-1+sqrt(5)) + (1+sqrt(5))*(3+sqrt(5))^n)) / sqrt(5). - Colin Barker, Jun 03 2016

E.g.f.: (sqrt(5)*sinh(sqrt(5)*x/2) + 5*cosh(sqrt(5)*x/2))*exp(3*x/2)/5 - exp(x). - Ilya Gutkovskiy, Jun 03 2016

a(n) = Sum_{k=0..n} binomial(n+1,k+1)*Fibonacci(k). - Vladimir Kruchinin, Oct 14 2016

a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i+1,k-i). - Wesley Ivan Hurt, Sep 21 2017

a(n)*a(n-2) = a(n-1)*(a(n-1) - 1) for n>1. - Robert K. Moniot, Aug 23 2020

a(n) = Sum_{k=1..n} C(2*n-k,k). - Wesley Ivan Hurt, Dec 22 2020

a(n) = Sum_{k = 1..2*n+2} (-1)^k*Fibonacci(k). - Peter Bala, Nov 14 2021

a(n) = (2*cosh((1 + 2*n)*arccsch(2)))/sqrt(5) - 1. - Peter Luschny, Nov 21 2021

a(n) = F(n + (n mod 2)) * L(n+1 - (n mod 2)), where L(n) = A000032(n) and F(n) = A000045(n) (Euler and Sadek, 2001). - Amiram Eldar, Jan 13 2022

Extensions

More terms from James Sellers, Sep 08 2000

Paul Barry's Nov 14 2003 formula, recurrences and g.f. corrected for offset 0 and index link for Chebyshev polynomials added by Wolfdieter Lang, Aug 28 2014