cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 124 results. Next

A001519 a(n) = 3*a(n-1) - a(n-2) for n >= 2, with a(0) = a(1) = 1.

Original entry on oeis.org

1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229, 1346269, 3524578, 9227465, 24157817, 63245986, 165580141, 433494437, 1134903170, 2971215073, 7778742049, 20365011074, 53316291173, 139583862445, 365435296162, 956722026041
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n) and F(-1) = 1.
Number of ordered trees with n+1 edges and height at most 3 (height=number of edges on a maximal path starting at the root). Number of directed column-convex polyominoes of area n+1. Number of nondecreasing Dyck paths of length 2n+2. - Emeric Deutsch, Jul 11 2001
Terms are the solutions x to: 5x^2-4 is a square, with 5x^2-4 in A081071 and sqrt(5x^2-4) in A002878. - Benoit Cloitre, Apr 07 2002
a(0) = a(1) = 1, a(n+1) is the smallest Fibonacci number greater than the n-th partial sum. - Amarnath Murthy, Oct 21 2002
The fractional part of tau*a(n) decreases monotonically to zero. - Benoit Cloitre, Feb 01 2003
Numbers k such that floor(phi^2*k^2) - floor(phi*k)^2 = 1 where phi=(1+sqrt(5))/2. - Benoit Cloitre, Mar 16 2003
Number of leftist horizontally convex polyominoes with area n+1.
Number of 31-avoiding words of length n on alphabet {1,2,3} which do not end in 3. (E.g., at n=3, we have 111, 112, 121, 122, 132, 211, 212, 221, 222, 232, 321, 322 and 332.) See A028859. - Jon Perry, Aug 04 2003
Appears to give all solutions > 1 to the equation: x^2 = ceiling(x*r*floor(x/r)) where r=phi=(1+sqrt(5))/2. - Benoit Cloitre, Feb 24 2004
a(1) = 1, a(2) = 2, then the least number such that the square of any term is just less than the geometric mean of its neighbors. a(n+1)*a(n-1) > a(n)^2. - Amarnath Murthy, Apr 06 2004
All positive integer solutions of Pell equation b(n)^2 - 5*a(n+1)^2 = -4 together with b(n)=A002878(n), n >= 0. - Wolfdieter Lang, Aug 31 2004
Essentially same as Pisot sequence E(2,5).
Number of permutations of [n+1] avoiding 321 and 3412. E.g., a(3) = 13 because the permutations of [4] avoiding 321 and 3412 are 1234, 2134, 1324, 1243, 3124, 2314, 2143, 1423, 1342, 4123, 3142, 2413, 2341. - Bridget Tenner, Aug 15 2005
Number of 1324-avoiding circular permutations on [n+1].
A subset of the Markoff numbers (A002559). - Robert G. Wilson v, Oct 05 2005
(x,y) = (a(n), a(n+1)) are the solutions of x/(yz) + y/(xz) + z/(xy) = 3 with z=1. - Floor van Lamoen, Nov 29 2001
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 1. - Herbert Kociemba, Jun 10 2004
With interpolated zeros, counts closed walks of length n at the start or end node of P_4. a(n) counts closed walks of length 2n at the start or end node of P_4. The sequence 0,1,0,2,0,5,... counts walks of length n between the start and second node of P_4. - Paul Barry, Jan 26 2005
a(n) is the number of ordered trees on n edges containing exactly one non-leaf vertex all of whose children are leaves (every ordered tree must contain at least one such vertex). For example, a(0) = 1 because the root of the tree with no edges is not considered to be a leaf and the condition "all children are leaves" is vacuously satisfied by the root and a(4) = 13 counts all 14 ordered trees on 4 edges (A000108) except (ignore dots)
|..|
.\/.
which has two such vertices. - David Callan, Mar 02 2005
Number of directed column-convex polyominoes of area n. Example: a(2)=2 because we have the 1 X 2 and the 2 X 1 rectangles. - Emeric Deutsch, Jul 31 2006
Same as the number of Kekulé structures in polyphenanthrene in terms of the number of hexagons in extended (1,1)-nanotubes. See Table 1 on page 411 of I. Lukovits and D. Janezic. - Parthasarathy Nambi, Aug 22 2006
Number of free generators of degree n of symmetric polynomials in 3-noncommuting variables. - Mike Zabrocki, Oct 24 2006
Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5)*a(n) + sqrt(5*a(n)^2 - 4))/2) = n for n >= 1. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
Consider a teacher who teaches one student, then he finds he can teach two students while the original student learns to teach a student. And so on with every generation an individual can teach one more student then he could before. a(n) starting at a(2) gives the total number of new students/teachers (see program). - Ben Paul Thurston, Apr 11 2007
The Diophantine equation a(n)=m has a solution (for m >= 1) iff ceiling(arcsinh(sqrt(5)*m/2)/log(phi)) != ceiling(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130255(m)=A130256(m). - Hieronymus Fischer, May 24 2007
a(n+1) = B^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 2=`0`, 5=`00`, 13=`000`, ..., in Wythoff code.
Bisection of the Fibonacci sequence into odd-indexed nonzero terms (1, 2, 5, 13, ...) and even-indexed terms (1, 3, 8, 21, ...) may be represented as row sums of companion triangles A140068 and A140069. - Gary W. Adamson, May 04 2008
a(n) is the number of partitions pi of [n] (in standard increasing form) such that Flatten[pi] is a (2-1-3)-avoiding permutation. Example: a(4)=13 counts all 15 partitions of [4] except 13/24 and 13/2/4. Here "standard increasing form" means the entries are increasing in each block and the blocks are arranged in increasing order of their first entries. Also number that avoid 3-1-2. - David Callan, Jul 22 2008
Let P be the partial sum operator, A000012: (1; 1,1; 1,1,1; ...) and A153463 = M, the partial sum & shift operator. It appears that beginning with any randomly taken sequence S(n), iterates of the operations M * S(n), -> M * ANS, -> P * ANS, etc. (or starting with P) will rapidly converge upon a two-sequence limit cycle of (1, 2, 5, 13, 34, ...) and (1, 1, 3, 8, 21, ...). - Gary W. Adamson, Dec 27 2008
Number of musical compositions of Rhythm-music over a time period of n-1 units. Example: a(4)=13; indeed, denoting by R a rest over a time period of 1 unit and by N[j] a note over a period of j units, we have (writing N for N[1]): NNN, NNR, NRN, RNN, NRR, RNR, RRN, RRR, N[2]R, RN[2], NN[2], N[2]N, N[3] (see the J. Groh reference, pp. 43-48). - Juergen K. Groh (juergen.groh(AT)lhsystems.com), Jan 17 2010
Given an infinite lower triangular matrix M with (1, 2, 3, ...) in every column but the leftmost column shifted upwards one row. Then (1, 2, 5, ...) = lim_{n->infinity} M^n. (Cf. A144257.) - Gary W. Adamson, Feb 18 2010
As a fraction: 8/71 = 0.112676 or 98/9701 = 0.010102051334... (fraction 9/71 or 99/9701 for sequence without initial term). 19/71 or 199/9701 for sequence in reverse. - Mark Dols, May 18 2010
For n >= 1, a(n) is the number of compositions (ordered integer partitions) of 2n-1 into an odd number of odd parts. O.g.f.: (x-x^3)/(1-3x^2+x^4) = A(A(x)) where A(x) = 1/(1-x)-1/(1-x^2).
For n > 0, determinant of the n X n tridiagonal matrix with 1's in the super and subdiagonals, (1,3,3,3,...) in the main diagonal, and the rest zeros. - Gary W. Adamson, Jun 27 2011
The Gi3 sums, see A180662, of the triangles A108299 and A065941 equal the terms of this sequence without a(0). - Johannes W. Meijer, Aug 14 2011
The number of permutations for which length equals reflection length. - Bridget Tenner, Feb 22 2012
Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n+1, with exactly 2 elements of each rank between 0 and 1. (Uniform used in the sense of Retakh, Serconek and Wilson. Graded used in R. Stanley's sense that all maximal chains have the same length.)
HANKEL transform of sequence and the sequence omitting a(0) is the sequence A019590(n). This is the unique sequence with that property. - Michael Somos, May 03 2012
The number of Dyck paths of length 2n and height at most 3. - Ira M. Gessel, Aug 06 2012
Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - R. J. Mathar, Aug 10 2012
Primes in the sequence are 2, 5, 13, 89, 233, 1597, 28657, ... (apparently A005478 without the 3). - R. J. Mathar, May 09 2013
a(n+1) is the sum of rising diagonal of the Pascal triangle written as a square - cf. comments in A085812. E.g., 13 = 1+5+6+1. - John Molokach, Sep 26 2013
a(n) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 1, 1, 1; 0, 1, 1] or [1, 1, 1; 0, 1, 1; 1, 1, 1] or [1, 1, 0; 1, 1, 1; 1, 1, 1] or [1, 0, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker, Feb 04 2014
Except for the initial term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 64 = 0. - Colin Barker, Feb 16 2014
Positive values of x such that there is a y satisfying x^2 - xy - y^2 - 1 = 0. - Ralf Stephan, Jun 30 2014
a(n) is also the number of permutations simultaneously avoiding 231, 312 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl, Aug 07 2014
(1, a(n), a(n+1)), n >= 0, are Markoff triples (see A002559 and Robert G. Wilson v's Oct 05 2005 comment). In the Markoff tree they give one of the outer branches. Proof: a(n)*a(n+1) - 1 = A001906(2*n)^2 = (a(n+1) - a(n))^2 = a(n)^2 + a(n+1)^2 - 2*a(n)*a(n+1), thus 1^2 + a(n)^2 + a(n+1)^2 = 3*a(n)*a(n+1). - Wolfdieter Lang, Jan 30 2015
For n > 0, a(n) is the smallest positive integer not already in the sequence such that a(1) + a(2) + ... + a(n) is a Fibonacci number. - Derek Orr, Jun 01 2015
Number of vertices of degree n-2 (n >= 3) in all Fibonacci cubes, see Klavzar, Mollard, & Petkovsek. - Emeric Deutsch, Jun 22 2015
Except for the first term, this sequence can be generated by Corollary 1 (ii) of Azarian's paper in the references for this sequence. - Mohammad K. Azarian, Jul 02 2015
Precisely the numbers F(n)^k + F(n+1)^k that are also Fibonacci numbers with k > 1, see Luca & Oyono. - Charles R Greathouse IV, Aug 06 2015
a(n) = MA(n) - 2*(-1)^n where MA(n) is exactly the maximum area of a quadrilateral with lengths of sides in order L(n-2), L(n-2), F(n+1), F(n+1) for n > 1 and L(n)=A000032(n). - J. M. Bergot, Jan 28 2016
a(n) is the number of bargraphs of semiperimeter n+1 having no valleys (i.e., convex bargraphs). Equivalently, number of bargraphs of semiperimeter n+1 having exactly 1 peak. Example: a(5) = 34 because among the 35 (=A082582(6)) bargraphs of semiperimeter 6 only the one corresponding to the composition [2,1,2] has a valley. - Emeric Deutsch, Aug 12 2016
Integers k such that the fractional part of k*phi is less than 1/k. See Byszewski link p. 2. - Michel Marcus, Dec 10 2016
Number of words of length n-1 over {0,1,2,3} in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017
With a(0) = 0 this is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Fibonacci sequence A000045. See a Feb 17 2017 comment on A097805. - Wolfdieter Lang, Feb 17 2017
Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) < e(k). [Martinez and Savage, 2.12] - Eric M. Schmidt, Jul 17 2017
Number of permutations of [n] that avoid the patterns 321 and 2341. - Colin Defant, May 11 2018
The sequence solves the following problem: find all the pairs (i,j) such that i divides 1+j^2 and j divides 1+i^2. In fact, the pairs (a(n), a(n+1)), n > 0, are all the solutions. - Tomohiro Yamada, Dec 23 2018
Number of permutations in S_n whose principal order ideals in the Bruhat order are lattices (equivalently, modular, distributive, Boolean lattices). - Bridget Tenner, Jan 16 2020
From Wolfdieter Lang, Mar 30 2020: (Start)
a(n) is the upper left entry of the n-th power of the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602: a(n) = ((M_2)^n)[1,1].
Proof: (M_2)^2 = 3*M + 1_2 (with the 2 X 2 unit matrix 1_2) from the characteristic polynomial of M_2 (see a comment in A322602) and the Cayley-Hamilton theorem. The recurrence M^n = M*M^(n-1) leads to (M_n)^n = S(n, 3)*1_2 + S(n-a, 3)*(M - 3*1_2), for n >= 0, with S(n, 3) = F(2(n+1)) = A001906(n+1). Hence ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3) = a(n) = F(2*n-1) = (1/(2*r+1))*r^(2*n-1)*(1 + (1/r^2)^(2*n-1)), with r = rho(5) = A001622 (golden ratio) (see the first Aug 31 2004 formula, using the recurrence of S(n, 3), and the Michael Somos Oct 28 2002 formula). This proves a conjecture of Gary W. Adamson in A322602.
The ratio a(n)/a(n-1) converges to r^2 = rho(5)^2 = A104457 for n -> infinity (see the a(n) formula in terms of r), which is one of the statements by Gary W. Adamson in A322602. (End)
a(n) is the number of ways to stack coins with a bottom row of n coins such that any coin not on the bottom row touches exactly two coins in the row below, and all the coins on any row are contiguous [Wilf, 2.12]. - Greg Dresden, Jun 29 2020
a(n) is the upper left entry of the (2*n)-th power of the 4 X 4 Jacobi matrix L with L(i,j)=1 if |i-j| = 1 and L(i,j)=0 otherwise. - Michael Shmoish, Aug 29 2020
All positive solutions of the indefinite binary quadratic F(1, -3, 1) := x^2 - 3*x*y + y^2, of discriminant 5, representing -1 (special Markov triples (1, y=x, z=y) if y <= z) are [x(n), y(n)] = [abs(F(2*n+1)), abs(F(2*n-1))], for n = -infinity..+infinity. (F(-n) = (-1)^(n+1)*F(n)). There is only this single family of proper solutions, and there are no improper solutions. [See also the Floor van Lamoen Nov 29 2001 comment, which uses this negative n, and my Jan 30 2015 comment.] - Wolfdieter Lang, Sep 23 2020
These are the denominators of the lower convergents to the golden ratio, tau; they are also the numerators of the upper convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022
a(n+1) is the number of subgraphs of the path graph on n vertices. - Leen Droogendijk, Jun 17 2023
For n > 4, a(n+2) is the number of ways to tile this 3 x n "double-box" shape with squares and dominos (reflections or rotations are counted as distinct tilings). The double-box shape is made up of two horizontal strips of length n, connected by three vertical columns of length 3, and the center column can be located anywhere not touching the two outside columns.
_ _ _ _
|||_|||_|||_|||_|||
|| _ |_| _ _ ||
|||_|||_|||_|||_|||. - Greg Dresden and Ruishan Wu, Aug 25 2024
a(n+1) is the number of integer sequences a_1, ..., a_n such that for any number 1 <= k <= n, (a_1 + ... + a_k)^2 = a_1^3 + ... + a_k^3. - Yifan Xie, Dec 07 2024

Examples

			a(3) = 13: there are 14 ordered trees with 4 edges; all of them, except for the path with 4 edges, have height at most 3.

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 13,15.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 188.
  • N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.
  • GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 92.
  • Jurgen Groh, Computerimprovisation mit Markoffketten und "kognitiven Algorithmen", Studienarbeit, Technische Hochschule Darmstadt, 1987.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 39.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • R. Stanley, Enumerative combinatorics, Vol. 1. Cambridge University Press, Cambridge, 1997, pp. 96-100.
  • H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 41.

Links

Crossrefs

Fibonacci A000045 = union of this sequence and A001906.
Cf. A001653, A055105, A055106, A055107, A074664, A101368, A124292, A124293, A124294, A124295, A140069, A153463, A153266, A153267, A144257, A211216, A002559, A082582.
a(n)= A060920(n, 0).
Row 3 of array A094954.
Equals A001654(n+1) - A001654(n-1), n > 0.
A122367 is another version. Inverse sequences A130255 and A130256. Row sums of A140068, A152251, A153342, A179806, A179745, A213948.
Cf. A001622, A001906, A104457, A153387, A322602.

Programs

  • GAP
    a:=[1,1];; for n in [3..10^2] do a[n]:=3*a[n-1]-a[n-2]; od; a; # Muniru A Asiru, Sep 27 2017
  • Haskell
    a001519 n = a001519_list !! n
a001519_list = 1 : zipWith (-) (tail a001906_list) a001906_list
-- Reinhard Zumkeller, Jan 11 2012
a001519_list = 1 : f a000045_list where f (_:x:xs) = x : f xs
-- Reinhard Zumkeller, Aug 09 2013
  • Magma
    [1] cat [(Lucas(2*n) - Fibonacci(2*n))/2: n in [1..50]]; // Vincenzo Librandi, Jul 02 2014
  • Maple
    A001519:=-(-1+z)/(1-3*z+z**2); # Simon Plouffe in his 1992 dissertation; gives sequence without an initial 1
A001519 := proc(n) option remember: if n=0 then 1 elif n=1 then 1 elif n>=2 then 3*procname(n-1)-procname(n-2) fi: end: seq(A001519(n), n=0..28); # Johannes W. Meijer, Aug 14 2011
  • Mathematica
    Fibonacci /@ (2Range[29] - 1) (* Robert G. Wilson v, Oct 05 2005 *)
LinearRecurrence[{3, -1}, {1, 1}, 29] (* Robert G. Wilson v, Jun 28 2012 *)
a[ n_] := With[{c = Sqrt[5]/2}, ChebyshevT[2 n - 1, c]/c]; (* Michael Somos, Jul 08 2014 *)
CoefficientList[ Series[(1 - 2x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Robert G. Wilson v, Feb 01 2015 *)
  • Maxima
    a[0]:1$ a[1]:1$ a[n]:=3*a[n-1]-a[n-2]$ makelist(a[n],n,0,30); /* Martin Ettl, Nov 15 2012 */
  • PARI
    {a(n) = fibonacci(2*n - 1)}; /* Michael Somos, Jul 19 2003 */
  • PARI
    {a(n) = real( quadgen(5) ^ (2*n))}; /* Michael Somos, Jul 19 2003 */
  • PARI
    {a(n) = subst( poltchebi(n) + poltchebi(n - 1), x, 3/2) * 2/5}; /* Michael Somos, Jul 19 2003 */
  • Sage
    [lucas_number1(n,3,1)-lucas_number1(n-1,3,1) for n in range(30)] # Zerinvary Lajos, Apr 29 2009

Formula

G.f.: (1-2*x)/(1-3*x+x^2).
G.f.: 1 / (1 - x / (1 - x / (1 - x))). - Michael Somos, May 03 2012
a(n) = A001906(n+1) - 2*A001906(n).
a(n) = a(1-n) for all n in Z.
a(n+2) = (a(n+1)^2+1)/a(n) with a(1)=1, a(2)=2. - Benoit Cloitre, Aug 29 2002
a(n) = (phi^(2*n-1) + phi^(1-2*n))/sqrt(5) where phi=(1+sqrt(5))/2. - Michael Somos, Oct 28 2002
a(n) = A007598(n-1) + A007598(n) = A000045(n-1)^2 + A000045(n)^2 = F(n)^2 + F(n+1)^2. - Henry Bottomley, Feb 09 2001
a(n) = Sum_{k=0..n} binomial(n+k, 2*k). - Len Smiley, Dec 09 2001
a(n) ~ (1/5)*sqrt(5)*phi^(2*n+1). - Joe Keane (jgk(AT)jgk.org), May 15 2002
a(n) = Sum_{k=0..n} C(n, k)*F(k+1). - Benoit Cloitre, Sep 03 2002
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i); then q(n, 1)=a(n) (this comment is essentially the same as that of L. Smiley). - Benoit Cloitre, Nov 10 2002
a(n) = (1/2)*(3*a(n-1) + sqrt(5*a(n-1)^2-4)). - Benoit Cloitre, Apr 12 2003
Main diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = max(T(i-1, j) + T(i-1, j-1); T(i-1, j-1) + T(i, j-1)). - Benoit Cloitre, Aug 05 2003
Hankel transform of A002212. E.g., Det([1, 1, 3;1, 3, 10;3, 10, 36]) = 5. - Philippe Deléham, Jan 25 2004
Solutions x > 0 to equation floor(x*r*floor(x/r)) = floor(x/r*floor(x*r)) when r=phi. - Benoit Cloitre, Feb 15 2004
a(n) = Sum_{i=0..n} binomial(n+i, n-i). - Jon Perry, Mar 08 2004
a(n) = S(n-1, 3) - S(n-2, 3) = T(2*n-1, sqrt(5)/2)/(sqrt(5)/2) with S(n, x) = U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first kind. See triangle A049310, resp. A053120. - Wolfdieter Lang, Aug 31 2004
a(n) = ((-1)^(n-1))*S(2*(n-1), i), with the imaginary unit i and S(n, x) = U(n, x/2) Chebyshev's polynomials of the second kind, A049310. - Wolfdieter Lang, Aug 31 2004
a(n) = Sum_{0<=i_1<=i_2<=n} binomial(i_2, i_1)*binomial(n, i_1+i_2). - Benoit Cloitre, Oct 14 2004
a(n) = L(n,3), where L is defined as in A108299; see also A002878 for L(n,-3). - Reinhard Zumkeller, Jun 01 2005
a(n) = a(n-1) + Sum_{i=0..n-1} a(i)*a(n) = F(2*n+1)*Sum_{i=0..n-1} a(i) = F(2*n). - Andras Erszegi (erszegi.andras(AT)chello.hu), Jun 28 2005
The i-th term of the sequence is the entry (1, 1) of the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - Simone Severini, Oct 15 2005
a(n-1) = (1/n)*Sum_{k=0..n} B(2*k)*F(2*n-2*k)*binomial(2*n, 2*k) where B(2*k) is the (2*k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005
a(n) = A055105(n,1) + A055105(n,2) + A055105(n,3) = A055106(n,1) + A055106(n,2). - Mike Zabrocki, Oct 24 2006
a(n) = (2/sqrt(5))*cosh((2n-1)*psi), where psi=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007
a(n) = (phi+1)^n - phi*A001906(n) with phi=(1+sqrt(5))/2. - Reinhard Zumkeller, Nov 22 2007
a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3); a(n) = ((sqrt(5) + 5)/10)*(3/2 + sqrt(5)/2)^(n-2) + ((-sqrt(5) + 5)/10)*(3/2 - sqrt(5)/2)^(n-2). - Antonio Alberto Olivares, Mar 21 2008
a(n) = A147703(n,0). - Philippe Deléham, Nov 29 2008
Sum_{n>=0} atan(1/a(n)) = (3/4)*Pi. - Jaume Oliver Lafont, Feb 27 2009
With X,Y defined as X = ( F(n) F(n+1) ), Y = ( F(n+2) F(n+3) ), where F(n) is the n-th Fibonacci number (A000045), it follows a(n+2) = X.Y', where Y' is the transpose of Y (n >= 0). - K.V.Iyer, Apr 24 2009
From Gary Detlefs, Nov 22 2010: (Start)
a(n) = Fibonacci(2*n+2) mod Fibonacci(2*n), n > 1.
a(n) = (Fibonacci(n-1)^2 + Fibonacci(n)^2 + Fibonacci(2*n-1))/2. (End)
INVERT transform is A166444. First difference is A001906. Partial sums is A055588. Binomial transform is A093129. Binomial transform of A000045(n-1). - Michael Somos, May 03 2012
a(n) = 2^n*f(n;1/2), where f(n;d), n=0,1,...,d, denote the so-called delta-Fibonacci numbers (see Witula et al. papers and comments in A000045). - Roman Witula, Jul 12 2012
a(n) = (Fibonacci(n+2)^2 + Fibonacci(n-3)^2)/5. - Gary Detlefs, Dec 14 2012
G.f.: 1 + x/( Q(0) - x ) where Q(k) = 1 - x/(x*k + 1 )/Q(k+1); (recursively defined continued fraction). - Sergei N. Gladkovskii, Feb 23 2013
G.f.: (1-2*x)*G(0)/(2-3*x), where G(k) = 1 + 1/( 1 - x*(5*k-9)/(x*(5*k-4) - 6/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 19 2013
G.f.: 1 + x*(1-x^2)*Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+2 + 2*x - x^2)/( x*(4*k+4 + 2*x - x^2 ) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 11 2013
G.f.: Q(0,u), where u=x/(1-x), Q(k,u) = 1 + u^2 + (k+2)*u - u*(k+1 + u)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
Sum_{n>=2} 1/(a(n) - 1/a(n)) = 1. Compare with A001906, A007805 and A097843. - Peter Bala, Nov 29 2013
Let F(n) be the n-th Fibonacci number, A000045(n), and L(n) be the n-th Lucas number, A000032(n). Then for n > 0, a(n) = F(n)*L(n-1) + (-1)^n. - Charlie Marion, Jan 01 2014
a(n) = A238731(n,0). - Philippe Deléham, Mar 05 2014
1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - Michael Somos, Jul 08 2014
a(n) = (L(2*n+4) + L(2*n-6))/25 for L(n)=A000032(n). - J. M. Bergot, Dec 30 2014
a(n) = (L(n-1)^2 + L(n)^2)/5 with L(n)=A000032(n). - J. M. Bergot, Dec 31 2014
a(n) = (L(n-2)^2 + L(n+1)^2)/10 with L(n)=A000032(n). - J. M. Bergot, Oct 23 2015
a(n) = 3*F(n-1)^2 + F(n-3)*F(n) - 2*(-1)^n. - J. M. Bergot, Feb 17 2016
a(n) = (F(n-1)*L(n) + F(n)*L(n-1))/2 = (A081714(n-1) + A128534(n))/2. - J. M. Bergot, Mar 22 2016
E.g.f.: (2*exp(sqrt(5)*x) + 3 + sqrt(5))*exp(-x*(sqrt(5)-3)/2)/(5 + sqrt(5)). - Ilya Gutkovskiy, Jul 04 2016
a(n) = ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3), with the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602. For a proof see the Mar 30 2020 comment above. - Wolfdieter Lang, Mar 30 2020
Sum_{n>=1} 1/a(n) = A153387. - Amiram Eldar, Oct 05 2020
a(n+1) = Product_{k=1..n} (1 + 4*cos(2*Pi*k/(2*n + 1))^2). Special case of A099390. - Greg Dresden, Oct 16 2021
a(n+1) = 4^(n+1)*Sum_{k >= n} binomial(2*k,2*n)*(1/5)^(k+1). Cf. A102591. - Peter Bala, Nov 29 2021
a(n) = cosh((2*n-1)*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022
From J. M. Bergot, May 27 2022: (Start)
a(n) = F(n-1)*L(n) - (-1)^n where L(n)=A000032(n) and F(n)=A000045(n).
a(n) = (L(n-1)^2 + L(n-1)*L(n+1))/5 + (-1)^n.
a(n) = 2*(area of a triangle with vertices at (L(n-2), L(n-1)), (F(n), F(n-1)), (L(n), L(n+1))) + 5*(-1)^n for n > 2. (End)
a(n) = A059929(n-1)+A059929(n-2), n>1. - R. J. Mathar, Jul 09 2024

Extensions

Entry revised by N. J. A. Sloane, Aug 24 2006, May 13 2008

A000071 a(n) = Fibonacci(n) - 1.

Original entry on oeis.org

0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of allowable transition rules for passing from one change to the next (on n-1 bells) in the English art of bell-ringing. This is also the number of involutions in the symmetric group S_{n-1} which can be represented as a product of transpositions of consecutive numbers from {1, 2, ..., n-1}. Thus for n = 6 we have a(6) from (12), (12)(34), (12)(45), (23), (23)(45), (34), (45), for instance. See my 1983 Math. Proc. Camb. Phil. Soc. paper. - Arthur T. White, letter to N. J. A. Sloane, Dec 18 1986
Number of permutations p of {1, 2, ..., n-1} such that max|p(i) - i| = 1. Example: a(4) = 2 since only the permutations 132 and 213 of {1, 2, 3} satisfy the given condition. - Emeric Deutsch, Jun 04 2003 [For a(5) = 4 we have 2143, 1324, 2134 and 1243. - Jon Perry, Sep 14 2013]
Number of 001-avoiding binary words of length n-3. a(n) is the number of partitions of {1, ..., n-1} into two blocks in which only 1- or 2-strings of consecutive integers can appear in a block and there is at least one 2-string. E.g., a(6) = 7 because the enumerated partitions of {1, 2, 3, 4, 5} are 124/35, 134/25, 14/235, 13/245, 1245/3, 145/23, 125/34. - Augustine O. Munagi, Apr 11 2005
Numbers for which only one Fibonacci bit-representation is possible and for which the maximal and minimal Fibonacci bit-representations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8 + 3 + 1 = 12. - Casey Mongoven, Mar 19 2006
Beginning with a(2), the "Recamán transform" (see A005132) of the Fibonacci numbers (A000045). - Nick Hobson, Mar 01 2007
Starting with nonzero terms, a(n) gives the row sums of triangle A158950. - Gary W. Adamson, Mar 31 2009
a(n+2) is the minimum number of elements in an AVL tree of height n. - Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010
a(n) is the number of branch nodes in the Fibonacci tree of order n-1. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417). - Emeric Deutsch, Jun 14 2010
a(n+3) is the number of distinct three-strand positive braids of length n (cf. Burckel). - Maxime Bourrigan, Apr 04 2011
a(n+1) is the number of compositions of n with maximal part 2. - Joerg Arndt, May 21 2013
a(n+2) is the number of leafs of great-grandparent DAG (directed acyclic graph) of height n. A great-grandparent DAG of height n is a single node for n = 1; for n > 1 each leaf of ggpDAG(n-1) has two child nodes where pairs of adjacent new nodes are merged into single node if and only if they have disjoint grandparents and same great-grandparent. Consequence: a(n) = 2*a(n-1) - a(n-3). - Hermann Stamm-Wilbrandt, Jul 06 2014
2 and 7 are the only prime numbers in this sequence. - Emmanuel Vantieghem, Oct 01 2014
From Russell Jay Hendel, Mar 15 2015: (Start)
We can establish Gerald McGarvey's conjecture mentioned in the Formula section, however we require n > 4. We need the following 4 prerequisites.
(1) a(n) = F(n) - 1, with {F(n)}A000045.%20(2)%20(Binet%20form)%20F(n)%20=%20(d%5En%20-%20e%5En)/sqrt(5)%20with%20d%20=%20phi%20and%20e%20=%201%20-%20phi,%20de%20=%20-1%20and%20d%20+%20e%20=%201.%20It%20follows%20that%20a(n)%20=%20(d(n)%20-%20e(n))/sqrt(5)%20-%201.%20(3)%20To%20prove%20floor(x)%20=%20y%20is%20equivalent%20to%20proving%20that%20x%20-%20y%20lies%20in%20the%20half-open%20interval%20%5B0,%201).%20(4)%20The%20series%20%7Bs(n)%20=%20c1%20x%5En%20+%20c2%7D">{n >= 1} the Fibonacci numbers A000045. (2) (Binet form) F(n) = (d^n - e^n)/sqrt(5) with d = phi and e = 1 - phi, de = -1 and d + e = 1. It follows that a(n) = (d(n) - e(n))/sqrt(5) - 1. (3) To prove floor(x) = y is equivalent to proving that x - y lies in the half-open interval [0, 1). (4) The series {s(n) = c1 x^n + c2}{n >= 1}, with -1 < x < 0, and c1 and c2 positive constants, converges by oscillation with s(1) < s(3) < s(5) < ... < s(6) < s(4) < s(2). If follows that for any odd n, the open interval (s(n), s(n+1)) contains the subsequence {s(t)}_{t >= n + 2}. Using these prerequisites we can analyze the conjecture.
Using prerequisites (2) and (3) we see we must prove, for all n > 4, that d((d^(n-1) - e^(n-1))/sqrt(5) - 1) - (d^n - e^n)/sqrt(5) + 1 + c lies in the interval [0, 1). But de = -1, implying de^(n-1) = -e^(n-2). It follows that we must equivalently prove (for all n > 4) that E(n, c) = (e^(n-2) + e^n)/sqrt(5) + 1 - d + c = e^(n-2) (e^2 + 1)/sqrt(5) + e + c lies in [0, 1). Clearly, for any particular n, E(n, c) has extrema (maxima, minima) when c = 2*(1-d) and c = (1+d)*(1-d). Therefore, the proof is completed by using prerequisite (4). It suffices to verify E(5, 2*(1-d)) = 0, E(6, 2*(1-d)) = 0.236068, E(5, (1-d)*(1+d)) = 0.618034, E(6, (1-d)*(1+d)) = 0.854102, all lie in [0, 1).
(End)
a(n) can be shown to be the number of distinct nonempty matchings on a path with n vertices. (A matching is a collection of disjoint edges.) - Andrew Penland, Feb 14 2017
Also, for n > 3, the lexicographically earliest sequence of positive integers such that {phi*a(n)} is located strictly between {phi*a(n-1)} and {phi*a(n-2)}. - Ivan Neretin, Mar 23 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) <= e(k). [Martinez and Savage, 2.5]
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) <= e(k) and e(i) != e(k). [Martinez and Savage, 2.5]
(End)
Numbers whose Zeckendorf (A014417) and dual Zeckendorf (A104326) representations are the same: alternating digits of 1 and 0. - Amiram Eldar, Nov 01 2019
a(n+2) is the length of the longest array whose local maximum element can be found in at most n reveals. See link to the puzzle by Alexander S. Kulikov. - Dmitry Kamenetsky, Aug 08 2020
a(n+2) is the number of nonempty subsets of {1,2,...,n} that contain no consecutive elements. For example, the a(6)=7 subsets of {1,2,3,4} are {1}, {2}, {3}, {4}, {1,3}, {1,4} and {2,4}. - Muge Olucoglu, Mar 21 2021
a(n+3) is the number of allowed patterns of length n in the even shift (that is, a(n+3) is the number of binary words of length n in which there are an even number of 0s between any two occurrences of 1). For example, a(7)=12 and the 12 allowed patterns of length 4 in the even shift are 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1100, 1110, 1111. - Zoran Sunic, Apr 06 2022
Conjecture: for k a positive odd integer, the sequence {a(k^n): n >= 1} is a strong divisibility sequence; that is, for n, m >= 1, gcd(a(k^n), a(k^m)) = a(k^gcd(n,m)). - Peter Bala, Dec 05 2022
In general, the sum of a second-order linear recurrence having signature (c,d) will be a third-order recurrence having a signature (c+1,d-c,-d). - Gary Detlefs, Jan 05 2023
a(n) is the number of binary strings of length n-2 whose longest run of 1's is of length 1, for n >= 3. - Félix Balado, Apr 03 2025

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
  • GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 28.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 64.
  • D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Links

Crossrefs

Cf. A000032, A000045, A000119, A001611, A001654, A001911, A005968, A005969.
Cf. A006327, A014417, A054761, A081006, A081007, A081008, A081009, A083368.
Cf. A098531, A098532, A098533, A101220, A104326, A105488, A105489, A119282.
Cf. A128697, A157725, A157726, A157727, A157728, A157729, A158950, A167616.
Cf. A001622, A228074.
Antidiagonal sums of array A004070.
Right-hand column 2 of triangle A011794.
Related to sum of Fibonacci(kn) over n. Cf. A099919, A058038, A138134, A053606.
Subsequence of A226538. Also a subsequence of A061489.

Programs

  • Haskell
    a000071 n = a000071_list !! n
a000071_list = map (subtract 1) $ tail a000045_list
-- Reinhard Zumkeller, May 23 2013
  • Magma
    [Fibonacci(n)-1: n in [1..60]]; // Vincenzo Librandi, Apr 04 2011
  • Maple
    A000071 := proc(n) combinat[fibonacci](n)-1 ; end proc; # R. J. Mathar, Apr 07 2011
a:= n-> (Matrix([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^(n-1))[3, 2]; seq(a(n), n=1..50); # Alois P. Heinz, Jul 24 2008
  • Mathematica
    Fibonacci[Range[40]] - 1 (* or *) LinearRecurrence[{2, 0, -1}, {0, 0, 1}, 40] (* Harvey P. Dale, Aug 23 2013 *)
Join[{0}, Accumulate[Fibonacci[Range[0, 39]]]] (* Alonso del Arte, Oct 22 2017, based on Giorgi Dalakishvili's formula *)
  • PARI
    {a(n) = if( n<1, 0, fibonacci(n)-1)};
  • SageMath
    [fibonacci(n)-1 for n in range(1,60)] # G. C. Greubel, Oct 21 2024

Formula

a(n) = A000045(n) - 1.
a(0) = -1, a(1) = 0; thereafter a(n) = a(n-1) + a(n-2) + 1.
a(n) = A101220(1, 1, n-2), for n > 1.
G.f.: x^3/((1-x-x^2)*(1-x)). - Simon Plouffe in his 1992 dissertation, dropping initial 0's
a(n) = 2*a(n-1) - a(n-3). - R. H. Hardin, Apr 02 2011
Partial sums of Fibonacci numbers. - Wolfdieter Lang
a(n) = -1 + (A*B^n + C*D^n)/10, with A, C = 5 +- 3*sqrt(5), B, D = (1 +- sqrt(5))/2. - Ralf Stephan, Mar 02 2003
a(1) = 0, a(2) = 0, a(3) = 1, then a(n) = ceiling(phi*a(n-1)) where phi is the golden ratio (1 + sqrt(5))/2. - Benoit Cloitre, May 06 2003
Conjecture: for all c such that 2*(2 - Phi) <= c < (2 + Phi)*(2 - Phi) we have a(n) = floor(Phi*a(n-1) + c) for n > 4. - Gerald McGarvey, Jul 22 2004. This is true provided n > 3 is changed to n > 4, see proof in Comments section. - Russell Jay Hendel, Mar 15 2015
a(n) = Sum_{k = 0..floor((n-2)/2)} binomial(n-k-2, k+1). - Paul Barry, Sep 23 2004
a(n+3) = Sum_{k = 0..floor(n/3)} binomial(n-2*k, k)*(-1)^k*2^(n-3*k). - Paul Barry, Oct 20 2004
a(n+1) = Sum(binomial(n-r, r)), r = 1, 2, ... which is the case t = 2 and k = 2 in the general case of t-strings and k blocks: a(n+1, k, t) = Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r = 1, 2, ... - Augustine O. Munagi, Apr 11 2005
a(n) = Sum_{k = 0..n-2} k*Fibonacci(n - k - 3). - Ross La Haye, May 31 2006
a(n) = term (3, 2) in the 3 X 3 matrix [1, 1, 0; 1, 0, 0; 1, 0, 1]^(n-1). - Alois P. Heinz, Jul 24 2008
For n >= 4, a(n) = ceiling(phi*a(n-1)), where phi is the golden ratio. - Vladimir Shevelev, Jul 04 2010
Closed-form without two leading zeros g.f.: 1/(1 - 2*x - x^3); ((5 + 2*sqrt(5))*((1 + sqrt(5))/2)^n + (5 - 2*sqrt(5))*((1 - sqrt(5))/2)^n - 5)/5; closed-form with two leading 0's g.f.: x^2/(1 - 2*x - x^3); ((5 + sqrt(5))*((1 + sqrt(5))/2)^n + (5 - sqrt(5))*((1 - sqrt(5))/2)^n - 10)/10. - Tim Monahan, Jul 10 2011
A000119(a(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
a(n) = A228074(n - 1, 2) for n > 2. - Reinhard Zumkeller, Aug 15 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 - x^2)/( x*(4*k + 4 - x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
A083368(a(n+3)) = n. - Reinhard Zumkeller, Aug 10 2014
E.g.f.: 1 - exp(x) + 2*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5). - Ilya Gutkovskiy, Jun 15 2016
a(n) = A000032(3+n) - 1 mod A000045(3+n). - Mario C. Enriquez, Apr 01 2017
a(n) = Sum_{i=0..n-2} Fibonacci(i). - Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005 [corrected by Doug Bell, Jun 01 2017]
a(n+2) = Sum_{j = 0..floor(n/2)} Sum_{k = 0..j} binomial(n - 2*j, k+1)*binomial(j, k). - Tony Foster III, Sep 08 2017
From Peter Bala, Nov 12 2021: (Start)
a(4*n) = Fibonacci(2*n+1)*Lucas(2*n-1) = A081006(n);
a(4*n+1) = Fibonacci(2*n)*Lucas(2*n+1) = A081007(n);
a(4*n+2) = Fibonacci(2*n)*Lucas(2*n+2) = A081008(n);
a(4*n+3) = Fibonacci(2*n+2)*Lucas(2*n+1) = A081009(n). (End)
G.f.: x^3/((1 - x - x^2)*(1 - x)) = Sum_{n >= 0} (-1)^n * x^(n+3) *( Product_{k = 1..n} (k - x)/Product_{k = 1..n+2} (1 - k*x) ) (a telescoping series). - Peter Bala, May 08 2024
Product_{n>=4} (1 + (-1)^n/a(n)) = 3*phi/4, where phi is the golden ratio (A001622). - Amiram Eldar, Nov 28 2024

Extensions

Edited by N. J. A. Sloane, Apr 04 2011

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

Original entry on oeis.org

1, 0, 2, 1, 6, 7, 22, 36, 89, 168, 377, 756, 1630, 3353, 7110, 14783, 31130, 65016, 136513, 285648, 599041, 1254456, 2629418, 5508097, 11542854, 24183271, 50674318, 106173180, 222470009, 466131960, 976694489, 2046447180, 4287928678, 8984443769, 18825088134
Offset: 1

Views

Author

Clark Kimberling, Jun 26 2011

Keywords

Comments

Polynomial reduction: an introduction
...
We begin with an example. Suppose that p(x) is a polynomial, so that p(x)=(x^2)t(x)+r(x) for some polynomials t(x) and r(x), where r(x) has degree 0 or 1. Replace x^2 by x+1 to get (x+1)t(x)+r(x), which is (x^2)u(x)+v(x) for some u(x) and v(x), where v(x) has degree 0 or 1. Continuing in this manner results in a fixed polynomial w(x) of degree 0 or 1. If p(x)=x^n, then w(x)=x*F(n)+F(n-1), where F=A000045, the sequence of Fibonacci numbers.
In order to generalize, write d(g) for the degree of an arbitrary polynomial g(x), and suppose that p, q, s are polynomials satisfying d(s)s in this manner until reaching w such that d(w)s.
The coefficients of (reduction of p by q->s) comprise a vector of length d(q)-1, so that a sequence p(n,x) of polynomials begets a sequence of vectors, such as (F(n), F(n-1)) in the above example. We are interested in the component sequences (e.g., F(n-1) and F(n)) for various choices of p(n,x).
Following are examples of reduction by x^2->x+1:
n-th Fibonacci p(x) -> A192232+x*A112576
n-th cyclotomic p(x) -> A192233+x*A051258
n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101
n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236
x(x+1)(x+2)...(x+n-1) -> A192238+x*A192239
(x+1)^n -> A001519+x*A001906
(x^2+x+1)^n -> A154626+x*A087635
(x+2)^n -> A020876+x*A030191
(x+3)^n -> A192240+x*A099453
...
Suppose that b=(b(0), b(1),...) is a sequence, and let p(n,x)=b(0)+b(1)x+b(2)x^2+...+b(n)x^n. We define (reduction of sequence b by q->s) to be the vector given by (reduction of p(n,x) by q->s), with components in the order of powers, from 0 up to d(q)-1. For k=0,1,...,d(q)-1, we then have the "k-sequence of (reduction of sequence b by q->s)". Continuing the example, if b is the sequence given by b(k)=1 if k=n and b(k)=0 otherwise, then the 0-sequence of (reduction of b by x^2->x+1) is (F(n-1)), and the 1-sequence is (F(n)).
...
For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):
b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields
0-sequence A166536 and 1-sequence A064831.
b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
0-sequence A166516 and 1-sequence A001654.
b=A000027, natural number sequence (1,2,3,4,...) yields
0-sequence A190062 and 1-sequence A122491.
b=A000032, Lucas sequence (1,3,4,7,11,...) yields
0-sequence A192243 and 1-sequence A192068.
b=A000217, triangular sequence (1,3,6,10,...) yields
0-sequence A192244 and 1-sequence A192245.
b=A000290, squares sequence (1,4,9,16,...) yields
0-sequence A192254 and 1-sequence A192255.
More examples: A192245-A192257.
...
More comments:
(1) If s(n,x)=(reduction of x^n by q->s) and
p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then
(reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)
+...+p(n-1)s(1,x)+p(n)s(0,x). See A192744.
(2) For any polynomial p(x), let P(x)=(reduction of p(x)
by q->s). Then P(r)=p(r) for each zero r of
q(x)-s(x). In particular, if q(x)=x^2 and s(x)=x+1,
then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or
r=(1-sqrt(5))/2.

Examples

			The first four Fibonacci polynomials and their reductions by x^2->x+1 are shown here:
F1(x)=1 -> 1 + 0x
F2(x)=x -> 0 + 1x
F3(x)=x^2+1 -> 2+1x
F4(x)=x^3+2x -> 1+4x
F5(x)=x^4+3x^2+1 -> (x+1)^2+3(x+1)+1 -> 6+6x.
From these, read A192232=(1,0,1,1,6,...) and A112576=(0,1,1,4,6,...).

Links

Crossrefs

Cf. A168561, A192233 - A192240, A192744.
Cf. A206296, A265398, A265399, A265752, A265753.

Programs

  • Mathematica
    q[x_] := x + 1;
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),  x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[FixedPoint[Expand[#1 /. reductionRules] &, Fibonacci[n, x]], {n, 1, 40}];
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}]
  (* A192232 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]
(* A112576 *)
(* Peter J. C. Moses, Jun 25 2011 *)
LinearRecurrence[{1, 3, -1, -1}, {1, 0, 2, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)
  • PARI
    Vec((1-x-x^2)/(1-x-3*x^2+x^3+x^4)+O(x^99)) \\ Charles R Greathouse IV, Jan 08 2013

Formula

Empirical G.f.: -x*(x^2+x-1)/(x^4+x^3-3*x^2-x+1). - Colin Barker, Sep 11 2012
The above formula is correct. - Charles R Greathouse IV, Jan 08 2013
a(n) = A265752(A206296(n)). - Antti Karttunen, Dec 15 2015
a(n) = A112576(n) -A112576(n-1) -A112576(n-2). - R. J. Mathar, Dec 16 2015

Extensions

Example corrected by Clark Kimberling, Dec 18 2017

A007598 Squared Fibonacci numbers: a(n) = F(n)^2 where F = A000045.

Original entry on oeis.org

0, 1, 1, 4, 9, 25, 64, 169, 441, 1156, 3025, 7921, 20736, 54289, 142129, 372100, 974169, 2550409, 6677056, 17480761, 45765225, 119814916, 313679521, 821223649, 2149991424, 5628750625, 14736260449, 38580030724, 101003831721, 264431464441, 692290561600
Offset: 0

Views

Author

N. J. A. Sloane, Robert G. Wilson v

Keywords

Comments

a(n)*(-1)^(n+1) = (2*(1-T(n,-3/2))/5), n>=0, with Chebyshev's polynomials T(n,x) of the first kind, is the r=-1 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found. - Wolfdieter Lang, Oct 18 2004
From Giorgio Balzarotti, Mar 11 2009: (Start)
Determinant of power series with alternate signs of gamma matrix with determinant 1!.
a(n) = Determinant(A - A^2 + A^3 - A^4 + A^5 - ... - (-1)^n*A^n) where A is the submatrix A(1..2,1..2) of the matrix with factorial determinant.
A = [[1,1,1,1,1,1,...], [1,2,1,2,1,2,...], [1,2,3,1,2,3,...], [1,2,3,4,1,2,...], [1,2,3,4,5,1,...], [1,2,3,4,5,6,...], ...]; note: Determinant A(1..n,1..n) = (n-1)!.
a(n) is even with respect to signs of power of A.
See A158039...A158050 for sequence with matrix 2!, 3!, ... (End)
Equals the INVERT transform of (1, 3, 2, 2, 2, ...). Example: a(7) = 169 = (1, 1, 4, 9, 25, 64) dot (2, 2, 2, 2, 3, 1) = (2 + 2 + 8 + 18 + 75 + 64). - Gary W. Adamson, Apr 27 2009
This is a divisibility sequence.
a(n+1)*(-1)^n, n>=0, is the sequence of the alternating row sums of the Riordan triangle A158454. - Wolfdieter Lang, Dec 18 2010
a(n+1) is the number of tilings of a 2 X 2n rectangle with n tetrominoes of any shape, cf. A230031. - Alois P. Heinz, Nov 29 2013
This is the case P1 = 1, P2 = -6, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014
Differences between successive golden rectangle numbers A001654. - Jonathan Sondow, Nov 05 2015
a(n+1) is the number of 2 X n matrices that can be obtained from a 2 X n matrix by moving each element to an adjacent position, horizontally or vertically. This is because F(n+1) is the number of domino tilings of that matrix, therefore with a checkerboard coloring and two domino tilings we can move the black element of each domino of the first tiling to the white element of the same domino and similarly move the white element of each domino of the second tiling to the black element of the same domino. - Fabio Visonà, May 04 2022
In general, squaring the terms of a second-order linear recurrence with signature (c,d) will result in a third-order linear recurrence with signature (c^2+d,(c^2+d)*d,-d^3). - Gary Detlefs, Jan 05 2023

Examples

			G.f. = x + x^2 + 4*x^3 + 9*x^4 + 25*x^5 + 64*x^6 + 169*x^7 + 441*x^8 + ...

References

  • Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 8.
  • Ross Honsberger, Mathematical Gems III, M.A.A., 1985, p. 130.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Richard P. Stanley, Enumerative Combinatorics I, Example 4.7.14, p. 251.

Links

Crossrefs

Cf. A000032, A000045, A001254, A001622, A001654, A047946, A056570, A059260, A061646, A065885, A079291, A080097, A105393.
Bisection of A006498 and A074677. First differences of A001654.
Second row of array A103323.
Half of A175395.

Programs

  • GAP
    List([0..30], n -> Fibonacci(n)^2); # G. C. Greubel, Dec 10 2018
  • Haskell
    a007598 = (^ 2) . a000045  -- Reinhard Zumkeller, Sep 01 2013
  • Magma
    [Fibonacci(n)^2: n in [0..30]]; // Vincenzo Librandi, Apr 14 2011
  • Maple
    with(combinat): seq(fibonacci(n)^2, n=0..27); # Zerinvary Lajos, Sep 21 2007
  • Mathematica
    f[n_] := Fibonacci[n]^2; Array[f, 4!, 0] (* Vladimir Joseph Stephan Orlovsky, Oct 25 2009 *)
LinearRecurrence[{2,2,-1},{0,1,1},41] (* Harvey P. Dale, May 18 2011 *)
  • PARI
    {a(n) = fibonacci(n)^2};
  • PARI
    concat(0, Vec(x*(1-x)/((1+x)*(1-3*x+x^2)) + O(x^30))) \\ Altug Alkan, Nov 06 2015
  • Python
    from sympy import fibonacci
def A007598(n): return fibonacci(n)**2 # Chai Wah Wu, Apr 14 2025
  • Sage
    [(fibonacci(n))^2 for n in range(0, 28)]# Zerinvary Lajos, May 15 2009
  • Sage
    [fibonacci(n)^2 for n in range(30)] # G. C. Greubel, Dec 10 2018

Formula

G.f.: x*(1-x)/((1+x)*(1-3*x+x^2)).
a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3), n > 2. a(0)=0, a(1)=1, a(2)=1.
a(-n) = a(n) for all n in Z.
a(n) = A080097(n-2) + 1.
L.g.f.: 1/5*log((1+3*x+x^2)/(1-6*x+x^2)) = Sum_{n>=0} a(n)/n*x^n; special case of l.g.f. given in A079291. - Joerg Arndt, Apr 13 2011
a(0) = 0, a(1) = 1; a(n) = a(n-1) + Sum(a(n-i)) + k, 0 <= i < n where k = 1 when n is odd, or k = -1 when n is even. E.g., a(2) = 1 = 1 + (1 + 1 + 0) - 1, a(3) = 4 = 1 + (1 + 1 + 0) + 1, a(4) = 9 = 4 + (4 + 1 + 1 + 0) - 1, a(5) = 25 = 9 + (9 + 4 + 1 + 1 + 0) + 1. - Sadrul Habib Chowdhury (adil040(AT)yahoo.com), Mar 02 2004
a(n) = (2*Fibonacci(2*n+1) - Fibonacci(2*n) - 2*(-1)^n)/5. - Ralf Stephan, May 14 2004
a(n) = F(n-1)*F(n+1) - (-1)^n = A059929(n-1) - A033999(n).
Sum_{j=0..2*n} binomial(2*n,j)*a(j) = 5^(n-1)*A005248(n+1) for n >= 1 [P. Stanica]. Sum_{j=0..2*n+1} binomial(2*n+1,j)*a(j) = 5^n*A001519(n+1) [P. Stanica]. - R. J. Mathar, Oct 16 2006
a(n) = (A005248(n) - 2*(-1)^n)/5. - R. J. Mathar, Sep 12 2010
a(n) = (-1)^k*(Fibonacci(n+k)^2-Fibonacci(k)*Fibonacci(2*n+k)), for any k. - Gary Detlefs, Dec 13 2010
a(n) = 3*a(n-1) - a(n-2) + 2*(-1)^(n+1), n > 1. - Gary Detlefs, Dec 20 2010
a(n) = Fibonacci(2*n-2) + a(n-2). - Gary Detlefs, Dec 20 2010
a(n) = (Fibonacci(3*n) - 3*(-1)^n*Fibonacci(n))/(5*Fibonacci(n)), n > 0. - Gary Detlefs, Dec 20 2010
a(n) = (Fibonacci(n)*Fibonacci(n+4) - 3*Fibonacci(n)*Fibonacci(n+1))/2. - Gary Detlefs, Jan 17 2011
a(n) = (((3+sqrt(5))/2)^n + ((3-sqrt(5))/2)^n - 2*(-1)^n)/5; without leading zero we would have a(n) = ((3+sqrt(5))*((3+sqrt(5))/2)^n + (3-sqrt(5))*((3-sqrt(5))/2)^n + 4*(-1)^n)/10. - Tim Monahan, Jul 17 2011
E.g.f.: (exp((phi+1)*x) + exp((2-phi)*x) - 2*exp(-x))/5, with the golden section phi:=(1+sqrt(5))/2. From the Binet-de Moivre formula for F(n). - Wolfdieter Lang, Jan 13 2012
Starting with "1" = triangle A059260 * the Fibonacci sequence as a vector. - Gary W. Adamson, Mar 06 2012
a(0) = 0, a(1) = 1; a(n+1) = (a(n)^(1/2) + a(n-1)^(1/2))^2. - Thomas Ordowski, Jan 06 2013
a(n) + a(n-1) = A001519(n), n > 0. - R. J. Mathar, Mar 19 2014
From Peter Bala, Mar 31 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = 3/2 and beta = -1 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 3/2; 1, 1/2].
a(n) = U(n-1,i/2)*U(n-1,-i/2), where U(n,x) denotes the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
a(n) = (F(n+2)*F(n+3) - L(n)*L(n+1))/3 for F = A000045 and L = A000032. - J. M. Bergot, Jun 02 2014
0 = a(n)*(+a(n) - 2*a(n+1) - 2*a(n+2)) + a(n+1)*(+a(n+1) - 2*a(n+2)) + a(n+2)*(+a(n+2)) for all n in Z. - Michael Somos, Jun 03 2014
(F(n)*b(n+2))^2 + (F(n+1)*b(n-1))^2 = F(2*n+1)^3 = A001519(n+1)^3, with b(n) = a(n) + 2*(-1)^n and F(n) = A000045(n) (see Bruckman link). - Michel Marcus, Jan 24 2015
a(n) = 1/4*( a(n-2) - a(n-1) - a(n+1) + a(n+2) ). The same recurrence holds for A001254. - Peter Bala, Aug 18 2015
a(n) = F(n)*F(n+1) - F(n-1)*F(n). - Jonathan Sondow, Nov 05 2015
For n>2, a(n) = F(n-2)*(3*F(n-1) + F(n-3)) + F(2*n-5). Also, for n>2 a(n)=2*F(n-3)*F(n) + F(2*n-3) -(2)*(-1)^n. - J. M. Bergot, Nov 05 2015
a(n) = (F(n+2)^2 + L(n+1)^2) - 2*F(n+2)*L(n+1). - J. M. Bergot, Nov 08 2015
a(n) = F(n+3)^2 - 4*F(n+1)*F(n+2). - J. M. Bergot, Mar 17 2016
a(n) = (F(n-2)*F(n+2) + F(n-1)*F(n+1))/2. - J. M. Bergot, May 25 2017
4*a(n) = L(n+1)*L(n-1) - F(n+2)*F(n-2), where L = A000032. - Bruno Berselli, Sep 27 2017
a(n) = F(n+k)*F(n-k) + (-1)^(n+k)*a(k), for every integer k >= 0. - Federico Provvedi, Dec 10 2018
From Peter Bala, Nov 19 2019: (Start)
Sum_{n >= 3} 1/(a(n) - 1/a(n)) = 4/9.
Sum_{n >= 3} (-1)^n/(a(n) - 1/a(n)) = (10 - 3*sqrt(5))/18.
Conjecture: Sum_{n >= 1, n != 2*k+1} 1/(a(n) + (-1)^n*a(2*k+1)) = 1/a(4*k+2) for k = 0,1,2,.... (End)
Sum_{n>=1} 1/a(n) = A105393. - Amiram Eldar, Oct 22 2020
Product_{n>=2} (1 + (-1)^n/a(n)) = phi (A001622) (Falcon, 2016, p. 189, eq. (3.1)). - Amiram Eldar, Dec 03 2024

A202453 Fibonacci self-fusion matrix, by antidiagonals.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 5, 5, 6, 5, 5, 8, 8, 9, 9, 8, 8, 13, 13, 15, 15, 15, 13, 13, 21, 21, 24, 24, 24, 24, 21, 21, 34, 34, 39, 39, 40, 39, 39, 34, 34, 55, 55, 63, 63, 64, 64, 63, 63, 55, 55, 89, 89, 102, 102, 104, 104, 104, 102, 102, 89, 89, 144, 144, 165, 165
Offset: 1

Views

Author

Clark Kimberling, Dec 19 2011

Keywords

Comments

The Fibonacci self-fusion matrix, F, is the fusion P**Q, where P and Q are the lower and upper triangular Fibonacci matrices. See A193722 for the definition of fusion of triangular arrays.
Every term F(n,k) of F is a product of two Fibonacci numbers; indeed,
F(n,k)=F(n)*F(k+1) if k is even;
F(n,k)=F(n+1)*F(k) if k is odd.
antidiagonal sums: (1,2,6,12,...), A054454
diagonal (1,2,6,15,...), A001654
diagonal (1,3,9,24,...), A064831
diagonal (2,5,15,39,..), A059840
diagonal (3,8,24,63,..), A080097
diagonal (5,13,39,102,...), A080143
diagonal (8,21,63,165,...), A080144
principal submatrix sums, A202462
All the principal submatrices are invertible, and the terms in the inverses are in {-3,-2,-1,0,1,2,3}.

Examples

			Northwest corner:
1...1....2....3....5....8....13
1...2....3....5....8...13....21
2...3....6....9...15...24....39
3...5....9...15...24...39....63
5...8...15...24...40...64...104

Links

Crossrefs

Cf. A000045, A202451, A202452, A202503 (Fibonacci fission array).

Programs

  • Mathematica
    n = 12;
Q = NestList[Most[Prepend[#, 0]] &, #, Length[#] - 1] &[Table[Fibonacci[k], {k, 1, n}]];
P = Transpose[Q]; F = P.Q;
Flatten[Table[P[[i]][[k + 1 - i]], {k, 1, n}, {i, 1, k}]] (* A202452 as a sequence *)
Flatten[Table[Q[[i]][[k + 1 - i]], {k, 1, n}, {i, 1, k}]] (* A202451 as a sequence *)
Flatten[Table[F[[i]][[k + 1 - i]], {k, 1, n}, {i, 1, k}]] (* A202453 as a sequence *)
TableForm[Q]  (* A202451, upper tri. Fibonacci array *)
TableForm[P]  (* A202452, lower tri. Fibonacci array *)
TableForm[F]  (* A202453, Fibonacci fusion array *)
TableForm[FactorInteger[F]]

Formula

Matrix product P*Q, where P, Q are the lower and upper triangular Fibonacci matrices, A202451 and A202452.

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441, 714, 1156, 1870, 3025, 4895, 7921, 12816, 20736, 33552, 54289, 87841, 142129, 229970, 372100, 602070, 974169, 1576239, 2550409, 4126648, 6677056, 10803704, 17480761, 28284465, 45765225, 74049690, 119814916
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of compositions of n into 1's, 3's and 4's. - Len Smiley, May 08 2001
The sum of any two alternating terms (terms separated by one term) produces a number from the Fibonacci sequence. (e.g. 4+9=13, 9+25=34, 6+15=21, etc.) Taking square roots starting from the first term and every other term after, we get the Fibonacci sequence. - Sreyas Srinivasan (sreyas_srinivasan(AT)hotmail.com), May 02 2002
(1 + x + 2*x^2 + x^3)/(1 - x - x^3 - x^4) = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 15*x^5 + 25*x^6 + 40*x^7 + ... is the g.f. for the number of binary strings of length where neither 101 nor 111 occur. [Lozansky and Rousseau] Or, equivalently, where neither 000 nor 010 occur.
Equivalently, a(n+2) is the number of length-n binary strings with no two set bits with distance 2; see fxtbook link. - Joerg Arndt, Jul 10 2011
a(n) is the number of words written with the letters "a" and "b", with the following restriction: any "a" must be followed by at least two letters, the second of which is a "b". - Bruno Petazzoni (bpetazzoni(AT)ac-creteil.fr), Oct 31 2005. [This is also equivalent to the previous two conditions.]
Let a(0) = 1, then a(n) = partial products of Product_{n>2} (F(n)/F(n-1))^2 = 1*1*2*2*(3/2)*(3/2)*(5/3)*(5/3)*(8/5)*(8/5)*.... E.g., a(7) = 15 = 1*1*1*2*2*(3/2)*(3/2)*(5/3). - Gary W. Adamson, Dec 13 2009
Number of permutations satisfying -k <= p(i) - i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1}. - Vladimir Baltic, Mar 07 2012
The 2-dimensional version, which counts sets of pairs no two of which are separated by graph-distance 2, is A273461. - Gus Wiseman, Nov 27 2019
a(n+1) is the number of multus bitstrings of length n with no runs of 4 ones. - Steven Finch, Mar 25 2020

Examples

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 15*x^7 + 25*x^8 + 40*x^9 + ...
From _Gus Wiseman_, Nov 27 2019: (Start)
The a(2) = 1 through a(7) = 15 subsets with no two elements differing by 2:
  {}  {}   {}     {}     {}     {}
      {1}  {1}    {1}    {1}    {1}
           {2}    {2}    {2}    {2}
           {1,2}  {3}    {3}    {3}
                  {1,2}  {4}    {4}
                  {2,3}  {1,2}  {5}
                         {1,4}  {1,2}
                         {2,3}  {1,4}
                         {3,4}  {1,5}
                                {2,3}
                                {2,5}
                                {3,4}
                                {4,5}
                                {1,2,5}
                                {1,4,5}
(End)

References

  • E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see pp. 157 and 172.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.
Diagonal sums of number triangle A059259.
Cf. A000032, A000034, A000045, A001654, A007598, A209398.
Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.

Programs

  • Haskell
    a006498 n = a006498_list !! n
a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)
   (zipWith (+) (tail a006498_list) a006498_list)
-- Reinhard Zumkeller, Apr 07 2012
  • Magma
    [ n eq 1 select 1 else n eq 2 select 1 else n eq 3 select 1 else n eq 4 select 2 else Self(n-1)+Self(n-3)+ Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 20 2011
  • Mathematica
    LinearRecurrence[{1,0,1,1},{1,1,1,2},50] (* Harvey P. Dale, Jul 13 2011 *)
Table[Fibonacci[Floor[n/2] + 2]^Mod[n, 2]*Fibonacci[Floor[n/2] + 1]^(2 - Mod[n, 2]), {n, 0, 40}] (* David Nacin, Feb 29 2012 *)
a[ n_] := Fibonacci[ Quotient[ n+2, 2]] Fibonacci[ Quotient[ n+3, 2]] (* Michael Somos, Jan 19 2014 *)
Table[Length[Select[Subsets[Range[n]],!MatchQ[#,{_,x_,_,y_,_}/;x+2==y]&]],{n,10}] (* Gus Wiseman, Nov 27 2019 *)
  • PARI
    {a(n) = fibonacci( (n+2)\2 ) * fibonacci( (n+3)\2 )} /* Michael Somos, Mar 10 2004 */
  • PARI
    Vec(1/(1-x-x^3-x^4)+O(x^66))
  • Python
    def a(n, adict={0:1, 1:1, 2:1, 3:2}):
    if n in adict:
        return adict[n]
    adict[n]=a(n-1)+a(n-3)+a(n-4)
    return adict[n] # David Nacin, Mar 07 2012

Formula

G.f.: 1 / ((1 + x^2) * (1 - x - x^2)); a(2*n) = F(n+1)^2, a(2*n - 1) = F(n+1)*F(n). a(n) = a(-4-n) * (-1)^n. - Michael Somos, Mar 10 2004
The g.f. -(1+z+2*z^2+z^3)/((z^2+z-1)*(1+z^2)) for the truncated version 1, 2, 4, 6, 9, 15, 25, 40, ... was given in the Simon Plouffe thesis of 1992. [edited by R. J. Mathar, May 13 2008]
From Vladeta Jovovic, May 03 2002: (Start)
a(n) = round((-(1/5)*sqrt(5) - 1/5)*(-2*1/(-sqrt(5)+1))^n/(-sqrt(5)+1) + ((1/5)*sqrt(5) - 1/5)*(-2*1/( sqrt(5)+1))^n/(sqrt(5)+1)).
G.f.: 1/(1-x-x^2)/(1+x^2). (End)
a(n) = (-i)^n*Sum{k=0..n} U(n-2k, i/2) where i^2=-1. - Paul Barry, Nov 15 2003
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*F(n-2k+1). - Paul Barry, Oct 12 2007
F(floor(n/2) + 2)^(n mod 2)*F(floor(n/2) + 1)^(2 - (n mod 2)) where F(n) is the n-th Fibonacci number. - David Nacin, Feb 29 2012
a(2*n - 1) = A001654(n), a(2*n) = A007598(n+1). - Michael Somos, Mar 10 2004
a(n+1)*a(n+3) = a(n)*a(n+2) + a(n+1)*a(n+2) for all n in Z. - Michael Somos, Jan 19 2014
a(n) = round(1/(1/F(n+2) + 2/F(n+3))), where F(n) = A000045, and 0.5 is rounded to 1. - Richard R. Forberg, Aug 04 2014
5*a(n) = (-1)^floor(n/2)*A000034(n+1) + A000032(n+2). - R. J. Mathar, Sep 16 2017
a(n) = Sum_{j=0..floor(n/3)} Sum_{k=0..j} binomial(n-3j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 18 2017
E.g.f.: (2*cos(x) + sin(x) + exp(x/2)*(3*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024

A010048 Triangle of Fibonomial coefficients, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 3, 1, 1, 5, 15, 15, 5, 1, 1, 8, 40, 60, 40, 8, 1, 1, 13, 104, 260, 260, 104, 13, 1, 1, 21, 273, 1092, 1820, 1092, 273, 21, 1, 1, 34, 714, 4641, 12376, 12376, 4641, 714, 34, 1, 1, 55, 1870, 19635, 85085, 136136, 85085, 19635, 1870, 55, 1
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Conjecture: polynomials with (positive) Fibonomial coefficients are reducible iff n odd > 1. - Ralf Stephan, Oct 29 2004

Examples

			First few rows of the triangle T(n, k) are:
  n\k 0   1    2     3     4      5      6      7     8   9  10
   0: 1
   1: 1   1
   2: 1   1    1
   3: 1   2    2     1
   4: 1   3    6     3     1
   5: 1   5   15    15     5      1
   6: 1   8   40    60    40      8      1
   7: 1  13  104   260   260    104     13      1
   8: 1  21  273  1092  1820   1092    273     21     1
   9: 1  34  714  4641 12376  12376   4641    714    34   1
  10: 1  55 1870 19635 85085 136136  85085  19635  1870  55   1
... - Table extended and reformatted by _Wolfdieter Lang_, Oct 10 2012
For n=7 and k=3, n - k + 1 = 7 - 3 + 1 = 5, so T(7,3) = F(7)*F(6)*F(5)/( F(3)*F(2)*F(1)) = 13*8*5/(2*1*1) = 520/2 = 260. - _Michael B. Porter_, Sep 26 2016

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 15.
  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 84 and 492.

Links

Crossrefs

Cf. A055870 (signed version of triangle).
Columns include: A000045, A001654, A001655, A001656, A001657, A001658, A056565, A056566, A056567.
Sums include: A056569 (row), A181926 (antidiagonal), A181927 (row square-sums).
Cf. A003267 and A003268 (central Fibonomial coefficients), A003150 (Fibonomial Catalan numbers), A144712, A099927, A385732/A385733 (Lucas).

Programs

  • Magma
    Fibonomial:= func< n,k | k eq 0 select 1 else (&*[Fibonacci(n-j+1)/Fibonacci(j): j in [1..k]]) >;
[Fibonomial(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 20 2024
  • Maple
    A010048 := proc(n,k)
    mul(combinat[fibonacci](i),i=n-k+1..n)/mul(combinat[fibonacci](i),i=1..k) ;
end proc:
seq(seq(A010048(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Feb 05 2015
  • Mathematica
    f[n_, k_] := Product[ Fibonacci[n - j + 1]/Fibonacci[j], {j, k}]; Table[ f[n, i], {n, 0, 10}, {i, 0, n}] (* Robert G. Wilson v, Dec 04 2009 *)
Column[Round@Table[GoldenRatio^(k(n-k)) QBinomial[n, k, -1/GoldenRatio^2], {n, 0, 10}, {k, 0, n}], Center] (* Round is equivalent to FullSimplify here, but is much faster - Vladimir Reshetnikov, Sep 25 2016 *)
T[n_, k_] := With[{c = ArcCsch[2] - I Pi/2}, Product[I^j Sinh[c j], {j, k + 1, n}] / Product[I^j Sinh[c j], {j, 1, n - k}]]; Table[Simplify[T[n, k]], {n, 0, 10}, {k, 0, n}] // Flatten  (* Peter Luschny, Jul 08 2025 *)
  • Maxima
    ffib(n):=prod(fib(k),k,1,n);
fibonomial(n,k):=ffib(n)/(ffib(k)*ffib(n-k));
create_list(fibonomial(n,k),n,0,20,k,0,n); /* Emanuele Munarini, Apr 02 2012 */
  • PARI
    T(n, k) = prod(j=0, k-1, fibonacci(n-j))/prod(j=1, k, fibonacci(j));
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Jul 20 2018
  • SageMath
    def fibonomial(n,k): return 1 if k==0 else product(fibonacci(n-j+1)/fibonacci(j) for j in range(1,k+1))
flatten([[fibonomial(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jul 20 2024

Formula

T(n, k) = ((n, k)) = (F(n)*F(n-1)*...*F(n-k+1))/(F(k)*F(k-1)*...*F(1)), F(i) = Fibonacci numbers A000045.
T(n, k) = Fibonacci(n-k-1)*T(n-1, k-1) + Fibonacci(k+1)*T(n-1, k).
T(n, k) = phi^(k*(n-k)) * C(n, k)A001622%20is%20the%20golden%20ratio,%20and%20C(n,%20k)_q%20is%20the%20q-binomial%20coefficient.%20-%20_Vladimir%20Reshetnikov">{-1/phi^2}, where phi = (1+sqrt(5))/2 = A001622 is the golden ratio, and C(n, k)_q is the q-binomial coefficient. - _Vladimir Reshetnikov, Sep 26 2016
G.f. of column k: x^k * exp( Sum_{j>=1} Fibonacci((k+1)*j)/Fibonacci(j) * x^j/j ). - Seiichi Manyama, May 07 2025
T(n, k) = Product_{j=k+1..n} i^j*sinh(c*j) / Product_{j=1..n-k} i^j*sinh(c*j) where c = arccsch(2) - i*Pi/2 and i is the imaginary unit. If you substitute sinh by cosh you get the Lucas triangle A385732/A385733, which is a rational triangle. - Peter Luschny, Jul 08 2025

A045468 Primes congruent to {1, 4} mod 5.

Original entry on oeis.org

11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, 211, 229, 239, 241, 251, 269, 271, 281, 311, 331, 349, 359, 379, 389, 401, 409, 419, 421, 431, 439, 449, 461, 479, 491
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Rational primes that decompose in the field Q(sqrt(5)). - N. J. A. Sloane, Dec 26 2017
These are also primes p that divide Fibonacci(p-1). - Jud McCranie
Primes ending in 1 or 9. - Lekraj Beedassy, Oct 27 2003
Also primes p such that p divides 5^(p-1)/2 - 4^(p-1)/2. - Cino Hilliard, Sep 06 2004
Primes p such that the polynomial x^2-x-1 mod p has 2 distinct zeros. - T. D. Noe, May 02 2005
Same as A038872, apart from the term 5. - R. J. Mathar, Oct 18 2008
Appears to be the primes p such that p^6 mod 210 = 1. - Gary Detlefs, Dec 29 2011
Primes in A047209, also in A090771. - Reinhard Zumkeller, Jan 07 2012
Primes p such that p does not divide Sum_{i=1..p} Fibonacci(i)^2. The sum is A001654(p). - Arkadiusz Wesolowski, Jul 23 2012
Primes congruent to {1, 9} mod 10. Legendre symbol (5, a(n)) = +1. For prime 5 this symbol (5, 5) is set to 0, and (5, prime) = -1 for prime == {3, 7} (mod 10), given in A003631. - Wolfdieter Lang, Mar 05 2021

References

  • Hardy and Wright, An Introduction to the Theory of Numbers, Chap. X, p. 150, Oxford University Press, Fifth edition.

Links

Crossrefs

Cf. A030430, A030433, A064739, A038872, A010051, A003631.
Subsequence of A123976.

Programs

  • Haskell
    a045468 n = a045468_list !! (n-1)
a045468_list = [x | x <- a047209_list, a010051 x == 1]
-- Reinhard Zumkeller, Jan 07 2012
  • Magma
    [ p: p in PrimesUpTo(1000) | p mod 5 in {1,4} ]; // Vincenzo Librandi, Aug 13 2012
  • Maple
    for n from 1 to 500 do if(isprime(n)) and (n^6 mod 210=1) then print(n) fi od;  # Gary Detlefs, Dec 29 2011
  • Mathematica
    lst={};Do[p=Prime[n];If[Mod[p,5]==1||Mod[p,5]==4,AppendTo[lst,p]],{n,6!}];lst (* Vladimir Joseph Stephan Orlovsky, Feb 26 2009 *)
Select[Prime[Range[200]],MemberQ[{1,4},Mod[#,5]]&] (* Vincenzo Librandi, Aug 13 2012 *)
  • PARI
    list(lim)=select(n->n%5==1||n%5==4,primes(primepi(lim))) \\ Charles R Greathouse IV, Jul 25 2011

A003631 Primes congruent to 2 or 3 modulo 5.

Original entry on oeis.org

2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 157, 163, 167, 173, 193, 197, 223, 227, 233, 257, 263, 277, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 383, 397, 433, 443, 457, 463, 467, 487, 503, 523, 547, 557, 563, 577
Offset: 1

Views

Author

N. J. A. Sloane, Mira Bernstein

Keywords

Comments

For n>1, sequence gives primes ending in 3 or 7. - Lekraj Beedassy, Oct 27 2003
Inert rational primes in Q(sqrt 5), or, p is not a square mod 5. [See e.g., Hasse, Legendre symbol (5|p) = -1, Hardy and Wright, Theorem 257 (2), p. 222, and Dodd Appendix B, pp. 128 - 150, primes p < 32771 with (p,0). - Wolfdieter Lang, Jun 16 2021]
Primes for which the period of the Fibonacci sequence mod p divides 2p+2.
Let F(n) be the n-th Fibonacci number for n=1,2,3,... (A000045). F(n) mod p (a prime) generates a periodic sequence. This sequence may be generated as follows: F(p-1)* F(p) mod p = p-1. E.g., p=7: F(6) * F(7) mod 7 = 8 * 13 mod 7 = 6 = p-1. - Louis Mello (Mellols(AT)aol.com), Feb 09 2001
These are also the primes p that divide Fibonacci(p+1). - Jud McCranie
Also primes p such that p divides F(2p+1)-1; such that p divides F(2p+3)-1; such that p divides F(3p+1)-1. - Benoit Cloitre, Sep 05 2003
Primes p such that the polynomial x^2-x-1 mod p has no zeros; i.e., x^2-x-1 is irreducible over the integers mod p. - T. D. Noe, May 02 2005
Primes p such that (1-x^5)/(1-x) is irreducible over GF(p). - Joerg Arndt, Aug 10 2011
Primes p such that p does not divide Sum_{i=1..p-1} Fibonacci(i)^2 = A001654(p-1). - Arkadiusz Wesolowski, Jul 23 2012
The prime 2 and primes p such that p^2 mod 10 = 9. - Richard R. Forberg, Aug 28 2013
Primes p such that 5 divides sigma(p^3), cf. A274397. - M. F. Hasler, Jul 10 2016

References

  • F. W. Dodd, Number Theory in the Quadratic Field with Golden Section Unit, Polygon Publishing House, Passaic, NJ 07055, 1983, Appendix B, pp. 128 - 150.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chap. X, p. 150, Chap. XV, Theorem 257 (2), p. 222, Oxford University Press, Fifth edition.
  • H. Hasse, Number Theory, Springer-Verlag, NY, 1980, p. 498.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • N. N. Vorob'ev, Fibonacci Numbers, Pergamon Press, 1961.

Links

Crossrefs

Primes in A047221.
Cf. A000040.
Cf. A000045, A001654.
Cf. A274397.

Programs

  • Haskell
    a003631 n = a003631_list !! (n-1)
a003631_list = filter ((== 1) . a010051') a047221_list
-- Reinhard Zumkeller, Nov 27 2012, Jul 19 2011
  • Magma
    [ p: p in PrimesUpTo(1000) | p mod 5 in {2, 3} ]; // Vincenzo Librandi, Aug 07 2012
  • Mathematica
    Select[ Prime[Range[106]], MemberQ[{2, 3}, Mod[#, 5]] &] (* Robert G. Wilson v, Sep 12 2011 *)
a[ n_] := If[ n < 1, 0, Module[{c = 0, m = 0}, While[ c < n, If[ PrimeQ[++m] && KroneckerSymbol[5, m] == -1, c++]]; m]]; (* Michael Somos, Nov 24 2018 *)
  • PARI
    list(lim)=select(n->n%5==2||n%5==3,primes(primepi(lim))) \\ Charles R Greathouse IV, Jul 25 2011
  • PARI
    {a(n) = if( n < 1, 0, my(c ,m); while( c < n, if( isprime(m++) && kronecker(5, m) == -1, c++)); m)}; /* Michael Somos, Aug 14 2012 */

Formula

a(n) ~ 2n log n. - Charles R Greathouse IV, Jun 19 2017

A055870 Signed Fibonomial triangle.

Original entry on oeis.org

1, 1, -1, 1, -1, -1, 1, -2, -2, 1, 1, -3, -6, 3, 1, 1, -5, -15, 15, 5, -1, 1, -8, -40, 60, 40, -8, -1, 1, -13, -104, 260, 260, -104, -13, 1, 1, -21, -273, 1092, 1820, -1092, -273, 21, 1, 1, -34, -714, 4641, 12376, -12376, -4641, 714, 34, -1, 1, -55, -1870, 19635, 85085, -136136, -85085, 19635, 1870, -55, -1
Offset: 0

Views

Author

Wolfdieter Lang, Jul 10 2000

Keywords

Comments

Row n+1 (n >= 1) of the signed triangle lists the coefficients of the recursion relation for the n-th power of Fibonacci numbers A000045: Sum_{m=0..n+1} T(n+1,m)*(Fibonacci(k-m))^n = 0, k >= n+1; inputs: (Fibonacci(k))^n, k=0..n.
The inverse of the row polynomial p(n,x) := Sum_{m=0..n} T(n,m)*x^m is the g.f. for the column m=n-1 of the Fibonomial triangle A010048.
The row polynomials p(n,x) factorize according to p(n,x) = G(n-1)*p(n-2,-x), with inputs p(0,x)= 1, p(1,x)= 1-x and G(n):= 1 - A000032(n)*x + (-1)^n*x^2. (Derived from Riordan's result and Knuth's exercise).
The row polynomials are the characteristic polynomials of product of the binomial matrix binomial(i,j) and the exchange matrix J_n (matrix with 1's on the antidiagonal, 0 elsewhere). - Paul Barry, Oct 05 2004

Examples

			Row polynomial for n=4: p(4,x) = 1-3*x-6*x^2+3*x^3+x^4 = (1+x-x^2)*(1-4*x-x^2). 1/p(4,x) is G.f. for A010048(n+3,3), n >= 0: {1,3,15,60,...} = A001655(n).
For n=3: 1*(Fibonacci(k))^3 - 3*(Fibonacci(k-1))^3 - 6*(Fibonacci(k-2))^3 + 3*(Fibonacci(k-3))^3 + 1*(Fibonacci(k-4))^3 = 0, k >= 4; inputs: (Fibonacci(k))^3, k=0..3.
The triangle begins:
  n\m 0   1     2    3     4      5     6    7   8   9
  0   1
  1   1  -1
  2   1  -1    -1
  3   1  -2    -2    1
  4   1  -3    -6    3     1
  5   1  -5   -15   15     5     -1
  6   1  -8   -40   60    40     -8    -1
  7   1 -13  -104  260   260   -104   -13    1
  8   1 -21  -273 1092  1820  -1092  -273   21   1
  9   1 -34  -714 4641 12376 -12376 -4641  714  34  -1
  ... [_Wolfdieter Lang_, Aug 06 2012; a(7,1) corrected, Oct 10 2012]

References

  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 1, pp. 84-5 and 492.

Links

Crossrefs

Cf. A000032, A000045, A001654, A001655, A001656, A001657, A001658, A010048, A051159, A056565, A056566, A056567.
Sums include: A055871 (signed row), A056569 (row).
Central column: A003268.
Cf. A383715.

Programs

  • Magma
    Fibonomial:= func< n,k | k eq 0 select 1 else (&*[Fibonacci(n-j+1)/Fibonacci(j): j in [1..k]]) >;
[(-1)^Floor((k+1)/2)*Fibonomial(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 20 2024
  • Maple
    A055870 := proc(n,k)
    (-1)^floor((k+1)/2)*A010048(n,k) ;
end proc: # R. J. Mathar, Jun 14 2015
  • Mathematica
    T[n_, m_]:= {1,-1,-1,1}[[Mod[m,4] + 1]] * Product[ Fibonacci[n-j+1]/Fibonacci[j], {j, m}];
Table[T[n, m], {n, 0, 10}, {m, 0, n}]//Flatten (* Jean-François Alcover, Jul 05 2013 *)
  • SageMath
    def fibonomial(n,k): return 1 if k==0 else product(fibonacci(n-j+1)/fibonacci(j) for j in range(1,k+1))
flatten([[(-1)^((k+1)//2)*fibonomial(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jul 20 2024

Formula

T(n, m) = (-1)^floor((m+1)/2)*A010048(n, m), where A010048(n, m) := fibonomial(n, m).
G.f. for column m: (-1)^floor((m+1)/2)*x^m/p(m+1, x) with the row polynomial of the (signed) triangle: p(n, x) := Sum_{m=0..n} T(n, m)*x^m.
Sum_{k=0..n} T(n,k) * x^k = exp( -Sum_{k>=1} Fibonacci(n*k)/Fibonacci(k) * x^k/k ). - Seiichi Manyama, May 07 2025
Previous Showing 11-20 of 124 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.