A080424 -id:A080424 - cp's OEIS frontend

A078008 Expansion of (1 - x)/((1 + x)(1 - 2x)).

1, 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, 87382, 174762, 349526, 699050, 1398102, 2796202, 5592406, 11184810, 22369622, 44739242, 89478486, 178956970, 357913942, 715827882, 1431655766, 2863311530, 5726623062

Offset: 0

N. J. A. Sloane, Nov 17 2002

Conjecture: a(n) = the number of fractions in the infinite Farey row of 2^n terms with even denominators. Compare the Salamin & Gosper item in the Beeler et al. link. - Gary W. Adamson, Oct 27 2003
Counts closed walks starting and ending at the same vertex of a triangle. 3*a(n) = P(C_n, 3) chromatic polynomial for 3 colors on cyclic graph C_n. A078008(n) + 2*A001045(n) = 2^n provides decomposition of Pascal's triangle. - Paul Barry, Nov 17 2003
Permutations with one fixed point avoiding 123 and 132.
General form: iterate k -> 2^n - k. See also A001045. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
The inverse g.f. generates sequence 1, 0, -2, -2, -2, -2, ...
a(n) gives the number of oriented (i.e., unreduced for symmetry) meanders on an (n+2) X 3 rectangular grid; see A201145. - Jon Wild, Nov 22 2011
Pisano period lengths: 1, 1, 6, 1, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, ... - R. J. Mathar, Aug 10 2012
a(n) is the number of length n binary words that end in an odd length run of 0's if we do not include the first letter of the word in our run length count. a(4) =6 because we have 0000, 0010, 0110, 1000, 1010, 1110. - Geoffrey Critzer, Dec 16 2013
a(n) is the top left entry of the n-th power of any of the six 3 X 3 matrices [0, 1, 1; 1, 1, 1; 1, 0, 0], [0, 1, 1; 1, 1, 0; 1, 1, 0], [0, 1, 1; 1, 0, 1; 1, 1, 0], [0, 1, 1; 1, 1, 0; 1, 0, 1], [0, 1, 1; 1, 0, 1; 1, 0, 1] or [0, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 04 2014
a(n) is the number of compositions of n into parts of two kinds without part 1. - Gregory L. Simay, Jun 04 2018
a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is a multiple of three.  a(3) = 2: aba, bab. - Alois P. Heinz, Apr 13 2022
a(n) is the number of words of length n over a ternary alphabet starting with a fixed letter (say, 'a') and ending in a different letter, such that no two adjacent letters are the same. a(4) = 6: abab, abac, abcb, acab, acac, acbc. - Ignat Soroko, Jul 19 2023

			G.f. = 1 + 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + ... - _Michael Somos_, Mar 18 2022

Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 1.1.10a.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms n=0..300 from T. D. Noe)
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015. See Section 4.6.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry and A. Hennessy, Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms , JIS 12 (2009) 09.5.3.
M. Beeler, R. W. Gosper, and R. C. Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972. (Item #54 by Salamin & Gosper)
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
Ernesto Estevez-Rams, Cristy Azanza Ricardo and Beatriz Aragón Fernández, An alternative expression for counting the number of close-packaged polytypes, Z. Krist. 220 (2005) 592-595, eq (4)
Leonhard Euler, Introductio in analysin infinitorum, (1748), section 216.
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 13.
T. Mansour and A. Robertson, Refined Restricted Permutations Avoiding Subsets of Patterns of Length Three, arXiv:math/0204005 [math.CO], 2002.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for linear recurrences with constant coefficients, signature (1,2).
Index entries for sequences related to Chebyshev polynomials.

First differences of A001045.
See A151575 for a signed version.
Bisections: A047849, A020988.
Cf. A151548, A139250, A151555, A153006.

List([0..40], n-> (2^n + 2*(-1)^n)/3); # G. C. Greubel, Jun 28 2019

[(2^n + 2*(-1)^n)/3: n in [0..40]]; // G. C. Greubel, Jun 28 2019

Table[(2^n + 2*(-1)^n)/3, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008; modified by G. C. Greubel, Jun 28 2019 *)
CoefficientList[Series[(1-x)/(1-x-2x^2),{x,0,40}],x]  (* Harvey P. Dale, Mar 30 2011 *)
LinearRecurrence[{1, 2}, {1, 0}, 40] (* Jean-François Alcover, Sep 23 2017 *)

a(n)=(1<Charles R Greathouse IV, Jun 10 2011

def A078008(n): return ((1<Chai Wah Wu, Apr 18 2025

[(2^n + 2*(-1)^n)/3 for n in (0..40)] # G. C. Greubel, Jun 28 2019

Euler expands(1-x)/(1 - x - 2*x^2) into an infinite series and finds that the coefficient of the n-th term is (2^n + (-1)^n 2)/3. Section 226 shows that Euler could have easily found the recursion relation: a(n) = a(n-1) + 2a(n-2) with a(0) = 1 and a(1) = 0. - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006. [Typos corrected by Jaume Oliver Lafont, Jun 01 2009]
a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n)+3*k) where f(n) = (0, 2, 1, 0, 2, 1, ...) = A080424(n). - Paul Barry, Feb 20 2003
E.g.f. (exp(2*x) + 2*exp(-x))/3. - Paul Barry, Apr 20 2003
a(n) = A001045(n) + (-1)^n = A000079(n) - 2*A001045(n). - Paul Barry, Feb 20 2003
a(n) = (2^n + 2*(-1)^n)/3. - Mario Catalani (mario.catalani(AT)unito.it), Aug 29 2003
a(n) = T(n, i/(2*sqrt(2)))*(-i*sqrt(2))^n - U(n-1, i/(2*sqrt(2)))*(-i*sqrt(2))^(n-1)/2. - Paul Barry, Nov 17 2003
From Paul Barry, Jul 30 2004: (Start)
a(n) = 2*a(n-1) + 2*(-1)^n for n > 0, with a(0)=1.
a(n) = Sum_{k=0..n} (-1)^k*(2^(n-k-1) + 0^(n-k)/2). (End)
a(n) = A014113(n-1) for n > 0; a(n) = A052953(n-1) - 2*(n mod 2) = sum of n-th row of the triangle in A108561. - Reinhard Zumkeller, Jun 10 2005
A137208(n+1) - 2*A137208(n) = a(n) signed. - Paul Curtz, Aug 03 2008
a(n) = A001045(n+1) - A001045(n) - Paul Curtz, Feb 09 2009
If p[1] =0, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010
a(n) = 2*(a(n-2) + a(n-3) + a(n-4) ... + a(0)), that is, twice the sum of all the previous terms except the last; with a(0) = 1 and a(1) = 0. - Benoit Jubin, Nov 21 2011
a(n+1) = 2*A001045(n). - Benoit Jubin, Nov 22 2011
G.f.: 1 - x + x*Q(0), where Q(k) = 1 + 2*x^2 + (2*k+3)*x - x*(2*k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013
G.f.: 1+ x^2*Q(0), where Q(k) = 1 + 1/(1 - x*(4*k+1+2*x)/(x*(4*k+3+2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 01 2014
a(n) = 3*a(n-2) + 2*a(n-3). - David Neil McGrath, Sep 10 2014
a(n) = (-1)^n * A151575(n). - G. C. Greubel, Jun 28 2019
a(n)+a(n+1) = 2^n. - R. J. Mathar, Feb 24 2021
a(n) = -a(2-n) * (-2)^(n-1) = (3/2)*(a(n-1) + a(n-2)) - a(n-3) for all n in Z. - Michael Somos, Mar 18 2022

A015565 a(n) = 7a(n-1) + 8a(n-2), a(0) = 0, a(1) = 1.

Original entry on oeis.org

0, 1, 7, 57, 455, 3641, 29127, 233017, 1864135, 14913081, 119304647, 954437177, 7635497415, 61083979321, 488671834567, 3909374676537, 31274997412295, 250199979298361, 2001599834386887, 16012798675095097, 128102389400760775, 1024819115206086201, 8198552921648689607

Offset: 0

Olivier Gérard

A linear 2nd order recurrence. A Jacobsthal number sequence.
Binomial transform of A053573 (preceded by zero). - Paul Barry, Apr 09 2003
Second binomial transform of A080424. Binomial transform of A053573, with leading zero. Binomial transform is 0,1,9,81,729,....(9^n - 0^n)/9. Second binomial transform is 0,1,11,111,1111,... (A002275: repunits). - Paul Barry, Mar 14 2004
Number of walks of length n between any two distinct nodes of the complete graph K_9. Example: a(2)=7 because the walks of length 2 between the nodes A and B of the complete graph ABCDEFGHI are: ACB, ADB, AEB, AFB, AGB, AHB and AIB. - Emeric Deutsch, Apr 01 2004
Unsigned version of A014990. - Philippe Deléham, Feb 13 2007
General form: k=8^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500, A109501, A015552. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
The ratio a(n+1)/a(n) converges to 8 as n approaches infinity. - Felix P. Muga II, Mar 09 2014

			G.f. = x + 7*x^2 + 57*x^3 + 455*x^4 + 3641*x^5 + 29127*x^6 + 233017*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
Dale Gerdemann, Fractal generated from (7,8) recursion, YouTube Video, Dec 5, 2014.
Index entries for linear recurrences with constant coefficients, signature (7,8).

Cf. A002275, A014990, A053573, A080424, A082311, A082365.
Cf. A062160, A099322, A106566.
Cf. A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500, A109501, A015552. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

[Round(8^n/9): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

seq(round(8^n/9),n=0..25); # Mircea Merca, Dec 28 2010

k=0;lst={k};Do[k=8^n-k;AppendTo[lst, k], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
LinearRecurrence[{7,8},{0,1},30] (* Harvey P. Dale, Mar 04 2016 *)

x='x+O('x^30); concat([0], Vec(x/(1-7*x-8*x^2))) \\ G. C. Greubel, Dec 30 2017

[lucas_number1(n,7,-8) for n in range(0, 21)] # Zerinvary Lajos, Apr 24 2009

From Paul Barry, Apr 09 2003: (Start)
a(n) = (8^n - (-1)^n)/9.
a(n) = J(3*n)/3 = A001045(3*n)/3. (End)
From Emeric Deutsch, Apr 01 2004: (Start)
a(n) = 8^(n-1) - a(n-1).
G.f.: x/(1-7*x-8*x^2). (End)
a(n) = Sum_{k = 0..n} A106566(n,k)*A099322(k). - Philippe Deléham, Oct 30 2008
a(n) = round(8^n/9). - Mircea Merca, Dec 28 2010
From Peter Bala, May 31 2024: (Start)
G.f: A(x) = x/(1 - x^2) o x/(1 - x^2), where o denotes the black diamond product of power series as defined by Dukes and White. Cf. A054878.
The black diamond product A(x) o A(x) is the g.f. for the number of walks of length n between any two distinct nodes of the complete graph K_81.
Row 8 of A062160. (End)
E.g.f.: exp(-x)*(exp(9*x) - 1)/9. - Elmo R. Oliveira, Aug 17 2024

A015540 a(n) = 5a(n-1) + 6a(n-2), a(0) = 0, a(1) = 1.

Original entry on oeis.org

0, 1, 5, 31, 185, 1111, 6665, 39991, 239945, 1439671, 8638025, 51828151, 310968905, 1865813431, 11194880585, 67169283511, 403015701065, 2418094206391, 14508565238345, 87051391430071, 522308348580425, 3133850091482551, 18803100548895305, 112818603293371831

Offset: 0

Olivier Gérard

Number of walks of length n between any two distinct vertices of the complete graph K_7. Example: a(2)=5 because the walks of length 2 between the vertices A and B of the complete graph ABCDEFG are ACB, ADB, AEB, AFB and AGB. - Emeric Deutsch, Apr 01 2004
General form: k=6^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500. -Vladimir Joseph Stephan Orlovsky, Dec 11 2008
Pisano period lengths: 1, 1, 2, 2, 2, 2, 14, 2, 2, 2, 10, 2, 12, 14, 2, 2, 16, 2, 18, 2, ... - R. J. Mathar, Aug 10 2012
Sum_{i=0..m} (-1)^(m+i)*6^i, for m >= 0, gives all terms after 0. - Bruno Berselli, Aug 28 2013
The ratio a(n+1)/a(n) converges to 6 as n approaches infinity. Also A053524, A080424, A051958. - Felix P. Muga II, Mar 09 2014

			G.f. = x + 5*x^2 + 31*x^3 + 185*x^4 + 1111*x^5 + 6665*x^6 + 39991*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014; Preprint on ResearchGate.
Index entries for linear recurrences with constant coefficients, signature (5,6).

Partial sums are in A033116. Cf. A014987.

[Floor(6^n/7-(-1)^n/7): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

seq(round(6^n/7),n=0..25); # Mircea Merca, Dec 28 2010

k=0; lst={k}; Do[k = 6^n-k; AppendTo[lst, k], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
CoefficientList[Series[x / ((1 - 6 x) (1 + x)), {x, 0, 50}], x] (* Vincenzo Librandi, Mar 26 2014 *)
LinearRecurrence[{5,6},{0,1},30] (* Harvey P. Dale, May 12 2015 *)

my(x='x+O('x^30)); concat([0], Vec(x/((1-6*x)*(1+x)))) \\ G. C. Greubel, Jan 24 2018

a(n) = round(6^n/7); \\ Altug Alkan, Sep 05 2018

[lucas_number1(n,5,-6) for n in range(21)] # Zerinvary Lajos, Apr 24 2009

a(n) = 5*a(n-1) + 6*a(n-2).
From Paul Barry, Apr 20 2003: (Start)
a(n) = (6^n - (-1)^n)/7.
G.f.: x/((1-6*x)*(1+x)).
E.g.f.: (exp(6*x) - exp(-x))/7. (End)
a(n) = 6^(n-1) - a(n-1). - Emeric Deutsch, Apr 01 2004
a(n+1) = Sum_{k=0..n} binomial(n-k, k)*5^(n-2*k)*6^k. - Paul Barry, Jul 29 2004
a(n) = round(6^n/7). - Mircea Merca, Dec 28 2010
a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-7)^k = (6^n - (-1)^n)/7 = (-1)^(n-1)*Sum_{k=0..n-1} (-6)^k. Equals (-1)^(n-1)*Phi(n,-6), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - Tom Copeland, Apr 14 2014

A053428 a(n) = a(n-1) + 20*a(n-2), n >= 2; a(0)=1, a(1)=1.

Original entry on oeis.org

1, 1, 21, 41, 461, 1281, 10501, 36121, 246141, 968561, 5891381, 25262601, 143090221, 648342241, 3510146661, 16476991481, 86679924701, 416219754321, 2149818248341, 10474213334761, 53470578301581, 262954844996801

Offset: 0

Barry E. Williams, Jan 10 2000

Hankel transform is 1,20,0,0,0,0,0,0,0,0,0,0,... - Philippe Deléham, Nov 02 2008

Zero followed by this sequence gives the inverse binomial transform of A080424. - Paul Curtz, Jun 07 2011

A. H. Beiler, Recreations in the Theory of Numbers, Dover, N.Y., 1964, pp. 194-196.

Vincenzo Librandi, Table of n, a(n) for n = 0..400
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014; Preprint on ResearchGate.
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
Index entries for linear recurrences with constant coefficients, signature (1,20).

Cf. A001045, A015441, A053404, A000302, A053573, A080424.

[((5^(n+1))-(-4)^(n+1)) div 9: n in [0..40]]; // Vincenzo Librandi, Jun 07 2011

Join[{a=1,b=1},Table[c=b+20*a;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Feb 01 2011 *)

a(n)=((5^(n+1))-(-4)^(n+1))/9 \\ Charles R Greathouse IV, Jun 10 2011

a(n) = ((5^(n+1)) - (-4)^(n+1))/9.

G.f.: 1/((1+4*x)*(1-5*x)). - R. J. Mathar, Nov 16 2007

More terms from James Sellers, Feb 02 2000

cp's OEIS Frontend

A078008 Expansion of (1 - x)/((1 + x)*(1 - 2*x)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Python

Sage

Formula

A015565 a(n) = 7*a(n-1) + 8*a(n-2), a(0) = 0, a(1) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A015540 a(n) = 5*a(n-1) + 6*a(n-2), a(0) = 0, a(1) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A053428 a(n) = a(n-1) + 20*a(n-2), n >= 2; a(0)=1, a(1)=1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A099138 a(n) = 6^(n-1)*J(n), where J(n) = A001045(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A078008 Expansion of (1 - x)/((1 + x)(1 - 2x)).

A015565 a(n) = 7a(n-1) + 8a(n-2), a(0) = 0, a(1) = 1.

A015540 a(n) = 5a(n-1) + 6a(n-2), a(0) = 0, a(1) = 1.