%I A001629 M1377 N0537
%S A001629 0,0,1,2,5,10,20,38,71,130,235,420,744,1308,2285,3970,6865,11822,20284,
%T A001629 34690,59155,100610,170711,289032,488400,823800,1387225,2332418,
%U A001629 3916061,6566290,10996580,18394910,30737759,51310978,85573315
%N A001629 Fibonacci numbers convolved with themselves.
%C A001629 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 (deutsch(AT)duke.poly.edu), 
               Dec 10 2003
%C A001629 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
%C A001629 Number of 3412-avoiding involutions containing exactly one subsequence 
               of type 321.
%C A001629 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
%C A001629 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
%C A001629 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
%C A001629 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 (tauraso(AT)mat.uniroma2.it), May 02 2005; Graeme 
               McRae (g_m(AT)mcraefamily.com), Jun 02 2006
%C A001629 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. W. Lang, Apr 04 
               2007.
%D A001629 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A001629 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A001629 S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques 
               Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%D A001629 V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Fibonacci convolution sequences, 
               Fib. Quart., 15 (1977), 117-122.
%D A001629 Thomas Koshy, Fibonacci and Lucas Numbers with Applications, Chapter 
               15, page 187, "Hosoya's Triangle"
%D A001629 J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
%D A001629 S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood 
               Ltd., Chichester, 1989, p. 183, Nr.(98).
%H A001629 T. D. Noe, <a href="b001629.txt">Table of n, a(n) for n=0..500</a>
%H A001629 <a href="Sindx_Rea.html#recLCC">Index entries for sequences related to 
               linear recurrences with constant coefficients</a>
%H A001629 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">
               Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</
               a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%H A001629 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">
               1031 Generating Functions and Conjectures</a>, Universit\'{e} du 
               Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H A001629 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               Sequences realized by oligomorphic permutation groups</a>, J. Integ. 
               Seqs. Vol. 3 (2000), #00.1.5.
%H A001629 E. S. Egge, <a href="http://arXiv.org/abs/math.CO/0307050">Restricted 
               3412-Avoiding Involutions</a>, p. 16.
%H A001629 T. Mansour, <a href="http://arXiv.org/abs/math.CO/0301157">Generalization 
               of some identities involving the Fibonacci numbers</a>
%H A001629 P. Moree, <a href="http://arXiv.org/abs/math.CO/0311205">Convoluted convolved 
               Fibonacci numbers</a>
%H A001629 Pieter Moree, <a href="http://www.cs.uwaterloo.ca/journals/JIS/">Convoluted 
               Convolved Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 
               7 (2004), Article 04.2.2.
%H A001629 S. Klavzar, <a href="http://dx.doi.org/10.1016/j.disc.2004.02.023">On 
               median nature and enumerative properties of Fibonacci-like cubes</
               a>, Disc. Math. 299 (2005), 145-153. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), 
               Nov 05 2008]
%F A001629 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=A000045 (the Fibonacci sequence).
%F A001629 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
%F A001629 a(n)=sum((k+1)*binomial(n-k-1, k+1), k=0..floor(n/2)-1). - Emeric Deutsch 
               (deutsch(AT)duke.poly.edu), Nov 15 2001
%F A001629 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 (benoit7848c(AT)orange.fr), 
               Jan 05 2003
%F A001629 a(n)=a(n-1)+A010049(n-1) for n>0. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Dec 10 2003
%F A001629 a(n)=sum{k=0..floor((n-2)/2), (n-k-1)binomial(n-k-2, k)} - Paul Barry 
               (pbarry(AT)wit.ie), Jan 25 2005
%F A001629 a(n)= ((n-1)*F(n)+2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda reference)
%F A001629 F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated 
               at 1. - T. D. Noe (noe(AT)sspectra.com), Jan 18 2006
%F A001629 a(n)=a(n-1)+a(n-2)+F(n-1), where F=A000045, the Fibonacci sequence. - 
               Graeme McRae (g_m(AT)mcraefamily.com), Jun 02 2006
%F A001629 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 (g_m(AT)mcraefamily.com), Jun 02 2006
%F A001629 a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) 
               = (23 - 3). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 27 2007
%F A001629 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 (qntmpkt(AT)yahoo.com), 
               Oct 28 2007
%F A001629 Starting (1, 2, 5, 10, 20, 38,...), = row sums of triangle A134836. - 
               Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 12 2007
%F A001629 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. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 01 2008]
%e A001629 sage: taylor( mul((x^2)/(1-x^2-x^4) for i in xrange(0,2)),x,0,69)#solution>
               > x^4 + 2*x^6 + 5*x^8 + 10*x^10 + 20*x^12 + 38*x^14 + 71*x^16 + 130*x^18 
               + 235*x^20 + 420*x^22 + 744*x^24 + 1308*x^26 + 2285*x^28 + 3970*x^30 
               + 6865*x^32 + 11822*x^34 + 20284*x^36 + etc... [From Zerinvary Lajos 
               (zerinvarylajos(AT)yahoo.com), Jun 01 2009]
%p A001629 A001629:=1/(z**2+z-1)**2; [Conjectured by S. Plouffe in his 1992 dissertation.]
%p A001629 (Maple) 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..34); [From 
               Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 01 2008]
%t A001629 Table[Sum[Binomial[n - i, i]*i, {i, 0, n}], {n, 0, 34}] [From Geoffrey 
               Critzer (critzer.geoffrey(AT)usd443.org), May 04 2009]
%o A001629 (Other) sage: taylor( mul((x^2)/(1-x^2-x^4) for i in xrange(0,2)),x,0,
               69)# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 01 
               2009]
%Y A001629 a(n)= A037027(n-1, 1), n >= 1, (Fibonacci convolution triangle). Cf. 
               A000045, A001628.
%Y A001629 Row sums of triangle A058071.
%Y A001629 Cf. A010049.
%Y A001629 First differences of A006478.
%Y A001629 Cf. A055244.
%Y A001629 Cf. A134510.
%Y A001629 Cf. A134836.
%Y A001629 Sequence in context: A000712 A032442 A102688 this_sequence A159230 A068034 
               A084215
%Y A001629 Adjacent sequences: A001626 A001627 A001628 this_sequence A001630 A001631 
               A001632
%K A001629 nonn,easy,nice
%O A001629 0,4
%A A001629 N. J. A. Sloane (njas(AT)research.att.com).