cp's OEIS Frontend

A007483 a(n) = 3*a(n-1) + 2*a(n-2), with a(0)=1, a(1)=5.

%I A007483 M3875 #94 Jan 05 2025 19:51:34
%S A007483 1,5,17,61,217,773,2753,9805,34921,124373,442961,1577629,5618809,
%T A007483 20011685,71272673,253841389,904069513,3219891317,11467812977,
%U A007483 40843221565,145465290649,518082315077,1845177526529,6571697209741,23405446682281,83359734466325,296890096763537
%N A007483 a(n) = 3*a(n-1) + 2*a(n-2), with a(0)=1, a(1)=5.
%C A007483 Number of subsequences of [1,...,2n+1] in which each odd number has an even neighbor. The even neighbor must differ from the odd number by exactly 1.
%C A007483 From _Gary W. Adamson_, Aug 06 2016: (Start)
%C A007483 a(n) is the upper left term in the (n+1)-th matrix power of [(1,4); (1,2)] and is the INVERT transform of (1, 4, 4*2, 4*2^2, 4*2^3, 4*2^4, ...), i.e. of (1, 4, 8, 16, 32, 64, 128, ...).
%C A007483 The sequence is equal to row sums of an eigentriangle generated as follows: Let matrix A = an infinite lower triangle with (1, 4, 8, 16, ...) in every column and B = a triangle with (1, 1, 5, 17, 61, ...) as the rightmost diagonal and the rest zeros. Then the eigentriangle is A * B as follows: (1; 4, 1; 8, 4, 5; 16, 8, 20, 17; ...) with sums (1, 5, 17, 61, ...). Individual rows can be recovered by taking the dot product of (1, 4, 8, 16, ...) reversed and equal numbers of terms of(1, 1, 5, 17, ...). For example, 61 = (16, 8, 4, 1) dot (1, 1, 5, 17) = (16 + 8 + 20 + 17). (End)
%C A007483 The sequence is equal to A007482 convolved with (1, 2, 0, 0, 0, ...); i.e. (1 + 5x + 17x^2 + ...) = (1 + 3x + 11x^2 + 39x^3 + ...) * (1 + 2x). - _Gary W. Adamson_, Aug 08 2016
%C A007483 a(n) is the number of edge covers of the fan graph F(1,n+1) with a pendant attached to the vertex of degree n+1. - _Feryal Alayont_, Dec 08 2023
%D A007483 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007483 Vincenzo Librandi, <a href="/A007483/b007483.txt">Table of n, a(n) for n = 0..500</a>
%H A007483 C. Bautista-Ramos and C. Guillen-Galvan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Bautista/bautista4.html">Fibonacci numbers of generalized Zykov sums</a>, J. Integer Seq., 15 (2012), Article 12.7.8.
%H A007483 A. Burstein, S. Kitaev, and T. Mansour, <a href="https://arxiv.org/abs/math/0310379">Independent sets in certain classes of (almost) regular graphs</a>, arXiv:math/0310379 [math.CO], 2003.
%H A007483 Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.04249">Odd-Rule Cellular Automata on the Square Grid</a>, arXiv:1503.04249 [math.CO], 2015.
%H A007483 R. K. Guy and William O. J. Moser, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/34-2/guy.pdf">Numbers of subsequences without isolated odd members</a>, Fibonacci Quarterly, 34, No. 2, 152-155 (1996). Math. Rev. 97d:11017.
%H A007483 N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.
%H A007483 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,2).
%F A007483 G.f.: (1 + 2*x)/(1 - 3*x - 2*x^2).
%F A007483 a(n) = ((17 + 7*sqrt(17))/34)*((3 + sqrt(17))/2)^n* + ((17 - 7*sqrt(17))/34)*((3 - sqrt(17))/2)^n. - _Paul Barry_, Dec 08 2004
%F A007483 a(n-1) = Sum_{k=0..n} 2^(n-k)*A122542(n,k), n>=1. - _Philippe Deléham_, Oct 08 2006
%F A007483 a(n) = upper left term in the 2 X 2 matrix [1,2; 2,2]^(n+1). Also [a(n), a(n+1)] = the 2 X 2 matrix [0,1; 2,3]^(n+1) * [1,1]. Example: [0,1; 2,3]^4 * [1,1] = [61, 217]. - _Gary W. Adamson_, Mar 16 2008
%F A007483 Also, for n>=2, a(n)=[1,2;2,2]^(n-1)*[1,2]*[1,2]. - _John M. Campbell_, Jul 09 2011
%F A007483 a(n) = A007482(n) + 2*A007482(n-1). - _R. J. Mathar_, Sep 21 2012
%F A007483 a(n) = (i*sqrt(2))^(n-1)*( i*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) + 2*ChebyshevU(n-1, -3*i/(2*sqrt(2))) ). - _G. C. Greubel_, Jun 28 2021
%F A007483 E.g.f.: exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 7*sqrt(17)*sinh(sqrt(17)*x/2))/17. - _Stefano Spezia_, May 24 2024
%e A007483 a(2) = 17 = (8, 4, 1) dot (1, 1, 5) = 8 + 4 + 5. - _Gary W. Adamson_, Aug 06 2016
%e A007483 From _Feryal Alayont_, Dec 08 2023: (Start)
%e A007483 a(2) counts the edge covers of F(1,3) with a pendant attached at the vertex of degree 3. This is the graph:
%e A007483       * -- *
%e A007483     / | \
%e A007483    /  |  \
%e A007483   *---*---*
%e A007483 An edge cover is a subset of the edges where each vertex is an endpoint of at least one edge. We show a one-to-one correspondence between subsequences of [1,...,5] and edge covers. Label edges connecting the top left vertex to the bottom vertices with odd numbers, 1, 3, 5, left to right. Label bottom edges with 2 (left) and 4 (right). An odd number in the subsequence means that edge is not in the edge cover. An even number means that edge is in. All bottom vertices are covered because if an odd edge is missing, an even edge covers the vertex attached to that odd. The pendant edge must be in every cover, so that edge covers both top vertices. (End)
%t A007483 LinearRecurrence[{3, 2}, {1, 5}, 24] (* _Jean-François Alcover_, Sep 26 2017 *)
%t A007483 a[0]=1;a[1]=5;a[n_]:= a[n]= 3*a[n-1]+2*a[n-2];Table[a[n],{n,0,23}] (* _James C. McMahon_, Dec 17 2023 *)
%o A007483 (Magma) [Floor((3/2+Sqrt(17)/2)^n*(1/2+7*Sqrt(17)/34)+(1/2-7*Sqrt(17)/34)*(3/2-Sqrt(17)/2)^n)+1: n in [0..30]]; // _Vincenzo Librandi_, Jul 09 2011
%o A007483 (PARI) a(n)=([1,2;2,2]^n*[1,2]~*[1,2])[1,1] \\ _Charles R Greathouse IV_, Jul 10 2011
%o A007483 (Haskell)
%o A007483 a007483 n = a007483_list !! n
%o A007483 a007483_list = 1 : 5 : zipWith (+)
%o A007483                (map (* 3) $ tail a007483_list) (map (* 2) a007483_list)
%o A007483 -- _Reinhard Zumkeller_, Nov 02 2015
%o A007483 (Sage)
%o A007483 @CachedFunction
%o A007483 def a(n): return 5^n if (n<2) else 3*a(n-1) + 2*a(n-2)
%o A007483 [a(n) for n in (0..40)] # _G. C. Greubel_, Jun 28 2021
%Y A007483 Cf. A007482, A072272, A122542.
%K A007483 nonn,easy
%O A007483 0,2
%A A007483 _N. J. A. Sloane_, Sep 19 1994
%E A007483 Definition simplified by _N. J. A. Sloane_, Aug 25 2014