login
a(n) = 3^n - 2.
28

%I #69 Apr 28 2023 22:35:21

%S 1,7,25,79,241,727,2185,6559,19681,59047,177145,531439,1594321,

%T 4782967,14348905,43046719,129140161,387420487,1162261465,3486784399,

%U 10460353201,31381059607,94143178825,282429536479,847288609441

%N a(n) = 3^n - 2.

%C a(n) = number of 2 X n binary matrices with no zero rows or columns.

%C a(n)^2 + 2*a(n+1) + 1 is a square number, i.e., a(n)^2 + 2*a(n+1) + 1 = (a(n)+3)^2: for n=2, a(2)^2 + 2*a(3) + 1 = 7^2 + 2*25 + 1 = 100 = (7+3)^2; for n=3, a(3)^2 + 2*a(4) + 1 = 25^2 + 2*79 + 1 = 784 = (25+3)^2. - _Bruno Berselli_, Apr 23 2010

%C Sum of n-th row of triangle of powers of 3: 1; 3 1 3; 9 3 1 3 9; 27 9 3 1 3 9 27; ... . - _Philippe Deléham_, Feb 24 2014

%C a(n) = least k such that k*3^n + 1 is a square. Thus, the square is given by (3^n-1)^2. - _Derek Orr_, Mar 23 2014

%C Binomial transform of A058481: (1, 6, 12, 24, 48, 96, ...) and second binomial transform of (1, 5, 1, 5, 1, 5, ...). - _Gary W. Adamson_, Aug 24 2016

%C Number of ordered pairs of nonempty sets whose union is [n]. a(2) = 7: ({1,2},{1,2}), ({1,2},{1}), ({1,2},{2}), ({1},{1,2}), ({1},{2}), ({2},{1,2}), ({2},{1}). If "nonempty" is omitted we get A000244. - _Manfred Boergens_, Mar 29 2023

%H G. C. Greubel, <a href="/A058481/b058481.txt">Table of n, a(n) for n = 1..1000</a>

%H John Elias, <a href="/A058481/a058481.png">Illustration: Union of Triple-Sierpinski Triangles</a>

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

%F Number of m X n binary matrices with no zero rows or columns is Sum_{j=0..m} (-1)^j*C(m, j)*(2^(m-j)-1)^n.

%F From _Mohammad K. Azarian_, Jan 14 2009: (Start)

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

%F E.g.f.: e^(3*x)-2*(e^x)+1. (End)

%F a(n) = 3*a(n-1) + 4 (with a(1)=1). - _Vincenzo Librandi_, Aug 07 2010

%F a(n) = 4*a(n-1) - 3*a(n-2). - _G. C. Greubel_, Aug 25 2016

%e G.f. = x + 7*x^2 + 25*x^3 + 79*x^4 + 241*x^5 + 727*x^6 + 2185*x^7 + 6559*x^8 + ...

%e a(1) = 1;

%e a(2) = 3 + 1 + 3 = 7;

%e a(3) = 9 + 3 + 1 + 3 + 9 = 25;

%e a(4) = 27 + 9 + 3 + 1 + 3 + 9 + 27 = 79; etc. - _Philippe Deléham_, Feb 24 2014

%p A058481:=n->3^n-2; seq(A058481(n), n=1..30); # _Wesley Ivan Hurt_, Mar 24 2014

%t a=1;lst={a};Do[a=a*3+4;AppendTo[lst,a],{n,0,5!}];lst (* _Vladimir Joseph Stephan Orlovsky_, Dec 25 2008 *)

%t 3^Range[30]-2 (* _Harvey P. Dale_, Mar 28 2011 *)

%t LinearRecurrence[{4, -3}, {1, 7}, 25] (* _G. C. Greubel_, Aug 25 2016 *)

%o (PARI) a(n)=3^n-2 \\ _Charles R Greathouse IV_, Feb 06 2017

%o (PARI) {a(n) = if( n<1, 0, 3^n - 2)}; /* _Michael Somos_, Feb 17 2017 */

%Y Cf. A055602, A024206 (unlabeled case), A055609, A058482, A000244.

%Y Cf. A003462, A007051, A034472, A024023, A067771, A029858, A134931, A115099, A100774, A079004.

%K easy,nonn,nice

%O 1,2

%A _Vladeta Jovovic_, Nov 26 2000

%E More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000