login
Number of monomials in c(n) where c(1) = x, c(2) = y, c(n+2) = c(n+1) + c(n)^2.
1

%I #23 May 10 2020 09:18:06

%S 1,1,2,3,5,8,14,24,44,80,152,288,560,1088,2144,4224,8384,16640,33152,

%T 66048,131840,263168,525824,1050624,2100224,4198400,8394752,16785408,

%U 33566720,67125248,134242304,268468224,536920064,1073807360,2147581952,4295098368

%N Number of monomials in c(n) where c(1) = x, c(2) = y, c(n+2) = c(n+1) + c(n)^2.

%H Colin Barker, <a href="/A290075/b290075.txt">Table of n, a(n) for n = 1..1000</a>

%H Kai Williams, <a href="http://math.stackexchange.com/questions/2363374">Number of monomials in a_n = a_{n-1} + (a_{n-2})^2 with a_1 = a, a_2 = b</a>, Math StackExchange question 2363374, Jul 18 2017.

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

%F G.f.: (x - x^2 - 2*x^3 + x^4 - x^5) / ((1 - 2*x) * (1 - 2*x^2)).

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

%F A088966(n) = a(2*n+2). A257273(n) = a(2*n+3). A211525(n) = a(n+8).

%F From _Colin Barker_, Jul 22 2017: (Start)

%F a(n) = 2^(n/2-1) + 2^(n-4) for n>2 and even.

%F a(n) = 3*2^((n-5)/2) + 2^(n-4) for n>2 and odd.

%F (End)

%F Given the sequence c(n, x, y), then the coefficients of: (1) c(n+2, sqrt(t), 0), (2) c(n+1, 0, t), and (3) c(n, t, t), each form the triangular sequence A103484. - _Michael Somos_, Jul 24 2017

%e G.f. = x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 8*x^6 + 14*x^7 + 24*x^8 + 44*x^9 + ...

%e c(3) = x^2 + y so a(3) = 2, c(4) = x^2 + (y + y^2) so a(4) = 3, c(5) = x^4 + x^2(2*y) + (y + 2*y^2) so a(5) = 5.

%t nn:=36; nn:=10; Rest[CoefficientList[Series[(x - x^2 - 2*x^3 + x^4 - x^5) / ((1 - 2*x) * (1 - 2*x^2)),{x, 0, nn}], x]] (* _Georg Fischer_, May 10 2020 *)

%o (PARI) {a(n) = if( n<3, n>0, my(e=n%2, m=2^((n+e)/2-2)); m * (m+2+e) / (1+e))};

%o (PARI) Vec(x*(1 - x - 2*x^2 + x^3 - x^4) / ((1 - 2*x)*(1 - 2*x^2)) + O(x^50)) \\ _Colin Barker_, Jul 22 2017

%Y Cf. A088966, A103484, A211525, A257273.

%K nonn,easy

%O 1,3

%A _Michael Somos_, Jul 19 2017