|
%I #190 Oct 19 2023 23:14:16
%S 0,1,4,12,33,88,232,609,1596,4180,10945,28656,75024,196417,514228,
%T 1346268,3524577,9227464,24157816,63245985,165580140,433494436,
%U 1134903169,2971215072,7778742048,20365011073,53316291172,139583862444,365435296161,956722026040
%N a(n) = Fibonacci(2*n + 1) - 1.
%C Also T(2n+1,n+1), T given by A027935. Also first row of Inverse Stolarsky array.
%C 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
%C 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
%C 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
%C 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
%C 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)
%C 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
%C 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
%C 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
%C Also, numbers m such that 5*m*(m+2)+1 is a square. - _Bruno Berselli_, May 19 2014
%C 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
%C From _Robert K. Moniot_, Oct 04 2020: (Start)
%C 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).
%C 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)
%D R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., 58:2 (2020), 140-142.
%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 12.
%H T. D. Noe, <a href="/A027941/b027941.txt">Table of n, a(n) for n = 0..200</a>
%H Russ Euler and Jawad Sadek, <a href="https://www.fq.math.ca/Scanned/39-1/elementary39-1.pdf">Problem B-912</a>, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 39, No. 1 (2001), p. 85; <a href="https://www.fq.math.ca/Scanned/39-5/elementary39-5.pdf">From a Product to a Sum</a>, Solution to Problem B-912 by Charles K. Cook, ibid., Vol. 39, No. 5 (2001), pp. 468-469.
%H Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/intersp.html">Interspersions</a>.
%H Clark Kimberling, <a href="http://dx.doi.org/10.1090/S0002-9939-1993-1111434-0">Interspersions and dispersions</a>, Proceedings of the American Mathematical Society, 117 (1993) 313-321.
%H Ioana-Claudia Lazăr, <a href="https://arxiv.org/abs/1904.06555">Lucas sequences in t-uniform simplicial complexes</a>, arXiv:1904.06555 [math.GR], 2019.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 60 (doubled).
%H Luis A. Medina and Armin Straub, <a href="https://doi.org/10.1007/s00026-015-0292-7">On multiple and infinite log-concavity</a>, Annals of Combinatorics, Vol. 20, No. 1 (2016), pp. 125-138; <a href="http://arxiv.org/abs/1405.1765">arXiv preprint</a>, arXiv:1405.1765 [math.CO], 2014; <a href="http://arminstraub.com/downloads/pub/infinitelogconcavity.pdf">preprint</a>, 2014.
%H László Németh, <a href="http://arxiv.org/abs/1511.02067">Hyperbolic Pascal pyramid</a>, arXiv:1511.02067 [math.CO], 2015 (2nd line of Table 1 is 3*a(n-2)).
%H László Németh, <a href="https://arxiv.org/abs/1701.06022">Pascal pyramid in the space H^2×R</a>, arXiv:1701.06022 [math.CO], 2016. See bn in Table 1 p.10.
%H N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials</a>.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,1).
%F a(n) = Sum_{i=1..n} binomial(n+i, n-i). - _Benoit Cloitre_, Oct 15 2002
%F G.f.: Sum_{k>=1} x^k/(1-x)^(2*k+1). - _Benoit Cloitre_, Apr 21 2003
%F a(n) = Sum_{k=1..n} F(2*k), i.e., partial sums of A001906. - _Benoit Cloitre_, Oct 27 2003
%F 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
%F G.f.: x/((1-x)*(1-3*x+x^2)) = x/(1-4*x+4*x^2-x^3).
%F 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.
%F a(n) = 3*a(n-1) - a(n-2) + 1 with n>=1, a(-1)=0, a(0)=0.
%F 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
%F a(n) = 2*a(n-1) + (Sum_{k=1..n-2} a(k)) + n. - _Jon Perry_, Sep 01 2012
%F 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
%F 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
%F 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
%F 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
%F a(n) = Sum_{k=0..n} binomial(n+1,k+1)*Fibonacci(k). - _Vladimir Kruchinin_, Oct 14 2016
%F a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i+1,k-i). - _Wesley Ivan Hurt_, Sep 21 2017
%F a(n)*a(n-2) = a(n-1)*(a(n-1) - 1) for n>1. - _Robert K. Moniot_, Aug 23 2020
%F a(n) = Sum_{k=1..n} C(2*n-k,k). - _Wesley Ivan Hurt_, Dec 22 2020
%F a(n) = Sum_{k = 1..2*n+2} (-1)^k*Fibonacci(k). - _Peter Bala_, Nov 14 2021
%F a(n) = (2*cosh((1 + 2*n)*arccsch(2)))/sqrt(5) - 1. - _Peter Luschny_, Nov 21 2021
%F 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
%e a(5) = 88 = 2*33 + 12 + 4 + 1 + 5. a(6) = 232 = 2*88 + 33 + 12 + 4 + 1 + 6. - _Jon Perry_, Sep 01 2012
%e 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
%p with(combinat): seq(fibonacci(2*n+1)-1,n=1..27); # _Emeric Deutsch_, Dec 19 2004
%p a:=n->sum(binomial(n+k+1,2*k), k=0..n): seq(a(n), n=-1..26); # _Zerinvary Lajos_, Oct 02 2007
%t Table[Fibonacci[2*n+1]-1,{n,0,17}] (* _Vladimir Joseph Stephan Orlovsky_, Jul 21 2008 *)
%t LinearRecurrence[{4,-4,1},{0,1,4},40] (* _Harvey P. Dale_, Aug 17 2021 *)
%o (Magma) [Fibonacci(2*n+1)-1: n in [0..30]]; // _Vincenzo Librandi_, Apr 18 2011
%o (PARI) a(n)=fibonacci(2*n+1)-1 \\ _Charles R Greathouse IV_, Nov 20 2012
%o (PARI) concat(0, Vec(x/((1-x)*(1-3*x+x^2)) + O(x^40))) \\ _Colin Barker_, Jun 03 2016
%o (Haskell)
%o a027941 = (subtract 1) . a000045 . (+ 1) . (* 2)
%o -- _Reinhard Zumkeller_, Mar 10 2013
%o (Maxima)
%o a(n):=sum(binomial(n+1,k+1)*fib(k),k,0,n); /* _Vladimir Kruchinin_, Oct 14 2016 */
%Y Cf. A000045, A035507, A001906, A006318, A000032.
%Y Related to partial sums of Fibonacci(k*n) over n: A000071, A099919, A058038, A138134, A053606; this sequence is the case k=2.
%Y Cf. A212336 for more sequences with g.f. of the type 1/(1 - k*x + k*x^2 - x^3).
%Y Cf. A000225 (sublist connection).
%Y Cf. A258993 (row sums, n > 0), A000967.
%K nonn,easy,nice
%O 0,3
%A _Clark Kimberling_
%E More terms from _James A. Sellers_, Sep 08 2000
%E _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
|
