login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001629 Fibonacci numbers convolved with themselves.
(Formerly M1377 N0537)
59
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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) = 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))*diff(S(n,x),x)|_{x=I}, n>=1. First derivative of Chebyshev S-polynomials evaluated at x=I (imaginary unit) multiplied by (-I)^(n-1). See A049310 for the S-polynomials. - Wolfdieter Lang, Apr 04 2007

For n>=4, a(n)=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

a(n) = A214178(n,1) for n > 0. - Reinhard Zumkeller, Jul 08 2012

For n > 0: a(n) = sum(A039913(n-1,k): k=1..n-1) / 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)=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

REFERENCES

Thomas Koshy, Fibonacci and Lucas Numbers with Applications, 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

T. D. Noe, Table of n, a(n) for n = 0..500

Marco Abrate, Stefano Barbero, Umberto Cerruti, Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794

Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, Marko Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, arXiv:1407.4962 [math.CO], 2014. See Table 2.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

E. S. Egge, Restricted 3412-Avoiding Involutions, p. 16, arXiv:math/0307050 [math.CO], 2003.

Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792, 2012.

N. Gauthier (Proposer), Problem H-703, Fib. Quart., 50 (2012), 379-381.

V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Fibonacci convolution sequences, Fib. Quart., 15 (1977), 117-122.

S. Klavzar, On median nature and enumerative properties of Fibonacci-like cubes, Disc. Math. 299 (2005), 145-153. - R. J. Mathar, Nov 05 2008

S. Klavzar, Structure of Fibonacci cubes: a survey, Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094. (See Section 4.)

T. Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.

P. Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.

Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Index entries for sequences related to linear recurrences with constant coefficients, signature (2,1,-2,-1)

FORMULA

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

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

a(n) = sum(F(k)*F(n-k)), k=0..n where F(k)=A000045(k) (the Fibonacci sequence).

a(n+1) = sum(A007895(i), 0 <= i <= F(n)), where F = A000045, the Fibonacci sequence. - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001

a(n) = sum((k+1)*binomial(n-k-1, k+1), k=0..floor(n/2)-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) = sum of (n-1)-th row terms of triangle A134510; e.g., a(6) = 20 = (8 + 5 + 5 + 1 + 1). - Gary W. Adamson, Oct 28 2007

Starting (1, 2, 5, 10, 20, 38,...), = row sums of triangle A134836. - Gary W. Adamson, Nov 12 2007

a(n) = term (1,3) in the 4x4 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) = ((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.

MAPLE

A001629:=1/(z**2+z-1)**2; # [Conjectured by Simon Plouffe in his 1992 dissertation.]

a:= n-> (Matrix(4, (i, j)-> if (i=j-1) then 1 elif j=1 then [2, 1, -2, -1][i] else 0 fi)^n)[1, 3]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008

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 + 1)))* 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 *)

PROG

(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

(PARI) Vec(1/(1-x-x^2)^2+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014

(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

CROSSREFS

a(n)= A037027(n-1, 1), n >= 1, (Fibonacci convolution triangle). Cf. A000045, A001628, A010049, A055244, A134510, A134836.

Row sums of triangle A058071, first differences of A006478.

Sequence in context: A227356 A102688 A236559 * A159230 A181366 A068034

Adjacent sequences:  A001626 A001627 A001628 * A001630 A001631 A001632

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

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

Last modified November 27 11:59 EST 2014. Contains 250196 sequences.