cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A001629 Self-convolution of Fibonacci numbers.

Original entry on oeis.org

0, 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, 420, 744, 1308, 2285, 3970, 6865, 11822, 20284, 34690, 59155, 100610, 170711, 289032, 488400, 823800, 1387225, 2332418, 3916061, 6566290, 10996580, 18394910, 30737759, 51310978, 85573315, 142587180, 237387960, 394905492
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of elements in all subsets of {1,2,...,n-1} with no consecutive integers. Example: a(5)=10 because the subsets of {1,2,3,4} that have no consecutive elements, i.e., {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, the total number of elements is 10. - Emeric Deutsch, Dec 10 2003
If g is either of the real solutions to x^2-x-1=0, g'=1-g is the other one and phi is any 2 X 2-matricial solution to the same equation, not of the form gI or g'I, then Sum'_{i+j=n-1} g^i phi^j = F_n + (A001629(n) - A001629(n-1)g')*(phi-g'I), where i,j >= 0, F_n is the n-th Fibonacci number and I is the 2 X 2 identity matrix... - Michele Dondi (blazar(AT)lcm.mi.infn.it), Apr 06 2004
Number of 3412-avoiding involutions containing exactly one subsequence of type 321.
Number of binary sequences of length n with exactly one pair of consecutive 1's. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 02 2004
For this sequence the n-th term is given by (nF(n+1)-F(n)+nF(n-1))/5 where F(n) is the n-th Fibonacci number. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), Apr 20 2005
If an unbiased coin is tossed n times then there are 2^n possible strings of H and T. Out of these, number of strings with exactly one 'HH' is given by a(n) where a(n) denotes n-th term of this sequence. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), May 04 2005
a(n) is half the number of horizontal dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; a(n+1) = the number of vertical dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; thus 2*a(n)+a(n+1)=n*F(n+1) = the number of dominoes in all domino tilings of a 2 X n rectangle, where F=A000045, the Fibonacci sequence. - Roberto Tauraso, May 02 2005; Graeme McRae, Jun 02 2006
a(n+1) = (-i)^(n-1)*(d/dx)S(n,x)|A049310%20for%20the%20S-polynomials.%20-%20_Wolfdieter%20Lang">{x=i}, where i is the imaginary unit, n >= 1. First derivative of Chebyshev S-polynomials evaluated at x=i multiplied by (-i)^(n-1). See A049310 for the S-polynomials. - _Wolfdieter Lang, Apr 04 2007
For n >= 4, a(n) is the number of weak compositions of n-2 in which exactly one part is 0 and all other parts are either 1 or 2. - Milan Janjic, Jun 28 2010
For n greater than 1, a(n) equals the absolute value of (1 - (1/2 - i/2)*(1 + (-1)^(n + 1))) times the x-coefficient of the characteristic polynomial of the (n-1) X (n-1) tridiagonal matrix with i's along the main diagonal (i is the imaginary unit), 1's along the superdiagonal and the subdiagonal and 0's everywhere else (see Mathematica code below). - John M. Campbell, Jun 23 2011
For n > 0: a(n) = Sum_{k=1..n-1} (A039913(n-1,k)) / 2. - Reinhard Zumkeller, Oct 07 2012
The right-hand side of a binomial-coefficient identity [Gauthier]. - N. J. A. Sloane, Apr 09 2013
a(n) is the number of edges in the Fibonacci cube Gamma(n-1) (see the Klavzar 2005 reference, p. 149). Example: a(3)=2; indeed, the Fibonacci cube Gamma(2) is the path P(3) having 2 edges. - Emeric Deutsch, Aug 10 2014
a(n) is the number of c(i)'s, including repetitions, in p(n), where p(n)/q(n) is the n-th convergent p(n)/q(n) of the formal infinite continued fraction [c(0), c(1), ...]; e.g., the number of c(i)'s in p(3) = c(0)*c(1)*c(2)*c(3) + c(0)*c(1) + c(0)*c(3) + c(2)*c(3) + 1 is a(5) = 10. - Clark Kimberling, Dec 23 2015
Also the number of maximal and maximum cliques in the (n-1)-Fibonacci cube graph. - Eric W. Weisstein, Sep 07 2017
a(n+1) is the total number of fixed points in all permutations p on 1, 2, ..., n such that |k-p(k)| <= 1 for 1 <= k <= n. - Katharine Ahrens, Sep 03 2019
From Steven Finch, Mar 22 2020: (Start)
a(n+1) is the total binary weight (cf. A000120) of all A000045(n+2) binary sequences of length n not containing any adjacent 1's.
The only three 2-bitstrings without adjacent 1's are 00, 01 and 10. The bitsums of these are 0, 1 and 1. Adding these give a(3)=2.
The only five 3-bitstrings without adjacent 1's are 000, 001, 010, 100 and 101. The bitsums of these are 0, 1, 1, 1 and 2. Adding these give a(4)=5.
The only eight 4-bitstrings without adjacent 1's are 0000, 0001, 0010, 0100, 1000, 0101, 1010 and 1001. The bitsums of these are 0, 1, 1, 1, 1, 2, 2, and 2. Adding these give a(5)=10. (End)
Number of tilings of a 1 X n strip with monominoes (1 X 1 squares) and at least one domino (1 X 2 rectangles), where exactly one of the dominoes is colored gold. - Greg Dresden and Jiachen Weng, Jul 31 2025

Examples

			G.f. = x^2 + 2*x^3 + 5*x^4 + 10*x^5 + 20*x^6 + 38*x^7 + 71*x^8 + 130*x^9 + ... - _Michael Somos_, Jun 24 2018

References

  • Donald E. Knuth, Fundamental Algorithms, Addison-Wesley, 1968, p. 83, Eq. 1.2.8--(17). - Don Knuth, Feb 26 2019
  • Thomas Koshy, Fibonacci and Lucas Numbers with Applications, 2001, Chapter 15, page 187, "Hosoya's Triangle", and p. 375, eq. (32.13).
  • J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
  • 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).
  • S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 183, Nr.(98).

Links

Crossrefs

Row sums of triangles A058071, A134510, A134836.
First differences of A006478.
Cf. A000032, A000045, A001628, A010049, A037027, A055244, A214178.

Programs

  • GAP
    List([0..40],n->Sum([0..n],k->Fibonacci(k)*Fibonacci(n-k))); # Muniru A Asiru, Jun 24 2018
  • Haskell
    a001629 n = a001629_list !! (n-1)
a001629_list = f [] $ tail a000045_list where
   f us (v:vs) = (sum $ zipWith (*) us a000045_list) : f (v:us) vs
-- Reinhard Zumkeller, Jan 18 2014, Oct 16 2011
  • Magma
    I:=[0,0,1,2]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)-2*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Nov 19 2014
  • Maple
    a:= n-> (<<2|1|0|0>, <1|0|1|0>, <-2|0|0|1>, <-1|0|0|0>>^n)[1,3]:
seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008
# Alternative:
A001629 := n -> `if`(n<2, 0, (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4)):
seq(simplify(A001629(n)), n=0..37); # Peter Luschny, Apr 10 2018
  • Mathematica
    Table[Sum[Binomial[n-i, i] i, {i, 0, n}], {n, 0, 34}] (* Geoffrey Critzer, May 04 2009 *)
Table[Abs[(1 -(1/2 -I/2)(1 - (-1)^n))*Coefficient[CharacteristicPolynomial[ Array[KroneckerDelta[#1, #2] I + KroneckerDelta[#1 + 1, #2] + KroneckerDelta[#1 -1, #2] &, {n-1, n-1}], x], x]], {n,2,50}] (* John M. Campbell, Jun 23 2011 *)
LinearRecurrence[{2,1,-2,-1}, {0,0,1,2}, 40] (* Harvey P. Dale, Aug 26 2013 *)
CoefficientList[Series[x^2/(1-x-x^2)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Nov 19 2014 *)
Table[(2nFibonacci[n-1] + (n-1)Fibonacci[n])/5, {n, 0, 40}] (* Vladimir Reshetnikov, May 08 2016 *)
Table[With[{fibs=Fibonacci[Range[n]]},ListConvolve[fibs,fibs]],{n,-1,40}]//Flatten (* Harvey P. Dale, Aug 19 2018 *)
  • PARI
    Vec(1/(1-x-x^2)^2+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014
  • PARI
    a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n)[2,4] \\ Charles R Greathouse IV, Jul 20 2016
  • SageMath
    def A001629(n): return (1/5)*(n*lucas_number2(n, 1, -1) - fibonacci(n))
[A001629(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

Formula

G.f.: x^2/(1 - x - x^2)^2. - Simon Plouffe in his 1992 dissertation
a(n) = A037027(n-1, 1), n >= 1 (Fibonacci convolution triangle).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n > 3.
a(n) = Sum_{k=0..n} A000045(k)*A000045(n-k).
a(n+1) = Sum_{i=0..F(n)} A007895(i), where F = A000045, the Fibonacci sequence. - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001
a(n) = Sum_{k=0..floor(n/2)-1} (k+1)*binomial(n-k-1, k+1). - Emeric Deutsch, Nov 15 2001
a(n) = floor( (1/5)*(n - 1/sqrt(5))*phi^n + 1/2 ) where phi=(1+sqrt(5))/2 is the golden ratio. - Benoit Cloitre, Jan 05 2003
a(n) = a(n-1) + A010049(n-1) for n > 0. - Emeric Deutsch, Dec 10 2003
a(n) = Sum_{k=0..floor((n-2)/2)} (n-k-1)*binomial(n-k-2, k). - Paul Barry, Jan 25 2005
a(n) = ((n-1)*F(n) + 2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda and Koshy reference).
F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated at 1. - T. D. Noe, Jan 18 2006
a(n) = a(n-1) + a(n-2) + F(n-1), where F=A000045, the Fibonacci sequence. - Graeme McRae, Jun 02 2006
a(n) = (1/5)*(n-1/sqrt(5))*((1+sqrt(5))/2)^n + (1/5)*(n+1/sqrt(5))*((1-sqrt(5))/2)^n. - Graeme McRae, Jun 02 2006
a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) = (23 - 3). - Gary W. Adamson, Jul 27 2007
a(n) = term (1,3) in the 4 X 4 matrix [2,1,0,0; 1,0,1,0; -2,0,0,1; -1,0,0,0]^n. - Alois P. Heinz, Aug 01 2008
a(n) = A214178(n,1) for n > 0. - Reinhard Zumkeller, Jul 08 2012
a(n) = ((n+1)*F(n-1) + (n-1)*F(n+1))/5. - Richard R. Forberg, Aug 04 2014
(n-2)*a(n) - (n-1)*a(n-1) - n*a(n-2) = 0, n > 1. - Michael D. Weiner, Nov 18 2014
a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j), where F(n) = A000045 Fibonacci Numbers. - Carlos A. Rico A., Jul 14 2016
a(n) = (n*Lucas(n) - Fibonacci(n))/5, where Lucas = A000032, Fibonacci = A000045. - Vladimir Reshetnikov, Sep 27 2016
a(n) = (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4) for n >= 2. - Peter Luschny, Apr 10 2018
a(n) = -(-1)^n a(-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/50)*exp(-2*x/(1+sqrt(5)))*(2*sqrt(5)-5*(-1+sqrt(5))*x+exp(sqrt(5)*x)*(-2*sqrt(5)+5*(1+sqrt(5))*x)). - Stefano Spezia, Sep 03 2019
From Peter Bala, Jan 14 2025: (Start)
a(2*n+1) is even and a(2*n) has the same parity as Fibonacci(n).
For n >= 1, a(n) = (2/n)*Sum_{k = 0..n} k*Fibonacci(k)*Fibonacci(n-k). (End)

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.