login
a(n) = 2*a(n-1) + 2*a(n-2) for n > 2, a(0)=1, a(1)=1, a(2)=3.
15

%I #85 Jul 22 2024 13:48:43

%S 1,1,3,8,22,60,164,448,1224,3344,9136,24960,68192,186304,508992,

%T 1390592,3799168,10379520,28357376,77473792,211662336,578272256,

%U 1579869184,4316282880,11792304128,32217174016,88018956288,240472260608,656982433792,1794909388800,4903783645184,13397386067968

%N a(n) = 2*a(n-1) + 2*a(n-2) for n > 2, a(0)=1, a(1)=1, a(2)=3.

%C Equals 1 followed by A028859. - _Klaus Brockhaus_, Jul 18 2009

%C a(n) is the number of ways to arrange 1- and 2-cent postage stamps (totaling n cents) in a row so that the first stamp is correctly placed and any subsequent stamp may (or not) be placed upside down.

%C Number of compositions of n into parts k >= 1 where there are F(k+1) = A000045(k+1) sorts of part k. - _Joerg Arndt_, Sep 30 2012

%C a(n) is the top-left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 1, 1; 1, 1, 0] or of the 3 X 3 matrix [1, 1, 1; 1, 0, 1; 1, 1, 1].

%C From _Tom Copeland_, Nov 08 2014: (Start)

%C (Setting a(0)=0.)

%C This array is one of a family of Catalan arrays related by compositions of the special fractional linear (Möbius) transformations P(x,t) = x/(1-t*x); its inverse Pinv(x,t) = P(x,-t); and an o.g.f. of the Catalan numbers A000108, C(x) = (1-sqrt(1-4x))/2; and its inverse Cinv(x) = x*(1-x). (Cf. A091867.)

%C O.g.f.: G(x) = -P(P(Cinv(-x),1),1) = -P(Cinv(-x),2) = x(1+x)/(1-2x(1+x)) = (x+x^2)/(1-2(x+x^2)) = x + 3*x^2 + 8*x^3 + ... = A155020(x) with a(0)=0.

%C Ginv(x) = -C(P(P(-x,-1),-1)) = -C(P(-x,-2)) = (-1+sqrt(1+4*x/(1+2x))/2 = x*A064613(-x).

%C G(x) = x*(1+x) + 2*(x*(1+x))^2 + 2^2*(x*(1+x))^3 - ..., and so this array contains the row sums of A030528 * Diag(1, 2^1, 2^2, 2^3, ...). (End)

%C INVERT transform of Fibonacci(n+1). - _Alois P. Heinz_, Feb 11 2021

%H Indranil Ghosh, <a href="/A155020/b155020.txt">Table of n, a(n) for n = 0..2287</a>

%H I. Amburg, K. Dasaratha, L. Flapan, T. Garrity, C. Lee, C. Mihailak, N. Neumann-Chun, S. Peluse, and M. Stoffregen, <a href="http://arxiv.org/abs/1509.05239">Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences</a>, arXiv:1509.05239v1 [math.CO] 17 Sep 2015.

%H Juan B. Gil and Jessica A. Tomasko, <a href="https://arxiv.org/abs/2108.06462">Fibonacci colored compositions and applications</a>, arXiv:2108.06462 [math.CO], 2021.

%H J. Shallit, <a href="https://arxiv.org/abs/2310.14252">Proof of Irvine's conjecture via mechanized guessing</a>, arXiv preprint arXiv:2310.14252 [math.CO], October 22 2023.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,2).

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

%F G.f.: 1/( 1 - Sum_{k>=1} (x+x^2)^k ) - 1/( 1 - Sum_{k>=1} F(k+1)*x^k ) where F(k) = A000045(k). - _Joerg Arndt_, Sep 30 2012

%F a(n+1) = Sum_{k=0..n} A154929(n,k) = A028859(n).

%F a(n) = Sum_{k=0..floor(n/2)} ( binomial(n-k,k)*2^(n-k-1) ) for n > 0. - _Emanuele Munarini_, Feb 04 2014

%F a(n) = (1/2)*[n=0] - (sqrt(2)*i)^(n-2)*ChebyshevU(n, -sqrt(2)*i/2). - _G. C. Greubel_, Mar 25 2021

%F E.g.f.: (3 + exp(x)*(3*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)))/6. - _Stefano Spezia_, Mar 02 2024

%e a(2) = 3 because we have {1,1}, {1,_1} and {2}.

%e a(3) = 8 because we can order the stamps in eight ways: {1,1,1} {1,1,_1} {1,_1,1} {1,_1,_1} {2,1} {2,_1} {1,2} {1,_2}, where _1 and _2 are upside down stamps.

%e a(4) = 22 = 2*3 + 2*8 because we can append 2 or _2 to the a(2) examples and 1 or _1 to the a(3) examples. - _Jon Perry_, Nov 10 2014

%p a:= proc(n) option remember; `if`(n=0, 1,

%p add(a(n-i)*combinat[fibonacci](1+i), i=1..n))

%p end:

%p seq(a(n), n=0..42); # _Alois P. Heinz_, Feb 11 2021

%t CoefficientList[Series[(1 -x -x^2)/(1 -2x -2x^2), {x,0,20}], x]

%t With[{m=2}, LinearRecurrence[{m, m}, {1, m-1, m^2-1}, 30]] (* _G. C. Greubel_, Mar 25 2021 *)

%o (PARI) Vec( (1-x-x^2)/(1-2*x-2*x^2) + O(x^66) ) /* _Joerg Arndt_, Sep 30 2012 */

%o (Maxima) makelist(sum(binomial(n-k,k)*2^(n-k-1),k,0,floor(n/2)),n,1,12); /* _Emanuele Munarini_, Feb 04 2014 */

%o (Magma) I:=[1,1,3,8]; [n le 4 select I[n] else 2*Self(n-1)+2*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Nov 10 2014

%o (Sage) [1]+[(-1)*(sqrt(2)*i)^(n-2)*chebyshev_U(n, -sqrt(2)*i/2) for n in (1..30)] # _G. C. Greubel_, Mar 25 2021

%Y Sequences of the form a(n) = m*(a(n-1) + a(n-2)) with a(0)=1, a(1) = m-1, a(2) = m^2 -1: this sequence (m=2), A155116 (m=3), A155117 (m=4), A155119 (m=5), A155127 (m=6), A155130 (m=7), A155132 (m=8), A155144 (m=9), A155157 (m=10).

%Y Cf. A028859 (essentially the same sequence). - _Klaus Brockhaus_, Jul 18 2009

%Y Cf. A000045, A000108, A030528, A064613, A091867, A154929.

%Y Row sums of A155112.

%K nonn,easy

%O 0,3

%A _Philippe Deléham_, Jan 19 2009