The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: "generalized fibonacci"
Displaying 1-10 of 346 results found. page 1 2 3 4 5 6 7 8 9 10 ... 35
     Sort: relevance | references | number | modified | created      Format: long | short | data
A015441 Generalized Fibonacci numbers. +20
48
0, 1, 1, 7, 13, 55, 133, 463, 1261, 4039, 11605, 35839, 105469, 320503, 953317, 2876335, 8596237, 25854247, 77431669, 232557151, 697147165, 2092490071, 6275373061, 18830313487, 56482551853, 169464432775, 508359743893, 1525146340543, 4575304803901, 13726182847159 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
a(n) is the coefficient of x^(n-1) in the bivariate Fibonacci polynomials F(n)(x,y) = xF(n-1)(x,y) + yF(n-2)(x,y), F(0)(x,y)=0, F(1)(x,y)=1, when y=6x^2. - Mario Catalani (mario.catalani(AT)unito.it), Dec 06 2002
For n>=1: number of length-(n-1) words with letters {0,1,2,3,4,5,6,7} where no two consecutive letters are nonzero, see fxtbook link below. - Joerg Arndt, Apr 08 2011
Starting with offset 1 and convolved with (1, 3, 3, 3, ...) = A003462: (1, 4, 13, 40, ...). - Gary W. Adamson, May 28 2009
a(n) is identical to its inverse binomial transform signed. Differences: A102901. - Paul Curtz, Feb 23 2010
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, 7*a(n-2) equals the number of 7-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, 1, 2, 20, 1, 6, 2, 3, 20, 5, 2, 12, 6, 20, 4, 16, 3, 18, 20, ... - R. J. Mathar, Aug 10 2012
A015441 and A015518 are the only integer sequences (from the family of homogeneous linear recurrence relation of order 2 with positive integer coefficients with initial values a(0)=0 and a(1)=1) whose ratio a(n+1)/a(n) converges to 3 as n approaches infinity. - Felix P. Muga II, Mar 14 2014
This is an autosequence of the first kind: the array of successive differences shows a main diagonal of zeros and the inverse binomial transform is identical to the sequence (with alternating signs). - Pointed out by Paul Curtz, Dec 05 2016
First two upper diagonals: A000400(n).
This is a variation on the Starhex honeycomb configuration A332243, see illustration in links. It is an alternating pattern of the 2nd iteration of the centered hexagonal numbers A003215 and centered 12-gonal 'Star' numbers A003154. - John Elias, Oct 06 2021
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
Joerg Arndt, Matters Computational (The Fxtbook), p. 317-318
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
John Elias, Illustration: A Starhex honeycomb variation
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
H. Li and T. MacHenry, Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences, J. Int. Seq. 16 (2013) #13.3.5, example 48.
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014; Preprint on ResearchGate.
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.
Index entries for linear recurrences with constant coefficients, signature (1,6).
FORMULA
G.f.: x/((1+2*x)*(1-3*x)).
a(n) = a(n-1) + 6*a(n-2).
a(n) = (1/5)*((3^n)-((-2)^n)). - henryk.wicke(AT)stud.uni-hannover.de
E.g.f.: (exp(3*x) - exp(-2*x))/5. - Paul Barry, Apr 20 2003
a(n+1) = Sum_{k=0..ceiling(n/2)} 6^k*binomial(n-k, k). - Benoit Cloitre, Mar 06 2004
a(n) = (A000244(n) - A001045(n+1)(-1)^n - A001045(n)(-1)^n)/5. - Paul Barry, Apr 27 2004
The binomial transform of [1,1,7,13,55,133,463,...] is A122117. - Philippe Deléham, Oct 19 2006
a(n+1) = Sum_{k=0..n} A109466(n,k)*(-6)^(n-k). - Philippe Deléham, Oct 26 2008
a(n) = 3a(n-1) + (-1)^(n+1)*A000079(n-1). - Paul Curtz, Feb 23 2010
G.f.: Q(0) -1, where Q(k) = 1 + 6*x^2 + (k+2)*x - x*(k+1 + 6*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 06 2013
a(n) = (Sum_{1<=k<=n, k odd} binomial(n,k)*5^(k-1))/2^(n-1). - Vladimir Shevelev, Feb 05 2014
a(-n) = -(-1)^n * a(n) / 6^n for all n in Z. - Michael Somos, Mar 18 2014
From Peter Bala, Apr 01 2015: (Start)
Sum_{n >= 0} a(n+1)*x^n = exp( Sum_{n >= 1} A087451(n)*x^n/n ).
For k = 0, 1, 2, ... and for n >= 1, (5^k)*a(n) | a((5^k)*n).
The expansion of exp( Sum_{n >= 1} a(5*n)/(5*a(n))*x^n/n ) has integral coefficients. Cf. A001656. (End)
EXAMPLE
G.f. = x + x^2 + 7*x^3 + 13*x^4 + 55*x^5 + 133*x^6 + 463*x^7 + 1261*x^8 + ...
MAPLE
A015441:=n->(1/5)*((3^n)-((-2)^n)); seq(A015441(n), n=0..30); # Wesley Ivan Hurt, Mar 14 2014
MATHEMATICA
a[n_]:=(MatrixPower[{{1, 4}, {1, -2}}, n].{{1}, {1}})[[2, 1]]; Table[Abs[a[n]], {n, -1, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{1, 6}, {0, 1}, 30] (* Harvey P. Dale, Apr 26 2011 *)
CoefficientList[Series[x/((1 + 2 x) (1 - 3 x)), {x, 0, 29}], x] (* Michael De Vlieger, Dec 05 2016 *)
PROG
(PARI) {a(n) = (3^n - (-2)^n) / 5};
(Sage) [lucas_number1(n, 1, -6) for n in range(0, 27)] # Zerinvary Lajos, Apr 22 2009
(Magma) I:=[0, 1]; [n le 2 select I[n] else Self(n-1) + 6*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 24 2018
CROSSREFS
Cf. A000079, A003462, A016153, A109466, A122117. Cf. A001656, A087451. Cf. A000400.
KEYWORD
nonn,easy,nice
AUTHOR
Olivier Gérard
STATUS
approved
A057087 Scaled Chebyshev U-polynomials evaluated at i. Generalized Fibonacci sequence. +20
38
1, 4, 20, 96, 464, 2240, 10816, 52224, 252160, 1217536, 5878784, 28385280, 137056256, 661766144, 3195289600, 15428222976, 74494050304, 359689093120, 1736732573696, 8385686667264, 40489676963840, 195501454524416 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
a(n) gives the length of the word obtained after n steps with the substitution rule 0->1111, 1->11110, starting from 0. The number of 1's and 0's of this word is 4*a(n-1) and 4*a(n-2), respectively.
Inverse binomial transform of odd Pell bisection A001653. With a leading zero, inverse binomial transform of even Pell bisection A001542, divided by 2. - Paul Barry, May 16 2003
For positive n, a(n) equals the permanent of the n X n tridiagonal matrix with 4's along the main diagonal, and 2's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 19 2011
Pisano period lengths: 1, 1, 8, 1, 3, 8, 6, 1, 24, 3, 120, 8, 21, 6, 24, 1, 16, 24, 360, 3, ... . - R. J. Mathar, Aug 10 2012
Exponential convolution of Pell numbers (A000129) and companion Pell numbers (A002203), divided by 2 and leading zero dropped. - Vladimir Reshetnikov, Oct 07 2016
LINKS
Indranil Ghosh, Table of n, a(n) for n = 0..1459
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=4, q=4.
Tanya Khovanova, Recursive Sequences.
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419; Eqs.(39) and (45),rhs, m=4.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,4)
FORMULA
a(n) = 4*(a(n-1) + a(n-2)), a(-1)=0, a(0)=1.
G.f.: 1/(1 - 4*x - 4*x^2).
a(n) = S(n, 2*i)*(-2*i)^n with S(n, x) := U(n, x/2), Chebyshev's polynomials of the 2nd kind, A049310.
a(n) = Sum_{k=0..n} 3^k*A063967(n,k). - Philippe Deléham, Nov 03 2006
a(n) = A000129(n+1)*A000079(n). - R. J. Mathar, Jul 08 2009
From Johannes W. Meijer, Aug 01 2010: (Start)
Limit_{k->oo} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2);
Limit_{n->oo} A084128(n)/A057087(n-1) = sqrt(2). (End)
a(n) = 4^n*hypergeom([1/2-n/2, -n/2], [-n], -1)) for n>=1. - Peter Luschny, Dec 17 2015
MAPLE
A057087 := n -> `if`(n=0, 1, 4^n*hypergeom([1/2-n/2, -n/2], [-n], -1)):
seq(simplify(A057087(n)), n=0..21); # Peter Luschny, Dec 17 2015
MATHEMATICA
Table[Fibonacci[n + 1, 2] 2^n, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 08 2016 *)
LinearRecurrence[{4, 4}, {1, 4}, 30] (* Harvey P. Dale, Aug 17 2017 *)
PROG
(PARI) a(n)=if(n<0, 0, (2*I)^n*subst(I*poltchebi(n+1)+poltchebi(n), 'x, -I)/2) /* Michael Somos, Sep 16 2005 */
(PARI) Vec(1/(1-4*x-4*x^2) + O(x^100)) \\ Altug Alkan, Dec 17 2015
(Sage) [lucas_number1(n, 4, -4) for n in range(1, 23)] # Zerinvary Lajos, Apr 23 2009
(Magma) I:=[1, 4]; [n le 2 select I[n] else 4*Self(n-1) + 4*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 16 2018
CROSSREFS
Pairwise sums are in A086347.
Appears in A086346, A086347 and A086348. - Johannes W. Meijer, Aug 01 2010
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Aug 11 2000
STATUS
approved
A015443 Generalized Fibonacci numbers: a(n) = a(n-1) + 8*a(n-2). +20
30
1, 1, 9, 17, 89, 225, 937, 2737, 10233, 32129, 113993, 371025, 1282969, 4251169, 14514921, 48524273, 164643641, 552837825, 1869986953, 6292689553, 21252585177, 71594101601, 241614783017, 814367595825, 2747285859961 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Construct a graph as follows: form the graph whose adjacency matrix is the tensor product of that of P_3 and [1,1;1,1], then add a loop at each of the extremity nodes. a(n-1) counts walks of length n between adjacent nodes. - Paul Barry, Nov 12 2004
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, 9*a(n-2) equals the number of 9-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, 6, 1, 24, 6, 16, 1, 6, 24, 110, 6, 56, 16, 24, 2, 16, 6, 60, 24, ... - R. J. Mathar, Aug 10 2012
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Joerg Arndt, Matters Computational (The Fxtbook), p. 318
M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Index entries for linear recurrences with constant coefficients, signature (1,8)
FORMULA
a(n) = (((1+sqrt(33))/2)^(n+1) - ((1-sqrt(33))/2)^(n+1))/sqrt(33).
a(n) = Sum_{k=0..n} A109466(n,k)*(-8)^(n-k). - Philippe Deléham, Oct 26 2008
G.f.: 1/(1-x-8*x^2). - R. J. Mathar, Apr 07 2011
a(n) = (Sum_{1<=k<=n+1, k odd} C(n+1,k)*33^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014
MATHEMATICA
CoefficientList[Series[1/(1-x-8*x^2), {x, 0, 50}], x] (* G. C. Greubel, Apr 30 2017 *)
PROG
(Sage) [lucas_number1(n, 1, -8) for n in range(1, 27)] # Zerinvary Lajos, Apr 22 2009
(Magma) [ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+8*Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 23 2011
(PARI) a(n)=Vec(1/(1-x-8*x^2)+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014
CROSSREFS
Cf. A015442, A015441, A100302, A100303.
KEYWORD
nonn,easy
AUTHOR
Olivier Gérard
STATUS
approved
A057088 Scaled Chebyshev U-polynomials evaluated at i*sqrt(5)/2. Generalized Fibonacci sequence. +20
29
1, 5, 30, 175, 1025, 6000, 35125, 205625, 1203750, 7046875, 41253125, 241500000, 1413765625, 8276328125, 48450468750, 283633984375, 1660422265625, 9720281250000, 56903517578125, 333118994140625, 1950112558593750, 11416157763671875, 66831351611328125, 391237546875000000 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
a(n) gives the length of the word obtained after n steps with the substitution rule 0->11111, 1->111110, starting from 0. The number of 1's and 0's of this word is 5*a(n-1) and 5*a(n-2), resp.
a(n) / a(n-1) converges to (5 + (3 * sqrt(5))) / 2 as n approaches infinity. (5 + (3 * sqrt(5))) / 2 can also be written as phi^2 + (2 * phi), phi^3 + phi, phi + sqrt(5) + 2, (3 * phi) + 1, (3 * phi^2) - 2, phi^4 - 1 and (5 + (3 * (L(n) / F(n)))) / 2, where L(n) is the n-th Lucas number and F(n) is the n-th Fibonacci number as n approaches infinity. - Ross La Haye, Aug 18 2003, on another version
Pisano period lengths: 1, 3, 3, 6, 1, 3, 24, 12, 9, 3, 10, 6, 56, 24, 3, 24,288, 9, 18, 6, ... - R. J. Mathar, Aug 10 2012
LINKS
Indranil Ghosh, Table of n, a(n) for n = 0..1300
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=5, q=5.
Tanya Khovanova, Recursive Sequences
W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. Eqs.(39) and (45),rhs, m=5.
Eric Weisstein's World of Mathematics, Horadam Sequence
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (5,5)
FORMULA
a(n) = 5*(a(n-1) + a(n-2)), a(-1)=0, a(0)=1.
a(n) = S(n, i*sqrt(5))*(-i*sqrt(5))^n with S(n, x) := U(n, x/2), Chebyshev's polynomials of the 2nd kind, A049310.
G.f.: 1/(1 - 5*x - 5*x^2).
a(n) = (1/3)*Sum_{k=0..n} binomial(n, k)*Fibonacci(k)*3^k. - Benoit Cloitre, Oct 25 2003
a(n) = ((5 + 3*sqrt(5))/2)^n(1/2 + sqrt(5)/6) + (1/2 - sqrt(5)/6)((5 - 3*sqrt(5))/2)^n. - Paul Barry, Sep 22 2004
(a(n)) appears to be given by the floretion - 0.75'i - 0.5'j + 'k - 0.75i' + 0.5j' + 0.5k' + 1.75'ii' - 1.25'jj' + 1.75'kk' - 'ij' - 0.5'ji' - 0.75'jk' - 0.75'kj' - 1.25e ("jes"). - Creighton Dement, Nov 28 2004
a(n) = Sum_{k=0..n} 4^k*A063967(n,k). - Philippe Deléham, Nov 03 2006
G.f.: G(0)/(2-5*x), where G(k)= 1 + 1/(1 - x*(9*k-5)/(x*(9*k+4) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 17 2013
From Ehren Metcalfe, Nov 18 2017: (Start)
With F(n) = A000045(n), L(n) = A000032(n), beta = (1-sqrt(5))/2:
a(2*n-1) = 5^n*F(4*n)/3 = (5^(n-1/2)*L(4*n) - 2*5^(n-1/2)*beta^(4*n))/3.
a(2*n) = 5^n*L(4*n+2)/3 = (5^(n+1/2)*F(4*n+2) + 2*5^n*beta^(4*n+2))/3.
a(n) = round 5^((n+1)/2)*F(2*(n+1))/3.
a(n) = round 5^(n/2)*L(2*(n+1))/3. (End)
MAPLE
a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=5*a[n-1]+5*a[n-2]od: seq(a[n], n=1..33); # Zerinvary Lajos, Dec 14 2008
MATHEMATICA
LinearRecurrence[{5, 5}, {1, 5}, 30] (* G. C. Greubel, Jan 16 2018 *)
PROG
(Sage) [lucas_number1(n, 5, -5) for n in range(1, 22)] # Zerinvary Lajos, Apr 24 2009
(PARI) x='x+O('x^30); Vec(1/(1 - 5*x - 5*x^2)) \\ G. C. Greubel, Jan 16 2018
(Magma) I:=[1, 5]; [n le 2 select I[n] else 5*Self(n-1) + 5*Self(n-2): n in [0..30]]; // G. C. Greubel, Jan 16 2018
CROSSREFS
Cf. A001076, A006190, A007482, A015520, A015521, A015523, A015524, A015525, A015528, A015529, A015530, A015531, A015532, A015533, A015534, A015535, A015536, A015537, A015443, A015447, A030195, A053404, A057087, A083858, A085939, A090017, A091914, A099012, A180222, A180226.
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Aug 11 2000
STATUS
approved
A015440 Generalized Fibonacci numbers. +20
25
1, 1, 6, 11, 41, 96, 301, 781, 2286, 6191, 17621, 48576, 136681, 379561, 1062966, 2960771, 8275601, 23079456, 64457461, 179854741, 502142046, 1401415751, 3912125981, 10919204736, 30479834641, 85075858321, 237475031526 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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, 6*a(n-2) equals the number of 6-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, 3, 6, 6, 1, 6, 21, 12, 18, 3, 40, 6, 56, 21, 6, 24, 16, 18, 360, 6, .... - R. J. Mathar, Aug 10 2012
From Wolfdieter Lang, Jan 02 2024: (Start)
This sequence {a(n-1)}, with a(-1) = 0, appears in the formula for powers of phi21 := (1 + sqrt(21))/2 = A222134 = 2.791287..., together with A(n) = A365824(n), as phi21^n = A(n) + a(n-1)*phi21(n), for n >= 0.
Limit_{n->oo} a(n)/a(n-1) = phi21. (End)
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Joerg Arndt, Matters Computational (The Fxtbook), section 14.8, pp. 317-318
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
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.
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,5).
FORMULA
a(n) = a(n-1) + 5 a(n-2).
a(n) = (( (1+sqrt(21))/2 )^(n+1) - ( (1-sqrt(21))/2 )^(n+1))/sqrt(21).
a(n) = Sum_{k=0..ceiling(n/2)} 5^k*binomial(n-k, k). - Benoit Cloitre, Mar 06 2004
G.f.: 1/(1 - x - 5x^2). - R. J. Mathar, Sep 03 2008
a(n) = Sum_{k=0..n} A109466(n,k)*(-5)^(n-k). - Philippe Deléham, Oct 26 2008
From Jeffrey R. Goodwin, May 28 2011: (Start)
A special case of a more general class of Lucas sequences given by
U(n) = U(n-1) + (4^(m-1)-1)/3 U(n-2).
U(n) = (( (1+sqrt((4^(m)-1)/3))/2 )^(n+1) - ( (1-sqrt((4^(m)-1)/3))/2 )^(n+1))/sqrt((4^(m)-1)/3). Fix m = 2 to get the formula for the Fibonacci sequence, fix m = 3 to get the formula for a(n). (End)
G.f.: G(0)/(2-x), where G(k)= 1 + 1/(1 - x*(21*k-1)/(x*(21*k+20) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013
G.f.: Q(0)/x -1/x, where Q(k) = 1 + 5*x^2 + (k+2)*x - x*(k+1 + 5*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 06 2013
a(n) = (Sum_{k=1..n+1, k odd} binomial(n+1,k)*21^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014
With an initial 0 prepended, the sequence [0, 1, 1, 6, 11, 41, 96, ...] satisfies the congruences a(n*p^k) == (3|p)*(7|p)*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where (n|p) denotes the Legendre symbol. See Young, Theorem 1, Corollary 1(i). - Peter Bala, Dec 28 2022
a(n) = sqrt(-5)^(n-1)*S(n-1,1/sqrt(-5)), for n >= 0, with the Chebyshev polynomial S(n, x) (see A049310). - Wolfdieter Lang, Nov 17 2023
MAPLE
A015440 := proc(n)
if n <= 1 then
1;
else
procname(n-1)+5*procname(n-2) ;
end if;
end proc: # R. J. Mathar, May 15 2016
MATHEMATICA
a[n_]:=(MatrixPower[{{1, 3}, {1, -2}}, n].{{1}, {1}})[[2, 1]]; Table[Abs[a[n]], {n, -1, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{1, 5}, {1, 1}, 100] (* Vincenzo Librandi, Nov 06 2012 *)
PROG
(Sage) [lucas_number1(n, 1, -5) for n in range(1, 28)] # Zerinvary Lajos, Apr 22 2009
(Magma) [n le 2 select 1 else Self(n-1)+5*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 06 2012
(PARI) a(n)=abs([1, 3; 1, -2]^n*[1; 1])[2, 1] \\ Charles R Greathouse IV, Feb 03 2014
CROSSREFS
Cf. A006130, A006131, A015441, A049310, A222134, A365824.
KEYWORD
nonn,easy
AUTHOR
Olivier Gérard
STATUS
approved
A092921 Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0. +20
25
0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 3, 2, 1, 1, 0, 1, 5, 4, 2, 1, 1, 0, 1, 8, 7, 4, 2, 1, 1, 0, 1, 13, 13, 8, 4, 2, 1, 1, 0, 1, 21, 24, 15, 8, 4, 2, 1, 1, 0, 1, 34, 44, 29, 16, 8, 4, 2, 1, 1, 0, 1, 55, 81, 56, 31, 16, 8, 4, 2, 1, 1, 0, 1, 89, 149, 108, 61, 32, 16, 8, 4, 2, 1, 1, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,12
COMMENTS
For all k >= 1, the k-generalized Fibonacci number F(k,n) satisfies the recurrence obtained by adding more terms to the recurrence of the Fibonacci numbers.
The number of tilings of an 1 X n rectangle with tiles of size 1 X 1, 1 X 2, ..., 1 X k is F(k,n).
T(k,n) is the number of 0-balanced ordered trees with n edges and height k (height is the number of edges from root to a leaf). - Emeric Deutsch, Jan 19 2007
Brlek et al. (2006) call this table "number of psp-polyominoes with flat bottom". - N. J. A. Sloane, Oct 30 2018
LINKS
Alois P. Heinz, Antidiagonals n = 0..140, flattened
Srecko Brlek, Andrea Frosini, Simone Rinaldi, and Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol. 13, (2006). Table 1 is essentially this array. - N. J. A. Sloane, Jul 20 2014
E. S. Egge, Restricted permutations related to Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0109219 [math.CO], 2001.
E. S. Egge, Restricted 3412-Avoiding Involutions, arXiv:math/0307050 [math.CO], 2003.
E. S. Egge and T. Mansour, Restricted permutations, Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0203226 [math.CO], 2002.
E. S. Egge and T. Mansour, 231-avoiding involutions and Fibonacci numbers, arXiv:math/0209255 [math.CO], 2002.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Abraham Flaxman, Aram W. Harrow, and Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8.
I. Flores, k-Generalized Fibonacci numbers, Fib. Quart., 5 (1967), 258-266.
H. Gabai, Generalized Fibonacci k-sequences, Fib. Quart., 8 (1970), 31-38.
R. Kemp, Balanced ordered trees, Random Structures and Alg., 5 (1994), pp. 99-121.
E. P. Miles jr., Generalized Fibonacci numbers and associated matrices, The Amer. Math. Monthly, 67 (1960) 745-752.
M. D. Miller, On generalized Fibonacci numbers, The Amer. Math. Monthly, 78 (1971) 1108-1109.
Harold R. Parks and Dean C. Wills, Sum of k-bonacci Numbers, arXiv:2208.01224 [math.CO], 2022. See p. 5.
FORMULA
F(k,n) = F(k,n-1) + F(k,n-2) + ... + F(k,n-k); F(k,1) = 1 and F(k,n) = 0 for n <= 0.
G.f.: x/(1-Sum_{i=1..k} x^i).
F(k,n) = 2^(n-2) for 1 < n <= k+1. - M. F. Hasler, Apr 20 2018
F(k,n) = Sum_{j=0..floor(n/(k+1))} (-1)^j*((n - j*k) + j + delta(n,0))/(2*(n - j*k) + delta(n,0))*binomial(n - j*k, j)*2^(n-j*(k+1)), where delta denotes the Kronecker delta (see Corollary 3.2 in Parks and Wills). - Stefano Spezia, Aug 06 2022
EXAMPLE
From Peter Luschny, Apr 03 2021: (Start)
Array begins:
n = 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------------
[k=1, mononacci ] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
[k=2, Fibonacci ] 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
[k=3, tribonacci] 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...
[k=4, tetranacci] 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
[k=5, pentanacci] 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...
[k=6] 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, ...
[k=7] 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, ...
[k=8] 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
[k=9] 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ...
Note that the first parameter in F(k, n) refers to rows, and the second parameter refers to columns. This is always the case. Only the usual naming convention for the indices is not adhered to because it is common to call the row sequences k-bonacci numbers. (End)
.
From Peter Luschny, Aug 12 2015: (Start)
As a triangle counting compositions of n with largest part k:
n\k]| [0][1] [2] [3] [4][5][6][7][8][9]
[0] | [0]
[1] | [0, 1]
[2] | [0, 1, 1]
[3] | [0, 1, 1, 1]
[4] | [0, 1, 2, 1, 1]
[5] | [0, 1, 3, 2, 1, 1]
[6] | [0, 1, 5, 4, 2, 1, 1]
[7] | [0, 1, 8, 7, 4, 2, 1, 1]
[8] | [0, 1, 13, 13, 8, 4, 2, 1, 1]
[9] | [0, 1, 21, 24, 15, 8, 4, 2, 1, 1]
For example for n=7 and k=3 we have the 7 compositions [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [3, 1, 3], [3, 1, 2, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1].
(End)
MAPLE
F:= proc(k, n) option remember; `if`(n<2, n,
add(F(k, n-j), j=1..min(k, n)))
end:
seq(seq(F(k, d+1-k), k=1..d+1), d=0..12); # Alois P. Heinz, Nov 02 2016
# Based on the above function:
Arow := (k, len) -> seq(F(k, j), j = 0..len):
seq(lprint(Arow(k, 14)), k = 1..10); # Peter Luschny, Apr 03 2021
MATHEMATICA
F[k_, n_] := F[k, n] = If[n<2, n, Sum[F[k, n-j], {j, 1, Min[k, n]}]];
Table[F[k, d+1-k], {d, 0, 12}, {k, 1, d+1}] // Flatten (* Jean-François Alcover, Jan 11 2017, translated from Maple *)
PROG
(PARI) F(k, n)=if(n<2, if(n<1, 0, 1), sum(i=1, k, F(k, n-i)))
(PARI) T(m, n)=!!n*(matrix(m, m, i, j, j==i+1||i==m)^(n+m-2))[1, m] \\ M. F. Hasler, Apr 20 2018
(PARI) F(k, n) = if(n==0, 0, polcoeff(lift(Mod('x, Pol(vector(k+1, i, if(i==1, 1, -1))))^(n+k-2)), k-1)); \\ Kevin Ryde, Jun 05 2020
(Sage)
# As a triangle of compositions of n with largest part k.
C = lambda n, k: Compositions(n, max_part=k, inner=[k]).cardinality()
for n in (0..9): [C(n, k) for k in (0..n)] # Peter Luschny, Aug 12 2015
CROSSREFS
Columns converge to A166444: each column n converges to A166444(n) = 2^(n-2).
Rows 1-8 are (shifted) A057427, A000045, A000073, A000078, A001591, A001592, A066178, A079262.
Essentially a reflected version of A048887.
See A048004 and A126198 for closely related arrays.
Cf. A066099.
KEYWORD
nonn,tabl
AUTHOR
Ralf Stephan, Apr 17 2004
STATUS
approved
A015447 Generalized Fibonacci numbers: a(n) = a(n-1) + 11*a(n-2). +20
21
1, 1, 12, 23, 155, 408, 2113, 6601, 29844, 102455, 430739, 1557744, 6295873, 23431057, 92685660, 350427287, 1369969547, 5224669704, 20294334721, 77765701465, 301003383396, 1156426099511, 4467463316867, 17188150411488 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
The compositions of n in which each positive integer is colored by one of p different colors are called p-colored compositions of n. For n>=2, 12*a(n-2) equals the number of 12-colored compositions of n, with all parts >= 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,11).
FORMULA
a(n) = ( ( (1+3*sqrt(5))/2 )^(n+1) - ( (1-3*sqrt(5))/2 )^(n+1) )/(3*sqrt(5)).
a(n-1) = (1/3)*(-1)^n*Sum_{i=0..n} (-3)^i*Fibonacci(i)*C(n, i). - Benoit Cloitre, Mar 06 2004
a(n) = Sum_{k=0..n} A109466(n,k)*(-11)^(n-k). - Philippe Deléham, Oct 26 2008
G.f.: 1/(1 - x - 11*x^2). - Harvey P. Dale, May 08 2011
a(n) = ( Sum_{1<=k<=n+1, k odd} C(n+1,k)*45^((k-1)/2) )/2^n. - Vladimir Shevelev, Feb 05 2014
MATHEMATICA
Join[{a=1, b=1}, Table[c=b+11*a; a=b; b=c, {n, 100}]] (* Vladimir Joseph Stephan Orlovsky, Jan 16 2011 *)
LinearRecurrence[{1, 11}, {1, 1}, 30] (* or *) CoefficientList[Series[ 1/(1-x-11 x^2), {x, 0, 50}], x] (* Harvey P. Dale, May 08 2011 *)
PROG
(Sage) [lucas_number1(n, 1, -11) for n in range(0, 27)] # Zerinvary Lajos, Apr 22 2009
(Magma) [n le 2 select 1 else Self(n-1) + 11*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 06 2012
(PARI) Vec(1/(1-x-11*x^2)+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014
CROSSREFS
Cf. A015446, A015443.
KEYWORD
nonn,easy
AUTHOR
Olivier Gérard
STATUS
approved
A015445 Generalized Fibonacci numbers: a(n) = a(n-1) + 9*a(n-2). +20
19
1, 1, 10, 19, 109, 280, 1261, 3781, 15130, 49159, 185329, 627760, 2295721, 7945561, 28607050, 100117099, 357580549, 1258634440, 4476859381, 15804569341, 56096303770, 198337427839, 703204161769, 2488241012320 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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, 10*a(n-2) equals the number of 10-colored compositions of n with all parts >= 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. Borowska, L. Lacinska, Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix, J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for permanent of tridiagonal Toeplitz matrices a=1, b=3.
Index entries for linear recurrences with constant coefficients, signature (1,9).
FORMULA
a(n) = (((1+sqrt(37))/2)^(n+1) - ((1-sqrt(37))/2)^(n+1))/sqrt(37).
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*9^k. - Paul Barry, Jul 20 2004
a(n) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)*(1+(-1)^(n-k))*3^(n-k)/2}. - Paul Barry, Aug 28 2005
a(n) = Sum_{k=0..n} A109466(n,k)*(-9)^(n-k). - Philippe Deléham, Oct 26 2008
a(n) = (-703*(1/2-sqrt(37)/2)^n + 199*sqrt(37)*(1/2-sqrt(37)/2)^n-333*(1/2+sqrt(37)/2)^n + 171*sqrt(37)*(1/2+sqrt(37)/2)^n)/(74*(5*sqrt(37)-14)). - Alexander R. Povolotsky, Oct 13 2010
a(n) = Sum_{1<=k<=n+1, k odd} C(n+1,k)*37^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014
G.f.: 1/(1-x-9*x^2). - Philippe Deléham, Feb 19 2020
a(n) = J(n, 9/2), where J(n,x) are the Jacobsthal polynomials. - G. C. Greubel, Feb 18 2020
E.g.f.: exp(x/2)*(sqrt(37)*cosh(sqrt(37)*x/2) + sinh(sqrt(37)*x/2))/sqrt(37). - Stefano Spezia, Feb 19 2020
MAPLE
m:=25; S:=series(1/(1-x-9*x^2), x, m+1): seq(coeff(S, x, j), j=0..m); # G. C. Greubel, Feb 18 2020
MATHEMATICA
CoefficientList[Series[1/(1-x-9*x^2), {x, 0, 25}], x] (* or *) LinearRecurrence[{1, 9}, {1, 1}, 25] (* G. C. Greubel, Apr 30 2017 *)
PROG
(Sage) [lucas_number1(n, 1, -9) for n in range(1, 25)] # Zerinvary Lajos, Apr 22 2009
(Magma) [ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+9*Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 23 2011
(PARI) a(n)=([0, 1; 9, 1]^n*[1; 1])[1, 1] \\ Charles R Greathouse IV, Oct 03 2016
CROSSREFS
Cf. A015443, A015442, A026595, A128099.
KEYWORD
nonn,easy
AUTHOR
Olivier Gérard
EXTENSIONS
Edited by N. J. A. Sloane, Oct 11 2010
STATUS
approved
A015446 Generalized Fibonacci numbers: a(n) = a(n-1) + 10*a(n-2). +20
16
1, 1, 11, 21, 131, 341, 1651, 5061, 21571, 72181, 287891, 1009701, 3888611, 13985621, 52871731, 192727941, 721445251, 2648724661, 9863177171, 36350423781, 134982195491, 498486433301, 1848308388211, 6833172721221 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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, 11*a(n-2) equals the number of 11-colored compositions of n with all parts >=2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011
For a(n) = [(1+(4m+1)^1/2)^n)-(1-(4m+1)^1/2))^n)]/[(2^n)(4m+1)^1/2), a(n)/a(n-1) appears to converge to (1+sqrt(4m+1))/2. Here with m = 10, the numbers in the sequence are congruent with those of the Fibonacci sequence modulo m-1 = 9. For example, F(8) = 21 (Fibonacci) corresponds to a(8) = 5061 (here) because 2+1 and 5+0+1+6 are congruent. - Maleval Francis, Nov 12 2013
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1, 10).
FORMULA
a(n) = (((1+sqrt(41))/2)^(n+1) - ((1-sqrt(41))/2)^(n+1))/sqrt(41).
From Paul Barry, Sep 10 2005: (Start)
a(n) = Sum_{k=0..n} binomial((n+k)/2, k)*(1+(-1)^(n-k))*10^((n-k)/2)/2.
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*10^k. (End)
a(n) is the entry (M^n)_1,1 where the matrix M = [1,2;5,0]. - Simone Severini, Jun 22 2006
a(n) = Sum_{k=0..n} A109466(n,k)*(-10)^(n-k). - Philippe Deléham, Oct 26 2008
G.f.: 1/(1-x-10*x^2). - Colin Barker, Feb 03 2012
a(n) = (sum{1<=k<=n+1, k odd}C(n+1,k)*41^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014
MATHEMATICA
Table[MatrixPower[{{1, 2}, {5, 0}}, n][[1]][[1]], {n, 0, 44}] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2010 *)
CoefficientList[Series[1/(1-x-10*x^2), {x, 0, 50}], x] (* G. C. Greubel, Apr 30 2017 *)
LinearRecurrence[{1, 10}, {1, 1}, 30] (* Harvey P. Dale, Dec 12 2018 *)
PROG
(Sage) [lucas_number1(n, 1, -10) for n in range(1, 25)] # Zerinvary Lajos, Apr 22 2009
(Magma) [ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+10*Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 23 2011
(PARI) a(n)=([1, 2; 5, 0]^n)[1, 1] \\ Charles R Greathouse IV, Mar 09 2014
CROSSREFS
Cf. A015447, A015443.
KEYWORD
nonn,easy
AUTHOR
Olivier Gérard
STATUS
approved
A057089 Scaled Chebyshev U-polynomials evaluated at i*sqrt(6)/2. Generalized Fibonacci sequence. +20
15
1, 6, 42, 288, 1980, 13608, 93528, 642816, 4418064, 30365280, 208700064, 1434392064, 9858552768, 67757668992, 465697330560, 3200729997312, 21998563967232, 151195763787264, 1039165966526976, 7142170381885440 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
a(n) gives the length of the word obtained after n steps with the substitution rule 0->1^6, 1->(1^6)0, starting from 0. The number of 1's and 0's of this word is 6*a(n-1) and 6*a(n-2), resp.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=6, q=6.
Tanya Khovanova, Recursive Sequences
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. Eqs.(39) and (45),rhs, m=6.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (6,6).
FORMULA
a(n) = 6*a(n-1) + 6*a(n-2); a(0)=1, a(1)=6.
a(n) = S(n, i*sqrt(6))*(-i*sqrt(6))^n with S(n, x) := U(n, x/2), Chebyshev's polynomials of the 2nd kind, A049310.
G.f.: 1/(1-6*x-6*x^2).
a(n) = Sum_{k=0..n} 5^k*A063967(n,k). - Philippe Deléham, Nov 03 2006
MATHEMATICA
Join[{a=0, b=1}, Table[c=6*b+6*a; a=b; b=c, {n, 100}]] (* Vladimir Joseph Stephan Orlovsky, Jan 16 2011 *)
LinearRecurrence[{6, 6}, {1, 6}, 40] (* Harvey P. Dale, Nov 05 2011 *)
PROG
(Sage) [lucas_number1(n, 6, -6) for n in range(1, 21)] # Zerinvary Lajos, Apr 24 2009
(Magma) I:=[1, 6]; [n le 2 select I[n] else 6*Self(n-1)+6*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 14 2011
(PARI) x='x+O('x^30); Vec(1/(1-6*x-6*x^2)) \\ G. C. Greubel, Jan 24 2018
CROSSREFS
Cf. A001076, A006190, A007482, A015520, A015521, A015523, A015524, A015525, A015528, A015529, A015530, A015531, A015532, A015533, A015534, A015535, A015536, A015537, A015440, A015441, A015443, A015444, A015445, A015447, A015548, A030195, A053404, A057087, A057088, A083858, A085939, A090017, A091914, A099012, A135030, A135032, A180222, A180226, A180250.
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Aug 11 2000
STATUS
approved
page 1 2 3 4 5 6 7 8 9 10 ... 35

Search completed in 0.432 seconds

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 12 17:59 EDT 2024. Contains 372493 sequences. (Running on oeis4.)