A026581 -id:A026581 - cp's OEIS frontend

A006131 a(n) = a(n-1) + 4*a(n-2), a(0) = a(1) = 1.

1, 1, 5, 9, 29, 65, 181, 441, 1165, 2929, 7589, 19305, 49661, 126881, 325525, 833049, 2135149, 5467345, 14007941, 35877321, 91909085, 235418369, 603054709, 1544728185, 3956947021, 10135859761, 25963647845, 66507086889, 170361678269

Offset: 0

N. J. A. Sloane

Length-n words with letters {0,1,2,3,4} where no two consecutive letters are nonzero, see fxtbook link below. - Joerg Arndt, Apr 08 2011
Equals INVERTi transform of A063727: (1, 2, 8, 24, 80, 256, 832, ...). - Gary W. Adamson, Aug 12 2010
a(n) is equal to the permanent of the n X n Hessenberg matrix with 1's along the main diagonal, 2's along the superdiagonal and the subdiagonal, and 0's everywhere else. - John M. Campbell, Jun 09 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 2, 5*a(n-2) equals the number of 5-colored compositions of n with all parts >= 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011
Pisano period lengths: 1, 1, 8, 1, 6, 8, 48, 2, 24, 6,120, 8, 12, 48, 24, 4,136, 24, 18, 6, ... - R. J. Mathar, Aug 10 2012
This is one of only two Lucas-type sequences whose 8th term is a square. The other one is A097705. - Michel Marcus, Dec 07 2012
Numerators of stationary probabilities for the M2/M/1 queue. In this queue, customers arrives in groups of 2. Intensity of arrival = 1. Service rate = 4. There is only one server and an infinite queue. - Igor Kleiner, Nov 02 2018
Number of 4-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
From M. Eren Kesim, May 13 2021: (Start)
a(n) is equal to the number of n-step walks from a universal vertex to another (itself or the other) on the diamond graph. It is also equal to the number of (n+1)-step walks from vertex A to vertex B on the graph below.
    B--C
    | /|
    |/ |
    A--D
(End)
From Wolfdieter Lang, Jan 03 2024: (Start)
This sequence {a(n-1)}, with a(-1) = 0, appears in the formula for powers of phi17 := (1 + sqrt(17))/2 = A222132, the fundamental (integer) algebraic number of Q(sqrt(17)): phi17^n = A052923(n) + a(n-1)*phi17, for n >= 0.
Limit_{n->oo} a(n+1)/a(n) = phi17. (End)

			G.f. = 1 + x + 5*x^2 + 9*x^3 + 29*x^4 + 65*x^5 + 181*x^6 + 441*x^7 + 1165*x^8 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Ilya Amburg, Krishna Dasaratha, Laure Flapan, Thomas Garrity, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse, and Matthew Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239 [math.CO], 2015.
Joerg Arndt, Matters Computational (The Fxtbook), pp.317-318.
Jolanta Borowska and Lena Łacińska, Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix", J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for tridiagonal Toeplitz matrices a=1, b=2.
Andrew Bremner and Nikos Tzanakis, Lucas sequences whose 8th term is a square, arXiv:math/0408371 [math.NT], 2004.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 437
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 387, 389.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
A. G. Shannon and J. V. Leyendekkers, The Golden Ratio family and the Binet equation, Notes on Number Theory and Discrete Mathematics, Vol. 21, No. 2, (2015), 35-42.
A. K. Whitford, Binet's formula generalized, Fib. Quart., 15 (1977), pp. 21, 24, 29.
Paul Thomas Young, p-adic congruences for generalized Fibonacci sequences, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
Index entries for linear recurrences with constant coefficients, signature (1,4).
Index entries for sequences related to Chebyshev polynomials.

Cf. A006130, A015440, A026581, A026583, A026597, A026599, A052923, A097705, A102446, A063727, A344236, A344261.

a:=[1,1];; for n in [3..30] do a[n]:=a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Dec 26 2019

[ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+4*Self(n-2): n in [1..40] ]; // Vincenzo Librandi, Aug 19 2011

A006131:=-1/(-1+z+4*z**2); # conjectured by Simon Plouffe in his 1992 dissertation
seq( simplify((2/I)^n*ChebyshevU(n, I/4)), n=0..30); # G. C. Greubel, Dec 26 2019

m = 16; f[n_] = Product[(1 + m*Cos[k*Pi/n]^2), {k, 1, Floor[(n - 1)/2]}]; Table[FullSimplify[ExpandAll[f[n]]], {n, 0, 15}]; N[%] (* Roger L. Bagula, Nov 21 2008 *)
a[n_]:=(MatrixPower[{{1,4},{1,0}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{1, 4}, {1, 1}, 29] (* Jean-François Alcover, Sep 25 2017 *)
Table[2^n*Fibonacci[n+1, 1/2], {n,0,30}] (* G. C. Greubel, Dec 26 2019 *)

a(n)=([0,1; 4,1]^n*[1;1])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

vector(31, n, (2/I)^(n-1)*polchebyshev(n-1, 2, I/4) ) \\ G. C. Greubel, Dec 26 2019

def A006131_list(n):
    list = [1, 1] + [0] * (n - 2)
    for i in range(2, n):
        list[i] = list[i - 1] + 4 * list[i - 2]
    return list
print(A006131_list(29)) # M. Eren Kesim, Jul 19 2021

[lucas_number1(n,1,-4) for n in range(1, 30)] # Zerinvary Lajos, Apr 22 2009

G.f.: 1/(1 - x - 4*x^2).
a(n) = (((1+sqrt(17))/2)^(n+1) - ((1-sqrt(17))/2)^(n+1))/sqrt(17).
a(n+1) = Sum_{k=0..ceiling(n/2)} 4^k*binomial(n-k, k). - Benoit Cloitre, Mar 06 2004
a(n) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)*(1+(-1)^(n-k))*2^(n-k)/2. - Paul Barry, Aug 28 2005
a(n) = A102446(n)/2. - Zerinvary Lajos, Jul 09 2008
a(n) = Sum_{k=0..n} A109466(n,k)*(-4)^(n-k). - Philippe Deléham, Oct 26 2008
a(n) = Product_{k=1..floor((n - 1)/2)} (1 + 16*cos(k*Pi/n)^2). - Roger L. Bagula, Nov 21 2008
Limiting ratio a(n+1)/a(n) is (1 + sqrt(17))/2 = 2.561552812... - Roger L. Bagula, Nov 21 2008
The fraction b(n) = a(n)/2^n satisfies b(n) = 1/2 b(n-1) + b(n-2); g.f. 1/(1-x/2-x^2); b(n) = (( (1+sqrt(17))/4 )^(n+1) - ( (1-sqrt(17))/4 )^(n+1))*2/sqrt(17). - Franklin T. Adams-Watters, Nov 30 2009
G.f.: G(0)/(2-x), where G(k) = 1 + 1/(1 - x*(17*k-1)/(x*(17*k+16) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + 4*x)/( x*(4*k+3 + 4*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 09 2013
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(k+1 + 4*x)/( x*(k+3/2 + 4*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 14 2013
G.f.: 1 / (1 - x / (1 - 4*x / (1 + 4*x))). - Michael Somos, Sep 15 2013
a(n) = (Sum_{1<=k<=n+1, k odd} C(n+1,k)*17^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014
a(n) = 2^n*Fibonacci(n+1, 1/2) = (2/i)^n*ChebyshevU(n, i/4). - G. C. Greubel, Dec 26 2019
E.g.f.: exp(x/2)*(sqrt(17)*cosh(sqrt(17)*x/2) + sinh(sqrt(17)*x/2))/sqrt(17). - Stefano Spezia, Dec 27 2019
a(n) = A344236(n) + A344261(n). - M. Eren Kesim, May 13 2021
With an initial 0 prepended, the sequence [0, 1, 1, 5, 9, 29, 65, ...] satisfies the congruences a(n*p^k) == e*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where e = +1 for the primes p listed in A296938, e = 0 when p = 17, otherwise e = -1. - Peter Bala, Dec 28 2022
a(n) = A052923(n+2)/4. - Wolfdieter Lang, Jan 03 2024
From Peter Bala, Jun 27 2025: (Start)
The following products telescope:
Product_{k >= 0} (1 + 4^k/a(2*k+1)) = 1 + sqrt(17).
Product_{k >= 1} (1 - 4^k/a(2*k+1)) = 1/18 * (1 + sqrt(17)).
Product_{k >= 0} (1 + (-4)^k/a(2*k+1)) = (1/17) * (17 + sqrt(17)).
Product_{k >= 1} (1 - (-4)^k/a(2*k+1)) = (1/18) * (17 + sqrt(17)). (End)

More terms from Roger L. Bagula, Sep 26 2006

A026597 Expansion of (1+x)/(1-x-4*x^2).

Original entry on oeis.org

1, 2, 6, 14, 38, 94, 246, 622, 1606, 4094, 10518, 26894, 68966, 176542, 452406, 1158574, 2968198, 7602494, 19475286, 49885262, 127786406, 327327454, 838473078, 2147782894, 5501675206, 14092806782, 36099507606, 92470734734

Offset: 0

Clark Kimberling

This sequence can generated by the following formula: a(n) = a(n-1) + 4*a(n-2) when n > 2; a[1] = 1, a[2] = 2. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 21 2004
An elephant sequence, see A175654 and A175655. For the corner squares just one A[5] vector, with decimal value 325, leads to the sequence given above. For the central square this vector leads to a companion sequence that is 4 times this very same sequence with n >= -1. - Johannes W. Meijer, Aug 15 2010
Equals INVERTi transform of A180168. - Gary W. Adamson, Aug 14 2010
Start with a single cell at coordinates (0, 0), then iteratively subdivide the grid into 2 X 2 cells and remove the cells that have one '1' in their modulo 3 coordinates. a(n) is the number of cells after n iterations. Cell configuration converges to a fractal with approximate dimension 1.357. - Peter Karpov, Apr 20 2017
Also, the number of walks of length n starting at vertex 1 in the graph with 4 vertices and edges {{0,1}, {0,2}, {0,3}, {1,2}, {2,3}}. - Sean A. Irvine, Jun 02 2025

Nathaniel Johnston, Table of n, a(n) for n = 0..500
Sean A. Irvine, Walks on Graphs.
Peter Karpov, InvMem, Item 26
Peter Karpov, Illustration of initial terms (n = 1..8)
Index entries for linear recurrences with constant coefficients, signature (1,4).

Cf. A006131, A006138, A007482, A026581, A026584, A122950, A175654, A175655, A180168.

[n le 2 select n else Self(n-1) + 4*Self(n-2): n in [1..41]]; // G. C. Greubel, Dec 08 2021

LinearRecurrence[{1,4},{1,2},40] (* Harvey P. Dale, Nov 28 2011 *)

[(2*i)^n*( chebyshev_U(n, -i/4) - (i/2)*chebyshev_U(n-1, -i/4) ) for n in (0..40)] # G. C. Greubel, Dec 08 2021

G.f.: (1+x)/(1-x-4*x^2).
a(n) = T(n,0) + T(n,1) + ... + T(n,2*n), T given by A026584.
a(n) = Sum_{k=0..n} binomial(floor((2*n-k-1)/2), n-k)*2^k. - Paul Barry, Feb 11 2005
a(n) = A006131(n) + A006131(n-1), n >= 1. - R. J. Mathar, Oct 20 2006
a(n) = Sum_{k=0..n} binomial(floor((2*n-k)/2),n-k)*4^floor(k/2). - Paul Barry, Feb 02 2007
Inverse binomial transform of A007482: (1, 3, 11, 39, 139, 495, ...). - Gary W. Adamson, Dec 04 2007
a(n) = Sum_{k=0..n+1} A122950(n+1,k)*3^(n+1-k). - Philippe Deléham, Jan 04 2008
a(n) = (1/2 + 3*sqrt(17)/34)*(1/2 + sqrt(17)/2)^n + (1/2 - 3*sqrt(17)/34)*(1/2 - sqrt(17)/2)^n. - Antonio Alberto Olivares, Jun 07 2011
a(n) = (2*i)^n*( chebyshevU(n, -i/4) - (i/2)*chebyshevU(n-1, -i/4) ). - G. C. Greubel, Dec 08 2021
E.g.f.: exp(x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, Jan 31 2023

Better name from Ralf Stephan, Jul 14 2013

A026599 a(n) = Sum_{j=0..2*i, i=0..n} A026584(i,j).

Original entry on oeis.org

1, 3, 9, 23, 61, 155, 401, 1023, 2629, 6723, 17241, 44135, 113101, 289643, 742049, 1900623, 4868821, 12471315, 31946601, 81831863, 209618269, 536945723, 1375418801, 3523201695, 9024876901, 23117683683, 59217191289, 151687926023

Offset: 0

Clark Kimberling

G. C. Greubel, Table of n, a(n) for n = 0..1000
Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case cyclic++, sequence c(n) (offset 1).
Index entries for linear recurrences with constant coefficients, signature (2,3,-4).

Cf. A026584, A026585, A026587, A026589, A026590, A026591, A026592, A026593, A026594, A026595, A026596, A026597 (first differences), A026598, A027282, A027283, A027284, A027285, A027286.

Cf. A006131, A026581.

[n le 3 select 3^(n-1) else 2*Self(n-1) +3*Self(n-2) -4*Self(n-3): n in [1..41]]; // G. C. Greubel, Dec 15 2021

LinearRecurrence[{2,3,-4}, {1,3,9}, 40] (* G. C. Greubel, Dec 15 2021 *)

[( (1+x)/((1-x)*(1-x-4*x^2)) ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Dec 15 2021

G.f.: (1+x)/((1-x)*(1-x-4*x^2)). - Ralf Stephan, Feb 04 2004
From Klaus Purath, Feb 02 2021: (Start)
a(n) = 2*a(n-1) + 3*a(n-2) - 4*a(n-3).
a(n) = Sum_{j=0..n} A026597(j). (End)
a(n) = 2^n*(Fibonacci(n+2, 1/2) + Fibonacci(n+1, 1/2)) - 1/2. - G. C. Greubel, Dec 15 2021

A382683 Expansion of (1-x^2) / (1-x-3*x^2+x^3).

Original entry on oeis.org

1, 1, 3, 5, 13, 25, 59, 121, 273, 577, 1275, 2733, 5981, 12905, 28115, 60849, 132289, 286721, 622739, 1350613, 2932109, 6361209, 13806923, 29958441, 65018001, 141086401, 306181963, 664423165, 1441882653, 3128970185, 6790194979, 14735222881, 31976837633

Offset: 0

Sean A. Irvine, Jun 02 2025

The number of walks of length n in the 4-vertex graph {{0,1}, {1,2}, {1,3}, {2,3}} starting at vertex 0 (see Example).

Also, a(n+1) is the number of such walks in the same graph starting at vertex 1.

			Consider walks starting at 0 in the following graph:
      2
     /|
  0-1 |
     \|
      3
The 5 walks of length 3 are 0-1-0-1, 0-1-2-1, 0-1-2-3, 0-1-3-1, and 0-1-3-2.

Index entries for linear recurrences with constant coefficients, signature (1,3,-1).

Cf. A087640 (walks starting at 2).

Cf. A000079 (missing edge {0,1}), A108411 (missing edge {2,3}), A026581 (adding edge {0,2}), A000244 (K4).

a:= n-> (<<0|1|0>, <0|0|1>, <-1|3|1>>^n. <<1,1,3>>)[1,1]:
seq(a(n), n=0..32);  # Alois P. Heinz, Jun 04 2025

LinearRecurrence[{1,3,-1},{1,1,3},33] (* or *) CoefficientList[Series[ (1-x^2) / (1-x-3*x^2+x^3),{x,0,32}],x] (* James C. McMahon, Jun 02 2025 *)

a(n) = A052973(n) + A052973(n-1). a(n) = A087640(n+1) - A087640(n). - R. J. Mathar, Jun 03 2025

A052923 Expansion of (1-x)/(1 - x - 4*x^2).

Original entry on oeis.org

1, 0, 4, 4, 20, 36, 116, 260, 724, 1764, 4660, 11716, 30356, 77220, 198644, 507524, 1302100, 3332196, 8540596, 21869380, 56031764, 143509284, 367636340, 941673476, 2412218836, 6178912740, 15827788084, 40543439044, 103854591380

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

First differences of A006131.

This sequence {a(n)} appears in the formula for powers of c = (1 + sqrt(17))/2 = A222132, the fundamental (integer) algebraic number of Q(sqrt(17)): c^n = a(n) + A006131(n-1)*c. This is also valid for positive powers of 1/c = (-1 + sqrt(17)) /8. See the formula below and in A006131 in terms of Chebyshev or Fibonacci polynomials. - Wolfdieter Lang, Nov 27 2023

G. C. Greubel, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 908
Index entries for linear recurrences with constant coefficients, signature (1,4).
Index entries for sequences related to Chebyshev polynomials.

Cf. A006131, A026581, A049310, A222132.

a:=[1,0];; for n in [3..30] do a[n]:=a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Oct 16 2019
a := n -> -(2*I)^n*ChebyshevU(n-2, -I/4):
seq(simplify(a(n)), n = 0..28);  # Peter Luschny, Dec 03 2023

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-x)/(1 -x -4*x^2) )); // G. C. Greubel, Oct 16 2019

spec := [S,{S=Sequence(Prod(Sequence(Z),Z,Union(Z,Z,Z,Z)))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
seq(coeff(series((1-x)/(1 -x -4*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 16 2019

LinearRecurrence[{1,4}, {1,0}, 30] (* G. C. Greubel, Oct 16 2019 *)

my(x='x+O('x^30)); Vec((1-x)/(1 -x -4*x^2)) \\ G. C. Greubel, Oct 16 2019

def A052923_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1 -x -4*x^2)).list()
A052923_list(30) # G. C. Greubel, Oct 16 2019

G.f.: (1-x)/(1 - x - 4*x^2).
a(n) = a(n-1) + 4*a(n-2), with a(0)=1, a(1)=0.
a(n) = Sum_{alpha=RootOf(-1+z+4*z^2)} (1/17)*(-1+9*alpha)*alpha^(-1-n).
If p[1]=0, and p[i]=4, ( 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
From Wolfdieter Lang, Nov 27 2023: (Start)
a(n) = 4*A006131(n-2), with A006131(-2) = 1/4 and A006131(-1) = 0.
a(n) = -(-2*i)^n*S(n-2, i/2), with i = sqrt(-1), and the S-Chebyshev polynomials (see A049310). S(-n, x) = -S(n-2, x). The Fibonacci polynomials are F(n, x) = (-i)^(n-1)*S(n-1, i*x). (End)

More terms from James Sellers, Jun 06 2000

A193734 Triangular array: the fusion of polynomial sequences P and Q given by p(n,x)=(2x+1)^n and q(n,x)=(x+2)^n.

Original entry on oeis.org

1, 1, 2, 1, 6, 8, 1, 10, 32, 32, 1, 14, 72, 160, 128, 1, 18, 128, 448, 768, 512, 1, 22, 200, 960, 2560, 3584, 2048, 1, 26, 288, 1760, 6400, 13824, 16384, 8192, 1, 30, 392, 2912, 13440, 39424, 71680, 73728, 32768, 1, 34, 512, 4480, 25088, 93184, 229376, 360448, 327680, 131072

Offset: 0

Clark Kimberling, Aug 04 2011

See A193722 for the definition of fusion of two sequences of polynomials or triangular arrays.

Triangle T(n,k), read by rows, given by (1,0,0,0,0,0,0,0,...) DELTA (2,2,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 05 2011

			First six rows:
  1;
  1,  2;
  1,  6,   8;
  1, 10,  32,  32;
  1, 14,  72, 160, 128;
  1, 18, 128, 448, 768, 512;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A084938, A193722, A193735.

Cf. A005053, A026581, A081294, A133494.

function T(n, k) // T = A193734
  if k lt 0 or k gt n then return 0;
  elif n lt 2 then return k+1;
  else return T(n-1, k) + 4*T(n-1, k-1);
  end if;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 19 2023

(* First program *)
z = 8; a = 2; b = 1; c = 1; d = 2;
p[n_, x_] := (a*x + b)^n ; q[n_, x_] := (c*x + d)^n
t[n_, k_] := Coefficient[p[n, x], x^k]; t[n_, 0] := p[n, x] /. x -> 0;
w[n_, x_] := Sum[t[n, k]*q[n + 1 - k, x], {k, 0, n}]; w[-1, x_] := 1
g[n_] := CoefficientList[w[n, x], {x}]
TableForm[Table[Reverse[g[n]], {n, -1, z}]]
Flatten[Table[Reverse[g[n]], {n, -1, z}]] (* A193734 *)
TableForm[Table[g[n], {n, -1, z}]]
Flatten[Table[g[n], {n, -1, z}]]      (* A193735 *)
(* Second program *)
T[n_, k_]:= T[n,k]= If[k<0 || k>n, 0, If[n<2, k+1, T[n-1,k] +4*T[n-1,k-1]]];
Table[T[n,k], {n,0,12}, {k,0,n}]//TableForm (* G. C. Greubel, Nov 19 2023 *)

def T(n, k): # T = A193734
    if (k<0 or k>n): return 0
    elif (n<2): return k+1
    else: return T(n-1, k) +4*T(n-1, k-1)
flatten([[T(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Nov 19 2023

T(n,k) = 4*T(n-1,k-1) + T(n-1,k) with T(0,0)=T(1,0)=1 and T(1,1)=2. - Philippe Deléham, Oct 05 2011
G.f.: (1 - 2*x*y)/(1 - x - 4*x*y). - R. J. Mathar, Aug 11 2015
From G. C. Greubel, Nov 19 2023: (Start)
T(n, n) = A081294(n).
Sum_{k=0..n} T(n, k) = A005053(n).
Sum_{k=0..n} (-1)^k * T(n, k) = (-1)^n * A133494(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = A026581(n-1) + (1/2)*[n=0]. (End)

A026583 a(n) = Sum{T(i,j)}, 0<=j<=i, 0<=i<=2n, T given by A026568.

Original entry on oeis.org

1, 4, 11, 30, 77, 200, 511, 1314, 3361, 8620, 22067, 56550, 144821, 371024, 950311, 2434410, 6235657, 15973300, 40915931, 104809134, 268472861, 687709400, 1761600847, 4512438450, 11558841841, 29608595644, 75843963011

Offset: 0

Clark Kimberling

Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case cyclic++, sequence d(n) (offset 1).
Index entries for linear recurrences with constant coefficients, signature (2,3,-4).

Cf. A006131, A026581 (first differences).

LinearRecurrence[{2,3,-4},{1,4,11},40] (* Harvey P. Dale, Apr 03 2024 *)

G.f.: (1+2x)/[(1-x)(1-x-4x^2)]. - Ralf Stephan, Feb 04 2004 (follows from first comment in A026581)

A103279 Array read by antidiagonals, generated by the matrix M = [1,1,1;1,N,1;1,1,1].

Original entry on oeis.org

1, 1, 3, 1, 3, 8, 1, 3, 9, 22, 1, 3, 10, 27, 60, 1, 3, 11, 34, 81, 164, 1, 3, 12, 43, 116, 243, 448, 1, 3, 13, 54, 171, 396, 729, 1224, 1, 3, 14, 67, 252, 683, 1352, 2187, 3344, 1, 3, 15, 82, 365, 1188, 2731, 4616, 6561, 9136, 1, 3, 16, 99, 516, 2019, 5616, 10923, 15760

Offset: 0

Lambert Klasen (lambert.klasen(AT)gmx.net), Jan 27 2005

Consider the matrix M = [1,1,1;1,N,1;1,1,1]; Characteristic polynomial of M is x^3 + (-N - 2)*x^2 + (2*N - 2)*x.
Now (M^n)[1,1] is equivalent to the recursion a(1) = 1, a(2) = 3, a(n) = (N+2)a(n-1)+(2N-2)a(n-2). (This also holds for negative N and fractional N.)
a(n+1)/a(n) converges to the upper root of the characteristic polynomial ((N + 2) + sqrt((N - 2)^2 + 8))/2 for n to infinity.
Columns of array follow the polynomials:
1,
3,
N + 8,
N^2 + 4*N + 22,
N^3 + 4*N^2 + 16*N + 60,
N^4 + 4*N^3 + 18*N^2 + 56*N + 164,
N^5 + 4*N^4 + 20*N^3 + 68*N^2 + 188*N + 448,
N^6 + 4*N^5 + 22*N^4 + 80*N^3 + 248*N^2 + 608*N + 1224,
N^7 + 4*N^6 + 24*N^5 + 92*N^4 + 312*N^3 + 864*N^2 + 1920*N + 3344,
N^8 + 4*N^7 + 26*N^6 + 104*N^5 + 380*N^4 + 1152*N^3 + 2928*N^2 + 5952*N + 9136,
etc.

			Array begins:
1,3,8,22,60,164,448,1224,3344,9136,...
1,3,9,27,81,243,729,2187,6561,19683,...
1,3,10,34,116,396,1352,4616,15760,53808,...
1,3,11,43,171,683,2731,10923,43691,174763,...
1,3,12,54,252,1188,5616,26568,125712,594864,...
...

Cf. A103280 (for (M^n)[1, 2]), A028859 (for N=0), A000244 (for N=1), A007052 (for N=2), A007583 (for N=3), A083881 (for N=4), A026581 (for N=-1), A026532 (for N=-2), A026568.

T11(N, n) = if(n==1,1,if(n==2,3,(N+2)*r1(N,n-1)-(2*N-2)*r1(N,n-2))) for(k=0,10,print1(k,": ");for(i=1,10,print1(T11(k,i),","));print())

T(N, 1)=1, T(N, 2)=3, T(N, n)=(N+2)*T(N, n-1)-(2*N-2)*T(N, n-2).

cp's OEIS Frontend

A006131 a(n) = a(n-1) + 4*a(n-2), a(0) = a(1) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A026597 Expansion of (1+x)/(1-x-4*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A026599 a(n) = Sum_{j=0..2*i, i=0..n} A026584(i,j).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A382683 Expansion of (1-x^2) / (1-x-3*x^2+x^3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052923 Expansion of (1-x)/(1 - x - 4*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A193734 Triangular array: the fusion of polynomial sequences P and Q given by p(n,x)=(2x+1)^n and q(n,x)=(x+2)^n.

Views

Author

Keywords

Comments

Examples

Links

A123486 Riordan array (1/(1-2x), x/(1-4x^2)).