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.

Showing 1-10 of 16 results. Next

A001906 F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).

Original entry on oeis.org

0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717, 591286729879, 1548008755920
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Apart from initial term, same as A088305.
Second column of array A102310 and of A028412.
Numbers k such that 5*k^2 + 4 is a square. - Gregory V. Richardson, Oct 13 2002
Apart from initial terms, also Pisot sequences E(3,8), P(3,8), T(3,8). See A008776 for definitions of Pisot sequences.
Binomial transform of A000045. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 in the path graph P_4 from one end to the other one. Example: a(2)=3 because in the path ABCD we have ABABCD, ABCBCD and ABCDCD. - Emeric Deutsch, Apr 02 2004
Simplest example of a second-order recurrence with the sixth term a square.
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) = 3. - Lekraj Beedassy, Jun 11 2004
a(n) (for n > 0) is the smallest positive integer that cannot be created by summing at most n values chosen among the previous terms (with repeats allowed). - Andrew Weimholt, Jul 20 2004
All nonnegative integer solutions of Pell equation b(n)^2 - 5*a(n)^2 = +4 together with b(n) = A005248(n), n >= 0. - Wolfdieter Lang, Aug 31 2004
a(n+1) is a Chebyshev transform of 3^n (A000244), where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - Paul Barry, Oct 25 2004
a(n) is the number of distinct products of matrices A, B, C, in (A+B+C)^n where commutator [A,B] = 0 but C does not commute with A or B. - Paul D. Hanna and Max Alekseyev, Feb 01 2006
Number of binary words with exactly k-1 strictly increasing runs. Example: a(3)=F(6)=8 because we have 0|0,1|0,1|1,0|01,01|0,1|01,01|1 and 01|01. Column sums of A119900. - Emeric Deutsch, Jul 23 2006
See Table 1 on page 411 of Lukovits and Janezic paper. - Parthasarathy Nambi, Aug 22 2006
Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5) a(n) + sqrt(5 a(n)^2 + 4))/2) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
[1,3,8,21,55,144,...] is the Hankel transform of [1,1,4,17,75,339,1558,...](see A026378). - Philippe Deléham, Apr 13 2007
The Diophantine equation a(n) = m has a solution (for m >= 1) if and only if floor(arcsinh(sqrt(5)*m/2)/log(phi)) <> floor(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130259(m) = A130260(m). - Hieronymus Fischer, May 25 2007
a(n+1) = AB^(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., 1=`1`, 3=`10`, 8=`100`, 21=`1000`, ..., in Wythoff code.
Equals row sums of triangles A140069, A140736 and A140737. - Gary W. Adamson, May 25 2008
a(n) is also the number of idempotent order-preserving partial transformations (of an n-element chain) of width n (width(alpha) = max(Im(alpha))). Equivalently, it is the number of idempotent order-preserving full transformations (of an n-element chain). - Abdullahi Umar, Sep 08 2008
a(n) is the number of ways that a string of 0,1 and 2 of size (n-1) can be arranged with no 12-pairs. - Udita Katugampola, Sep 24 2008
Starting with offset 1 = row sums of triangle A175011. - Gary W. Adamson, Apr 03 2010
As a fraction: 1/71 = 0.01408450... or 1/9701 = 0.0001030821.... - Mark Dols, May 18 2010
Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8). - Dylon Hamilton, Jun 20 2010, Geoffrey Critzer, Joerg Arndt, Dec 06 2010
a(n) relates to regular polygons with even numbers of edges such that Product_{k=1..(n-2)/2} (1 + 4*cos^2 k*Pi/n) = even-indexed Fibonacci numbers with a(n) relating to the 2*n-gons. The constants as products = roots to even-indexed rows of triangle A152063. For example: a(5) = 55 satisfies the product formula relating to the 10-gon. - Gary W. Adamson, Aug 15 2010
Alternatively, product of roots to x^4 - 12x^3 + 51x^2 - 90x + 55, (10th row of triangle A152063) = (4.618...)*(3.618...)*(2.381...)*(1.381...) = 55. - Gary W. Adamson, Aug 15 2010
a(n) is the number of generalized compositions of n when there are i different types of i, (i=1,2,...). - Milan Janjic, Aug 26 2010
Starting with "1" = row sums of triangle A180339, and eigensequence of triangle A137710. - Gary W. Adamson, Aug 28 2010
a(2) = 3 is the only prime.
Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n > 0, with exactly 2 elements of each rank level above 0. (Uniform used in the sense of Retakh, Serconek, and Wilson. Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 13 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
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 1. - Michel Lagneau, Feb 01 2014
For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,2}. - Milan Janjic, Jan 25 2015
With a(0) = 0, for n > 1, a(n) is the smallest number not already in the sequence such that a(n)^2 - a(n-1)^2 is a Fibonacci number. - Derek Orr, Jun 08 2015
Let T be the tree generated by these rules: 0 is in T, and if p is in T, then p + 1 is in T and x*p is in T and y*p is in T. The n-th generation of T consists of A001906(n) polynomials, for n >= 0. - Clark Kimberling, Nov 24 2015
For n > 0, a(n) = exactly the maximum area of a quadrilateral with sides in order of lengths F(n), F(n), L(n), and L(n) with L(n)=A000032(n). - J. M. Bergot, Jan 20 2016
a(n) = twice the area of a triangle with vertices at (L(n+1), L(n+2)), (F(n+1), F(n+1)), and (L(n+2), L(n+1)), with L(n)=A000032(n). - J. M. Bergot, Apr 20 2016
Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S - S^2; see A291000. - Clark Kimberling, Aug 24 2017
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a sequence of n triangles, where adjacent triangles share an edge. - Kevin Long, May 07 2018
a(n) is the number of ways to partition [n] such that each block is a run of consecutive numbers, and each block has a fixed point, e.g., for n=3, 12|3 with 1 and 3 as fixed points is valid, but 13|2 is not valid as 1 and 3 do not form a run. Consequently, a(n) also counts the spanning trees of the graph given by taking a path with n vertices and adding another vertex adjacent to all of them. - Kevin Long, May 11 2018
From Wolfdieter Lang, May 31 2018: (Start)
The preceding comment can be paraphrased as follows. a(n) is the row sum of the array A305309 for n >= 1. The array A305309(n, k) gives the sum of the products of the block lengths of the set partition of [n] := {1, 2, ..., n} with A048996(n, k) blocks of consecutive numbers, corresponding to the compositions obtained from the k-th partition of n in Abramowitz-Stegun order. See the comments and examples at A305309.
{a(n)} also gives the infinite sequence of nonnegative numbers k for which k * ||k*phi|| < 1/sqrt(5), where the irrational number phi = A001622 (golden section), and ||x|| is the absolute value of the difference between x and the nearest integer. See, e.g., the Havil reference, pp. 171-172. (End)
This Chebyshev sequence a(n) = S(n-1, 3) (see a formula below) is related to the bisection of Fibonacci sequences {F(a,b;n)}{n>=0} with input F(a,b;0) = a and F(a,b;1) = b, by F(a,b;2*k) = (a+b)*S(k-1, 3) - a*S(k-2, 3) and F(a,b;2*k+1) = b*S(k, 3) + (a-b)*S(k-1, 3), for k >= 0, and S(-2, 3) = -1. Proof via the o.g.f.s GFeven(a,b,t) = (a - t*(2*a-b))/(1 - 3*t + t^2) and GFodd(a,b,t) = (b + t*(a-b))/(1 - 3*t + t^2). The special case a = 0, b = 1 gives back F(2*k) = S(k-1, 3) = a(k). - _Wolfdieter Lang, Jun 07 2019
a(n) is the number of tilings of two n X 1 rectangles joined orthogonally at a common end-square (so to have 2n-1 squares in a right-angle V shape) with only 1 X 1 and 2 X 1 tiles. This is a consequence of F(2n) = F(n+1)*F(n) + F(n)*F(n-1). - Nathaniel Gregg, Oct 10 2021
These are the denominators of the upper convergents to the golden ratio, tau; they are also the numerators of the lower convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022
For n > 1, a(n) is the smallest Fibonacci number of unit equilateral triangle tiles needed to make an isosceles trapezoid of height F(n) triangles. - Kiran Ananthpur Bacche, Sep 01 2024

Examples

			G.f. = x + 3*x^2 + 8*x^3 + 21*x^4 + 55*x^5 + 144*x^6 + 377*x^7 + 987*x^8 + ...
a(3) = 8 because there are exactly 8 idempotent order-preserving full transformations on a 3-element chain, namely: (1,2,3)->(1,1,1),(1,2,3)->(2,2,2),(1,2,3)->(3,3,3),(1,2,3)->(1,1,3),(1,2,3)->(2,2,3),(1,2,3)->(1,2,2),(1,2,3)->(1,3,3),(1,2,3)->(1,2,3)-mappings are coordinate-wise. - _Abdullahi Umar_, Sep 08 2008

References

  • Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
  • Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 2,5,6,14,33,55.
  • R. J. Douglas, Tournaments that admit exactly one Hamiltonian cycle, Proc. London Math. Soc., 21 (1970), 716-730.
  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • A. Gerardin, Reply to Query 4389, L'Intermédiaire des Mathématiciens, 22 (1915), 23.
  • Julian Havil, The Irrationals, Princeton University Press, Princeton and Oxford, 2012, pp. 171-172.
  • Howie, J. M. Combinatorial and probabilistic results in transformation semigroups. Words, languages and combinatorics, II (Kyoto, 1992), 200--206, World Sci. Publ., River Edge, NJ, (1994).
  • Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving full transformations. Semigroup Forum 72 (2006), 51-62.
  • I. Lukovits, A. Graovac, E. Kalman, G. Kaptay, P. Nagy, S. Nikolic, J. Sytchev and N. Trinajstich, "Nanotubes: Number of Kekulé Structures and Aromaticity", J. Chem. Inf. Comput. Sci, vol. 43 (2003), pp. 609-614. See Equation 6 on page 611.
  • T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
  • H. Mathieu, Query 3932, L'Intermédiaire des Mathématiciens, 18 (1911), 222. - N. J. A. Sloane, Mar 08 2022
  • I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 101.
  • Paulo Ribenboim, Primes in Lucas sequences (Chap 4), in 'My Numbers, My Friends', Springer-Verlag 2000 NY, page 27.
  • 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.

Links

Crossrefs

Fibonacci A000045 = union of this sequence and A001519.
Cf. A000041, A000032, A001622, A048996, A052529, A055991, A078812, A305309, A058038 (pairwise products), A153386.
Inverse sequences A130259 and A130260.
Cf. A033888, A033890, A249450, A344212.

Programs

  • Haskell
    a001906 n = a001906_list !! n
a001906_list =
   0 : 1 : zipWith (-) (map (* 3) $ tail a001906_list) a001906_list
-- Reinhard Zumkeller, Oct 03 2011
  • Magma
    [Fibonacci(2*n): n in [0..30]]; // Vincenzo Librandi, Sep 10 2014
  • Maple
    with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 1), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+1), n=0..28); # Zerinvary Lajos, Apr 04 2009
H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
a := n -> `if`(n = 0, 0, H(2*n, 1, 1/2)):
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 03 2019
A001906 := proc(n)
    combinat[fibonacci](2*n) ;
end proc:
seq(A001906(n),n=0..20) ; # R. J. Mathar, Jan 11 2024
  • Mathematica
    f[n_] := Fibonacci[2n]; Array[f, 28, 0] (* or *)
LinearRecurrence[{3, -1}, {0, 1}, 28] (* Robert G. Wilson v, Jul 13 2011 *)
Take[Fibonacci[Range[0,60]],{1,-1,2}] (* Harvey P. Dale, May 23 2012 *)
Table[ ChebyshevU[n-1, 3/2], {n, 0, 30}] (* Jean-François Alcover, Jan 25 2013, after Michael Somos *)
CoefficientList[Series[(x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Sep 10 2014 *)
  • Maxima
    makelist(fib(2*n),n,0,30); /* Martin Ettl, Oct 21 2012 */
  • MuPAD
    numlib::fibonacci(2*n) $ n = 0..35; // Zerinvary Lajos, May 09 2008
  • PARI
    {a(n) = fibonacci(2*n)}; /* Michael Somos, Dec 06 2002 */
  • PARI
    {a(n) = subst( poltchebi(n+1)*4 - poltchebi(n)*6, x, 3/2)/5}; /* Michael Somos, Dec 06 2002 */
  • PARI
    {a(n) = polchebyshev( n-1, 2, 3/2)}; /* Michael Somos Jun 18 2011 */
  • PARI
    Vec(x/(1-3*x+x^2)+O(x^99)) \\ Charles R Greathouse IV, Oct 24 2012
  • Python
    def a(n, adict={0:0, 1:1}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1) - a(n-2)
    return adict[n] # David Nacin, Mar 04 2012
  • Sage
    [lucas_number1(n,3,1) for n in range(27)] # Zerinvary Lajos, Jun 25 2008
  • Sage
    [fibonacci(2*n) for n in range(0, 28)] # Zerinvary Lajos, May 15 2009

Formula

G.f.: x / (1 - 3*x + x^2). - Simon Plouffe in his 1992 dissertation
a(n) = 3*a(n-1) - a(n-2) = A000045(2*n).
a(n) = -a(-n).
a(n) = A060921(n-1, 0), n >= 1.
a(n) = sqrt((A005248(n)^2 - 4)/5).
a(n) = A007598(n) - A007598(n-2), n > 1.
a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2.
Invert transform of natural numbers: a(n) = Sum_{k=1..n} k*a(n-k), a(0) = 1. - Vladeta Jovovic, Apr 27 2001
a(n) = S(n-1, 3) with S(n, x) = U(n, x/2) Chebyshev's polynomials of the 2nd kind, see A049310.
a(n) = Sum_{k=0..n} binomial(n, k)*F(k). - Benoit Cloitre, Sep 03 2002
Limit_{n->infinity} a(n)/a(n-1) = 1 + phi = (3 + sqrt(5))/2. This sequence includes all of the elements of A033888 combined with A033890.
a(0)=0, a(1)=1, a(2)=3, a(n)*a(n-2) + 1 = a(n-1)^2. - Benoit Cloitre, Dec 06 2002
a(n) = n + Sum_{k=0..n-1} Sum_{i=0..k} a(i) = n + A054452(n). - Benoit Cloitre, Jan 26 2003
a(n) = Sum_{k=1..n} binomial(n+k-1, n-k). - Vladeta Jovovic, Mar 23 2003
E.g.f.: (2/sqrt(5))*exp(3*x/2)*sinh(sqrt(5)*x/2). - Paul Barry, Apr 11 2003
Second 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
a(n) = F(n)*L(n) = A000045(n)*A000032(n). - Lekraj Beedassy, Nov 17 2003
F(2n+2) = 1, 3, 8, ... is the binomial transform of F(n+2). - Paul Barry, Apr 24 2004
Partial sums of A001519(n). - Lekraj Beedassy, Jun 11 2004
a(n) = Sum_{i=0..n-1} binomial(2*n-1-i, i)*5^(n-i-1)*(-1)^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n) = Sum_{k=0..n} binomial(n+k, n-k-1) = Sum_{k=0..n} binomial(n+k, 2k+1).
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*3^(n-2*k). - Paul Barry, Oct 25 2004
a(n) = (n*L(n) - F(n))/5 = Sum_{k=0..n-1} (-1)^n*L(2*n-2*k-1).
The i-th term of the sequence is the entry (1, 2) in the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - Simone Severini, Oct 15 2005
Computation suggests that this sequence is the Hankel transform of A005807. The Hankel transform of {a(n)} is Det[{{a(1), ..., a(n)}, {a(2), ..., a(n+1)}, ..., {a(n), ..., a(2n-1)}}]. - John W. Layman, Jul 21 2000
a(n+1) = (A005248(n+1) - A001519(n))/2. - Creighton Dement, Aug 15 2004
a(n+1) = Sum_{i=0..n} Sum_{j=0..n} binomial(n-i, j)*binomial(n-j, i). - N. J. A. Sloane, Feb 20 2005
a(n) = (2/sqrt(5))*sinh(2*n*psi), where psi:=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007
a(n) = ((phi+1)^n - A001519(n))/phi with phi=(1+sqrt(5))/2. - Reinhard Zumkeller, Nov 22 2007
Row sums of triangle A135871. - Gary W. Adamson, Dec 02 2007
a(n)^2 = Sum_{k=1..n} a(2*k-1). This is a property of any sequence S(n) such that S(n) = B*S(n-1) - S(n-2) with S(0) = 0 and S(1) = 1 including {0,1,2,3,...} where B = 2. - Kenneth J Ramsey, Mar 23 2008
a(n) = 1/sqrt(5)*(phi^(2*n+2) - phi^(-2*n-2)), where phi = (1+sqrt(5))/2, the golden ratio. - Udita Katugampola (SIU), Sep 24 2008
If p[i] = i and if A is Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i<=j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, May 02 2010
If p[i] = Stirling2(i,2) and if A is the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i<=j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = det(A). - Milan Janjic, May 08 2010
a(n) = F(2*n+10) mod F(2*n+5).
a(n) = 1 + a(n-1) + Sum_{i=1..n-1} a(i), with a(0)=0. - Gary W. Adamson, Feb 19 2011
a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 3's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011
a(n), n > 1 is equal to the determinant of an (n-x) X (n-1) tridiagonal matrix with 3's in the main diagonal, 1's in the super and subdiagonals, and the rest 0's. - Gary W. Adamson, Jun 27 2011
a(n) = b such that Integral_{x=0..Pi/2} sin(n*x)/(3/2-cos(x)) dx = c + b*log(3). - Francesco Daddi, Aug 01 2011
a(n+1) = Sum_{k=0..n} A101950(n,k)*2^k. - Philippe Deléham, Feb 10 2012
G.f.: A(x) = x/(1-3*x+x^2) = G(0)/sqrt(5); where G(k)= 1 -(a^k)/(1 - b*x/(b*x - 2*(a^k)/G(k+1))), a = (7-3*sqrt(5))/2, b = 3+sqrt(5), if |x|<(3-sqrt(5))/2 = 0.3819660...; (continued fraction 3 kind, 3-step ). - Sergei N. Gladkovskii, Jun 25 2012
a(n) = 2^n*b(n;1/2) = -b(n;-1), where b(n;d), n=0,1,...,d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also Witula's et al. papers). - Roman Witula, Jul 12 2012
Product_{n>=1} (1 + 1/a(n)) = 1 + sqrt(5). - Peter Bala, Dec 23 2012
Product_{n>=2} (1 - 1/a(n)) = (1/6)*(1 + sqrt(5)). - Peter Bala, Dec 23 2012
G.f.: x/(1-2*x) + x^2/(1-2*x)/(Q(0)-x) where Q(k) = 1 - x/(x*k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Feb 23 2013
G.f.: G(0)/2 - 1, where G(k) = 1 + 1/( 1 - x/(x + (1-x)^2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013
G.f.: 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 17 2013
Sum_{n>=1} 1/(a(n) + 1/a(n)) = 1. Compare with A001519, A049660 and A049670. - Peter Bala, Nov 29 2013
a(n) = U(n-1,3/2) where U(n-1,x) is Chebyshev polynomial of the second kind. - Milan Janjic, Jan 25 2015
The o.g.f. A(x) satisfies A(x) + A(-x) + 6*A(x)*A(-x) = 0. The o.g.f. for A004187 equals -A(sqrt(x))*A(-sqrt(x)). - Peter Bala, Apr 02 2015
For n > 1, a(n) = (3*F(n+1)^2 + 2*F(n-2)*F(n+1) - F(n-2)^2)/4. - J. M. Bergot, Feb 16 2016
For n > 3, a(n) = floor(MA) - 4 for n even and floor(MA) + 5 for n odd. MA is the maximum area of a quadrilateral with lengths of sides in order L(n), L(n), F(n-3), F(n+3), with L(n)=A000032(n). The ratio of the longer diagonal to the shorter approaches 5/3. - J. M. Bergot, Feb 16 2016
a(n+1) = Sum_{j=0..n} Sum_{k=0..j} binomial(n-j,k)*binomial(j,k)*2^(j-k). - Tony Foster III, Sep 18 2017
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = Sum_{k=1..A000041(n)} A305309(n, k), n >= 1. Also row sums of triangle A078812.- Wolfdieter Lang, May 31 2018
a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4). - Peter Luschny, Sep 03 2019
Sum_{n>=1} 1/a(n) = A153386. - Amiram Eldar, Oct 04 2020
a(n) = A249450(n) + 2. - Leo Tavares, Oct 10 2021
a(n) = -2/(sqrt(5)*tan(2*arctan(phi^(2*n)))), where phi = A001622 is the golden ratio. - Diego Rattaggi, Nov 21 2021
a(n) = sinh(2*n*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022
From Amiram Eldar, Dec 02 2024: (Start)
Product_{n>=1} (1 - (-1)^n/a(n)) = 1 + 1/sqrt(5) (A344212).
Product_{n>=2} (1 + (-1)^n/a(n)) = (5/6) * (1 + 1/sqrt(5)). (End)
a(n) = Sum_{k>=0} Fibonacci(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025
Sum_{n>=0} a(n)/3^n = 3. - Diego Rattaggi, Jan 20 2025

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

A005248 Bisection of Lucas numbers: a(n) = L(2*n) = A000032(2*n).

Original entry on oeis.org

2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127, 39603, 103682, 271443, 710647, 1860498, 4870847, 12752043, 33385282, 87403803, 228826127, 599074578, 1568397607, 4106118243, 10749957122, 28143753123, 73681302247, 192900153618, 505019158607, 1322157322203
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Drop initial 2; then iterates of A050411 do not diverge for these starting values. - David W. Wilson
All nonnegative integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = +4 together with b(n)=A001906(n), n>=0. - Wolfdieter Lang, Aug 31 2004
a(n+1) = B^(n)AB(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., 3=`10`, 7=`010`, 18=`0010`, 47=`00010`, ..., in Wythoff code. a(0) = 2 = B(1) in Wythoff code.
Output of Tesler's formula (as well as that of Lu and Wu) for the number of perfect matchings of an m X n Möbius band where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009
Numbers having two 1's in their base-phi representation. - Robert G. Wilson v, Sep 13 2010
Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... - R. J. Mathar, Aug 10 2012
From Wolfdieter Lang, Feb 18 2013: (Start)
a(n) is also one half of the total number of round trips, each of length 2*n, on the graph P_4 (o-o-o-o) (the simple path with 4 points (vertices) and 3 lines (or edges)). See the array and triangle A198632 for the general case of the graph P_N (there N is n and the length is l=2*k).
O.g.f. for w(4,l) (with zeros for odd l): y*(d/dy)S(4,y)/S(4,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form. One half of this o.g.f. for x -> sqrt(x) produces the g.f. (2-3x)/(1-3x+x^2) given below. (End)
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy - 5. - Michel Lagneau, Feb 01 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 7xy + y^2 + 45 = 0. - Colin Barker, Feb 16 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 320 = 0. - Colin Barker, Feb 16 2014
a(n) are the numbers such that a(n)^2-2 are Lucas numbers. - Michel Lagneau, Jul 22 2014
All sequences of this form, b(n+1) = 3*b(n) - b(n-1), regardless of initial values, which includes this sequence, yield this sequence as follows: a(n) = (b(j+n) + b(j-n))/b(j), for any j, except where b(j) = 0. Also note formula below relating this a(n) to all sequences of the form G(n+1) = G(n) + G(n-1). - Richard R. Forberg, Nov 18 2014
A non-simple continued fraction expansion for F(2n*(k+1))/F(2nk) k>=1 is a(n) + (-1)/(a(n) + (-1)/(a(n) + ... + (-1)/a(n))) where a(n) appears exactly k times (F(n) denotes the n-th Fibonacci number). E.g., F(16)/F(12) equals 7 + (-1)/(7 + (-1)/7). Furthermore, these a(n) are exactly the positive integers k such that the non-simple infinite continued fraction k + (-1)/(k + (-1)/(k + (-1)/(k + ...))) belongs to Q(sqrt(5)). Compare to Benoit Cloitre and Thomas Baruchel's comments at A002878. - Greg Dresden, Aug 13 2019
For n >= 1, a(n) is the number of cyclic up-down words of length 2*n over an alphabet of size 3. - Sela Fried, Apr 08 2025

Examples

			G.f. = 2 + 3*x + 7*x^2 + 18*x^3 + 47*x^4 + 123*x^5 + 322*x^6 + 843*x^7 + ... - _Michael Somos_, Aug 11 2009

References

  • 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).
  • Richard P. Stanley, Enumerative combinatorics, Vol. 2. Volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

Links

Crossrefs

Cf. A000032, A002878 (odd-indexed Lucas numbers), A001906 (Chebyshev S(n-1, 3)), a(n) = sqrt(4+5*A001906(n)^2), A228842.
a(n) = A005592(n)+1 = A004146(n)+2 = A065034(n)-1.
First differences of A002878. Pairwise sums of A001519. First row of array A103997.
Cf. A153415, A201157. Also Lucas(k*n): A000032 (k = 1), A014448 (k = 3), A056854 (k = 4), A001946 (k = 5), A087215 (k = 6), A087281 (k = 7), A087265 (k = 8), A087287 (k = 9), A065705 (k = 10), A089772 (k = 11), A089775 (k = 12).

Programs

  • Haskell
    a005248 n = a005248_list !! n
a005248_list = zipWith (+) (tail a001519_list) a001519_list
-- Reinhard Zumkeller, Jan 11 2012
  • Magma
    [Lucas(2*n) : n in [0..100]]; // Vincenzo Librandi, Apr 14 2011
  • Maple
    a:= n-> (<<2|3>>. <<3|1>, <-1|0>>^n)[1$2]: seq(a(n), n=0..30); # Alois P. Heinz, Jul 31 2008
with(combinat): seq(5*fibonacci(n)^2+2*(-1)^n, n= 0..26);
  • Mathematica
    a[0] = 2; a[1] = 3; a[n_] := 3a[n - 1] - a[n - 2]; Table[ a[n], {n, 0, 27}] (* Robert G. Wilson v, Jan 30 2004 *)
Fibonacci[1 + 2n] + 1/2 (-Fibonacci[2n] + LucasL[2n]) (* Tesler. Sarah-Marie Belcastro, Jul 04 2009 *)
LinearRecurrence[{3, -1}, {2, 3}, 50] (* Sture Sjöstedt, Nov 27 2011 *)
LucasL[Range[0,60,2]] (* Harvey P. Dale, Sep 30 2014 *)
  • PARI
    {a(n) = fibonacci(2*n + 1) + fibonacci(2*n - 1)}; /* Michael Somos, Jun 23 2002 */
  • PARI
    {a(n) = 2 * subst( poltchebi(n), x, 3/2)}; /* Michael Somos, Jun 28 2003 */
  • Sage
    [lucas_number2(n,3,1) for n in range(37)] # Zerinvary Lajos, Jun 25 2008

Formula

a(n) = Fibonacci(2*n-1) + Fibonacci(2*n+1).
G.f.: (2-3*x)/(1-3*x+x^2). - Simon Plouffe in his 1992 dissertation.
a(n) = S(n, 3) - S(n-2, 3) = 2*T(n, 3/2) with S(n-1, 3) = A001906(n) and S(-2, x) = -1. U(n, x)=S(n, 2*x) and T(n, x) are Chebyshev's U- and T-polynomials.
a(n) = a(k)*a(n - k) - a(n - 2k) for all k, i.e., a(n) = 2*a(n) - a(n) = 3*a(n - 1) - a(n - 2) = 7*a(n - 2) - a(n - 4) = 18*a(n - 3) - a(n - 6) = 47*a(n - 4) - a(n - 8) etc., a(2n) = a(n)^2 - 2. - Henry Bottomley, May 08 2001
a(n) = A060924(n-1, 0) = 3*A001906(n) - 2*A001906(n-1), n >= 1. - Wolfdieter Lang, Apr 26 2001
a(n) ~ phi^(2*n) where phi=(1+sqrt(5))/2. - Joe Keane (jgk(AT)jgk.org), May 15 2002
a(0)=2, a(1)=3, a(n) = 3*a(n-1) - a(n-2) = a(-n). - Michael Somos, Jun 28 2003
a(n) = phi^(2*n) + phi^(-2*n) where phi=(sqrt(5)+1)/2, the golden ratio. E.g., a(4)=47 because phi^(8) + phi^(-8) = 47. - Dennis P. Walsh, Jul 24 2003
With interpolated zeros, trace(A^n)/4, where A is the adjacency matrix of path graph P_4. Binomial transform is then A049680. - Paul Barry, Apr 24 2004
a(n) = (floor((3+sqrt(5))^n) + 1)/2^n. - Lekraj Beedassy, Oct 22 2004
a(n) = ((3-sqrt(5))^n + (3+sqrt(5))^n)/2^n (Note: substituting the number 1 for 3 in the last equation gives A000204, substituting 5 for 3 gives A020876). - Creighton Dement, Apr 19 2005
a(n) = (1/(n+1/2))*Sum_{k=0..n} B(2k)*L(2n+1-2k)*binomial(2n+1, 2k) where B(2k) is the (2k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005
a(n) = term (1,1) in the 1 X 2 matrix [2,3] . [3,1; -1,0]^n. - Alois P. Heinz, Jul 31 2008
a(n) = 2*cosh(2*n*psi), where psi=log((1+sqrt(5))/2). - Al Hakanson, Mar 21 2009
From Sarah-Marie Belcastro, Jul 04 2009: (Start)
a(n) - (a(n) - F(2n))/2 - F(2n+1) = 0. (Tesler)
Product_{r=1..n} (1 + 4*(sin((4r-1)*Pi/(4n)))^2). (Lu/Wu) (End)
a(n) = Fibonacci(2n+6) mod Fibonacci(2n+2), n > 1. - Gary Detlefs, Nov 22 2010
a(n) = 5*Fibonacci(n)^2 + 2*(-1)^n. - Gary Detlefs, Nov 22 2010
a(n) = A033888(n)/A001906(n), n > 0. - Gary Detlefs, Dec 26 2010
a(n) = 2^(2*n) * Sum_{k=1..2} (cos(k*Pi/5))^(2*n). - L. Edson Jeffery, Jan 21 2012
From Peter Bala, Jan 04 2013: (Start)
Let F(x) = Product_{n>=0} (1 + x^(4*n+1))/(1 + x^(4*n+3)). Let alpha = 1/2*(3 - sqrt(5)). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.31829 56058 81914 31334 ... = 2 + 1/(3 + 1/(7 + 1/(18 + ...))).
Also F(-alpha) = 0.64985 97768 07374 32950 has the continued fraction representation 1 - 1/(3 - 1/(7 - 1/(18 - ...))) and the simple continued fraction expansion 1/(1 + 1/((3-2) + 1/(1 + 1/((7-2) + 1/(1 + 1/((18-2) + 1/(1 + ...))))))).
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((3^2-4) + 1/(1 + 1/((7^2-4) + 1/(1 + 1/((18^2-4) + 1/(1 + ...))))))).
Added Oct 13 2019: 1/2 + 1/2*F(alpha)/F(-alpha) = 1.5142923542... has the simple continued fraction expansion 1 + 1/((3 - 2) + 1/(1 + 1/((18 - 2) + 1/(1 + 1/(123 - 2) + 1/(1 + ...))))). (End)
G.f.: (W(0)+6)/(5*x), where W(k) = 5*x*k + x - 6 + 6*x*(5*k-9)/W(k+1) (continued fraction). - Sergei N. Gladkovskii, Aug 19 2013
Sum_{n >= 1} 1/( a(n) - 5/a(n) ) = 1. Compare with A001906, A002878 and A023039. - Peter Bala, Nov 29 2013
0 = a(n) * a(n+2) - a(n+1)^2 - 5 for all n in Z. - Michael Somos, Aug 24 2014
a(n) = (G(j+2n) + G(j-2n))/G(j), for n >= 0 and any j, positive or negative, except where G(j) = 0, and for any sequence of the form G(n+1) = G(n) + G(n-1) with any initial values for G(0), G(1), including non-integer values. G(n) includes Lucas, Fibonacci. Compare with A081067 for odd number offsets from j. - Richard R. Forberg, Nov 16 2014
a(n) = [x^n] ( (1 + 3*x + sqrt(1 + 6*x + 5*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
From J. M. Bergot, Oct 28 2015: (Start)
For n>0, a(n) = F(n-1) * L(n) + F(2*n+1) - (-1)^n with F(k) = A000045(k).
For n>1, a(n) = F(n+1) * L(n) + F(2*n-1) - (-1)^n.
For n>2, a(n) = 5*F(2*n-3) + 2*L(n-3) * L(n) + 8*(-1)^n. (End)
For n>1, a(n) = L(n-2)*L(n+2) -7*(-1)^n. - J. M. Bergot, Feb 10 2016
a(n) = 6*F(n-1)*L(n-1) - F(2*n-6) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, Apr 21 2017
a(n) = F(2*n) + 2*F(n-1)*L(n) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, May 01 2017
E.g.f.: exp(4*x/(1+sqrt(5))^2) + exp((1/4)*(1+sqrt(5))^2*x). - Stefano Spezia, Aug 13 2019
From Peter Bala, Oct 14 2019: (Start)
a(n) = F(2*n+2) - F(2*n-2) = A001906(n+1) - A001906(n-1).
a(n) = trace(M^n), where M is the 2 X 2 matrix [0, 1; 1, 1]^2 = [1, 1; 1, 2].
Consequently the Gauss congruences hold: a(n*p^k) = a(n*p^(k-1)) ( mod p^k ) for all prime p and positive integers n and k. See Zarelua and also Stanley (Ch. 5, Ex. 5.2(a) and its solution).
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 1/a(n) ) = 1/5.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 3/(a(n) + 2/(a(n))) ) = 1/6.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 9/(a(n) + 4/(a(n) + 1/(a(n)))) ) = 1/9.
x*exp(Sum_{n >= 1} a(n)*x^/n) = x + 3*x^2 + 8*x^3 + 21*x^4 + ... is the o.g.f. for A001906. (End)
a(n) = n + 2 + Sum_{k=1..n-1} k*a(n-k). - Yu Xiao, May 30 2020
Sum_{n>=1} 1/a(n) = A153415. - Amiram Eldar, Nov 11 2020
Sum_{n>=0} 1/(a(n) + 3) = (2*sqrt(5) + 1)/10 (André-Jeannin, 1991). - Amiram Eldar, Jan 23 2022
a(n) = 2*cosh(2*n*arccsch(2)) = 2*cosh(2*n*asinh(1/2)). - Peter Luschny, May 25 2022
a(n) = (5/2)*(Sum_{k=-n..n} binomial(2*n, n+5*k)) - (1/2)*4^n. - Greg Dresden, Jan 05 2023
a(n) = Sum_{k>=0} Lucas(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025

Extensions

Additional comments from Michael Somos, Jun 23 2001

A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3
Offset: 0

Views

Author

Felix Weinstein (wain(AT)ana.unibe.ch) and Clark Kimberling

Keywords

Comments

Also number of 0's (or B's) in the Wythoff representation of n -- see the Reble link. See also A135817 for references and links for the Wythoff representation for n >= 1. - Wolfdieter Lang, Jan 21 2008; N. J. A. Sloane, Jun 28 2008
Or, a(n) is the number of applications of Wythoff's B sequence A001950 needed in the unique Wythoff representation of n >= 1. E.g., 16 = A(B(A(A(B(1))))) = ABAAB = `10110`, hence a(16) = 2. - Wolfdieter Lang, Jan 21 2008
Let M(0) = 0, M(1) = 1 and for i > 0, M(i+1) = f(concatenation of M(j), j from 0 to i - 1) where f is the morphism f(k) = k + 1. Then the sequence is the concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003
From Joerg Arndt, Nov 09 2012: (Start)
Let m be the number of parts in the listing of the compositions of n into odd parts as lists of parts in lexicographic order, a(k) = (n - length(composition(k)))/2 for all k < Fibonacci(n) and all n (see example).
Let m be the number of parts in the listing of the compositions of n into parts 1 and 2 as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < Fibonacci(n) and all n (see example).
A000120 gives the equivalent for (all) compositions. (End)
a(n) = A104324(n) - A213911(n); row lengths in A035516 and A035516. - Reinhard Zumkeller, Mar 10 2013
a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - Alan Worley, Apr 17 2015
This follows from the fact that the sequence is subadditive: a(n+m) <= a(n) + a(m) for nonnegative integers n,m. See Lemma 2.1 of the Stoll link. - Robert Israel, Apr 17 2015
From Michel Dekking, Mar 08 2020: (Start)
This sequence is a morphic sequence on an infinite alphabet, i.e., (a(n)) is a letter-to-letter projection of a fixed point of a morphism tau.
The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
tau((j,0)) = (j,0) (j+1,1),
tau((j,1)) = (j,0).
The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
This implies that for all n and j one has
|tau^n(j,0)| = F(n+2),
where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
Secondly, we need the following simple, but crucial observation. Let the Zeckendorf representation of n be Z(n) = A014417(n). For example,
Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
Z(F(n+1)+i) = 10...0 Z(i),
where zeros are added to Z(i) to give the total representation length n-1.
This gives for i = 0,1,...,F(n)-1 that
a(F(n+1)+i) = a(i) + 1.
From the first observation follows that the first F(n+1) letters of tau^n(j,0) are equal to tau^{n-1}(j,0), and the last F(n) letters of tau^n(j,0) are equal to tau^{n-1}(j+1,1) = tau^{n-2}(j+1,0).
Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
It is of course possible to obtain a morphism tau' on the natural numbers by changing the alphabet: (j,0)-> 2j (j,1)-> 2j+1, which yields the morphism
tau'(2j) = 2j, 2j+3, tau'(2j+1) = 2j.
The fixed point of tau' starting with 0 is
u = 03225254254472544747625...
The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
(End)

Examples

			a(46) = a(1 + 3 + 8 + 34) = 4.
From _Joerg Arndt_, Nov 09 2012: (Start)
Connection to the compositions of n into odd parts (see comment):
[ #]:  a(n)  composition into odd parts
[ 0]   [ 0]   1 1 1 1 1 1 1 1
[ 1]   [ 1]   1 1 1 1 1 3
[ 2]   [ 1]   1 1 1 1 3 1
[ 3]   [ 1]   1 1 1 3 1 1
[ 4]   [ 2]   1 1 1 5
[ 5]   [ 1]   1 1 3 1 1 1
[ 6]   [ 2]   1 1 3 3
[ 7]   [ 2]   1 1 5 1
[ 8]   [ 1]   1 3 1 1 1 1
[ 9]   [ 2]   1 3 1 3
[10]   [ 2]   1 3 3 1
[11]   [ 2]   1 5 1 1
[12]   [ 3]   1 7
[13]   [ 1]   3 1 1 1 1 1
[14]   [ 2]   3 1 1 3
[15]   [ 2]   3 1 3 1
[16]   [ 2]   3 3 1 1
[17]   [ 3]   3 5
[18]   [ 2]   5 1 1 1
[19]   [ 3]   5 3
[20]   [ 3]   7 1
Connection to the compositions of n into parts 1 or 2 (see comment):
[ #]:  a(n)  composition into parts 1 and 2
[ 0]   [0]   1 1 1 1 1 1 1
[ 1]   [1]   1 1 1 1 1 2
[ 2]   [1]   1 1 1 1 2 1
[ 3]   [1]   1 1 1 2 1 1
[ 4]   [2]   1 1 1 2 2
[ 5]   [1]   1 1 2 1 1 1
[ 6]   [2]   1 1 2 1 2
[ 7]   [2]   1 1 2 2 1
[ 8]   [1]   1 2 1 1 1 1
[ 9]   [2]   1 2 1 1 2
[10]   [2]   1 2 1 2 1
[11]   [2]   1 2 2 1 1
[12]   [3]   1 2 2 2
[13]   [1]   2 1 1 1 1 1
[14]   [2]   2 1 1 1 2
[15]   [2]   2 1 1 2 1
[16]   [2]   2 1 2 1 1
[17]   [3]   2 1 2 2
[18]   [2]   2 2 1 1 1
[19]   [3]   2 2 1 2
[20]   [3]   2 2 2 1
(End)
From _Michel Dekking_, Mar 08 2020: (Start)
The third iterate of the morphism tau generating this sequence:
      tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
= (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)

References

  • Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
  • F. Weinstein, The Fibonacci Partitions, preprint, 1995.
  • Édouard Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

Links

Crossrefs

Cf. A000045, A007953, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911, A014417, A003849.
Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
Record positions are in A027941.

Programs

  • Haskell
    a007895 = length . a035516_row  -- Reinhard Zumkeller, Mar 10 2013
  • Maple
    # With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n.
with(combinat): B := proc (n) local A, ct, m, j: A := proc (n) local i: for i while fibonacci(i) <= n do n-fibonacci(i) end do end proc: ct := 0; m := n: for j while 0 < A(m) do ct := ct+1: m := A(m) end do: ct+1 end proc: 0, seq(B(n), n = 1 .. 104);
# Emeric Deutsch, Jul 05 2010
N:= 1000: # to get a(n) for n <= N
m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)):
Z:= Vector(m):
a[0]:= 0:
for n from 1 to N do
if Z[1] = 0 then Z[1]:= 1; q:= 1;
else Z[2]:= 1; Z[1]:= 0; q:= 2;
fi;
while Z[q+1] = 1 do
  Z[q]:= 0;
  Z[q+1]:= 0;
  Z[q+2]:= 1;
  q:= q+2;
od:
a[n]:= add(Z[i],i=1..m);
od:
seq(a[n],n=0..N); # Robert Israel, Apr 17 2015
# alternative
read("transforms") : # https://oeis.org/transforms.txt
A007895 := proc(n)
    wt(A003714(n)) ;
end proc:
seq(A007895(n),n=0..10) ; # R. J. Mathar, Sep 22 2020
  • Mathematica
    zf[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); zeckRep[n_] := If[n == 0, 0, r = n; s = {}; fr = zf[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]; zeckRepLen[n_] := Length[zeckRep[n]]; Table[zeckRepLen[n], {n, 0, 104}] (* Jean-François Alcover, Sep 27 2011 *)
DigitCount[Select[Range[0, 1000], BitAnd[#, 2#] == 0 &], 2, 1] (* Jean-François Alcover, Jan 25 2018 *)
Table[Length[DeleteCases[NestWhileList[# - Fibonacci[Floor[Log[Sqrt[5] * # + 3/2]/Log[GoldenRatio]]] &, n, # > 1 &], 0]], {n, 0, 143}] (* Alonso del Arte, May 14 2019 *)
Flatten[Nest[{Flatten[#], #[[1]] + 1} &, {0, 1}, 9]] (* Paolo Xausa, Jun 17 2024 *)
  • PARI
    a(n,mx=0)=if(n<4,n>0,if(!mx,while(fibonacci(mx)n,mx--); 1+a(n-fibonacci(mx),mx-2)) \\ Charles R Greathouse IV, Feb 14 2013
  • PARI
    a(n)=if(n<4, n>0, my(k=2,s,t); while(fibonacci(k++)<=n,); while(k && n, t=fibonacci(k); if(t<=n, n-=t; s++); k--); s) \\ Charles R Greathouse IV, Sep 02 2015
  • Python
    from sympy import fibonacci
def a(n):
    k=0
    x=0
    while n>0:
        k=0
        while fibonacci(k)<=n: k+=1
        x+=10**(k - 3)
        n-=fibonacci(k - 1)
    return str(x).count("1")
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 09 2017

Formula

a(n) = A000120(A003714(n)). - Reinhard Zumkeller, May 05 2005
a(n) = A107015(n) + A107016(n). - Reinhard Zumkeller, May 09 2005
a(n) = A143299(n+1) - 1. - Filip Zaludek, Oct 31 2016
a(n) = A007953(A014417(n)). - Amiram Eldar, Oct 10 2023

Extensions

Edited by N. J. A. Sloane Jun 27 2008 at the suggestion of R. J. Mathar and Don Reble

A001611 a(n) = Fibonacci(n) + 1.

Original entry on oeis.org

1, 2, 2, 3, 4, 6, 9, 14, 22, 35, 56, 90, 145, 234, 378, 611, 988, 1598, 2585, 4182, 6766, 10947, 17712, 28658, 46369, 75026, 121394, 196419, 317812, 514230, 832041, 1346270, 2178310, 3524579, 5702888, 9227466, 14930353, 24157818, 39088170, 63245987, 102334156
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(0) = 1, a(1) = 2 then the largest number such that a triangle is constructible with three successive terms as sides. - Amarnath Murthy, Jun 03 2003
a(n+2) = A^(n)B(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`, 3=`10`, 4=`110`, 6=`1110`, ..., in Wythoff code.
The first-difference sequence is the Fibonacci sequence (A000045). - Roland Schroeder (florola(AT)gmx.de), Aug 05 2010
2 and 3 are the only primes in this sequence.
a(n) is the number of 1 X n nonogram puzzles which can be solved uniquely. See A242876 for puzzle definition. - Lior Manor, Jan 23 2022

References

  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • 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).

Links

Crossrefs

Cf. A000045, A097280, A097281.
Cf. A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616. [Added by N. J. A. Sloane, Jun 25 2010 in response to a comment from Aviezri S. Fraenkel]
Cf. A002062, A019863, A160536, A212272, A242876.

Programs

  • Haskell
    a001611 = (+ 1) . a000045
a001611_list = 1 : 2 : map (subtract 1)
                       (zipWith (+) a001611_list $ tail a001611_list)
-- Reinhard Zumkeller, Jul 30 2013
  • Magma
    [Fibonacci(n)+1: n in [1..37]]; // Bruno Berselli, Jul 26 2011
  • Maple
    A001611:=-(-1+2*z**2)/(z-1)/(z**2+z-1); # Simon Plouffe in his 1992 dissertation
with(combinat): seq((fibonacci(n)+1), n=0..35);
  • Mathematica
    a[0] = 1; a[1] = 2; a[n_] := a[n] = a[n-2] + a[n-1] - 1; Table[ a[n], {n, 0, 40} ]
Fibonacci[Range[0,50]]+1  (* Harvey P. Dale, Mar 23 2011 *)
  • PARI
    a(n)=fibonacci(n)+1 \\ Charles R Greathouse IV, Jul 25 2011

Formula

G.f.: (1-2*x^2)/(1-2*x+x^3).
a(n) = 2*a(n-1) - a(n-3). - Tanya Khovanova, Jul 13 2007
a(0) = 1, a(1) = 2, a(n) = a(n - 2) + a(n - 1) - 1.
F(4*n) + 1 = F(2*n-1)*L(2*n+1); F(4*n+1) + 1 = F(2*n+1)*L(2*n); F(4*n+2) + 1 = F(2*n+2)*L(2*n); F(4*n+3) + 1 = F(2*n+1)*L(2*n+2) where F(n)=Fibonacci(n) and L(n)=Lucas(n). - R. K. Guy, Feb 27 2003
a(1) = 2; a(n+1)=floor(a(n)*(sqrt(5)+1)/2). - Roland Schroeder (florola(AT)gmx.de), Aug 05 2010
a(n) = Sum_{k=0..n+1} Fibonacci(k-3). - Ehren Metcalfe, Apr 15 2019
Product_{n>=1} (1 - (-1)^n/a(n)) = sin(3*Pi/10) (A019863). - Amiram Eldar, Nov 28 2024

A027941 a(n) = Fibonacci(2*n + 1) - 1.

Original entry on oeis.org

0, 1, 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, 75024, 196417, 514228, 1346268, 3524577, 9227464, 24157816, 63245985, 165580140, 433494436, 1134903169, 2971215072, 7778742048, 20365011073, 53316291172, 139583862444, 365435296161, 956722026040
Offset: 0

Views

Author

Clark Kimberling

Keywords

Comments

Also T(2n+1,n+1), T given by A027935. Also first row of Inverse Stolarsky array.
Third 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
Number of Schroeder paths of length 2(n+1) having exactly one up step starting at an even height (a Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis). Schroeder paths are counted by the large Schroeder numbers (A006318). Example: a(1)=4 because among the six Schroeder paths of length 4 only the paths (U)HD, (U)UDD, H(U)D, (U)DH have exactly one U step that starts at an even height (shown between parentheses). - Emeric Deutsch, Dec 19 2004
Also: smallest number not writeable as the sum of fewer than n positive Fibonacci numbers. E.g., a(5)=88 because it is the smallest number that needs at least 5 Fibonacci numbers: 88 = 55 + 21 + 8 + 3 + 1. - Johan Claes, Apr 19 2005 [corrected for offset and clarification by Mike Speciner, Sep 19 2023] In general, a(n) is the sum of n positive Fibonacci numbers as a(n) = Sum_{i=1..n} A000045(2*i). See A001076 when negative Fibonacci numbers can be included in the sum. - Mike Speciner, Sep 24 2023
Except for first term, numbers a(n) that set a new record in the number of Fibonacci numbers needed to sum up to n. Position of records in sequence A007895. - Ralf Stephan, May 15 2005
Successive extremal petal bends beta(n) = a(n-2). See the Ring Lemma of Rodin and Sullivan in K. Stephenson, Introduction to Circle Packing (Cambridge U. P., 2005), pp. 73-74 and 318-321. - David W. Cantrell (DWCantrell(AT)sigmaxi.net)
a(n+1)= AAB^(n)(1), n>=1, 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., 4=`110`, 12=`1100`, 33=`11000`, 88=`110000`, ..., in Wythoff code. AA(1)=1=a(1) but for uniqueness reason 1=A(1) in Wythoff code. - N. J. A. Sloane, Jun 29 2008
Start with n. Each n generates a sublist {n-1,n-1,n-2,..,1}. Each element of each sublist also generates a sublist. Add numbers in all terms. For example, 3->{2,2,1} and both 2->{1,1}, so a(3) = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 12. - Jon Perry, Sep 01 2012
For n>0: smallest number such that the inner product of Zeckendorf binary representation and its reverse equals n: A216176(a(n)) = n, see also A189920. - Reinhard Zumkeller, Mar 10 2013
Also, numbers m such that 5*m*(m+2)+1 is a square. - Bruno Berselli, May 19 2014
Also, number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
From Robert K. Moniot, Oct 04 2020: (Start)
Including a(-1):=0, consecutive terms (a(n-1),a(n))=(u,v) or (v,u) give all points on the hyperbola u^2-u+v^2-v-4*u*v=0 with both coordinates nonnegative integers. Note that this follows from identifying (1,u+1,v+1) with the Markov triple (1,Fibonacci(2n-1),Fibonacci(2n+1)). See A001519 (comments by Robert G. Wilson, Oct 05 2005, and Wolfdieter Lang, Jan 30 2015).
Let T(n) denote the n-th triangular number. If i, j are any two successive elements of the above sequence then (T(i-1) + T(j-1))/T(i+j-1) = 3/5. (End)

Examples

			a(5) = 88 = 2*33 + 12 + 4 + 1 + 5. a(6) = 232 = 2*88 + 33 + 12 + 4 + 1 + 6. - _Jon Perry_, Sep 01 2012
a(4) = 33 counts all nonempty submultisets of the last row: [1][2][3][4], [11][12][13][14][22][23][24][33][34], [111][112][113][122][123][124][133][134][222][223][233][234], [1111][1112][1122][1123][1222][1223][1233][1234]. - _Gus Wiseman_, Feb 10 2015

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 12.

Links

Crossrefs

Cf. A000045, A035507, A001906, A006318, A000032.
Related to partial sums of Fibonacci(k*n) over n: A000071, A099919, A058038, A138134, A053606; this sequence is the case k=2.
Cf. A212336 for more sequences with g.f. of the type 1/(1 - k*x + k*x^2 - x^3).
Cf. A000225 (sublist connection).
Cf. A258993 (row sums, n > 0), A000967.

Programs

Formula

a(n) = Sum_{i=1..n} binomial(n+i, n-i). - Benoit Cloitre, Oct 15 2002
G.f.: Sum_{k>=1} x^k/(1-x)^(2*k+1). - Benoit Cloitre, Apr 21 2003
a(n) = Sum_{k=1..n} F(2*k), i.e., partial sums of A001906. - Benoit Cloitre, Oct 27 2003
a(n) = Sum_{k=0..n-1} U(k, 3/2) = Sum_{k=0..n-1} S(k, 3), with S(k, 3) = A001906(k+1). - Paul Barry, Nov 14 2003
G.f.: x/((1-x)*(1-3*x+x^2)) = x/(1-4*x+4*x^2-x^3).
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) with n>=2, a(-1)=0, a(0)=0, a(1)=1.
a(n) = 3*a(n-1) - a(n-2) + 1 with n>=1, a(-1)=0, a(0)=0.
a(n) = Sum_{k=1..n} F(k)*L(k), where L(k) = Lucas(k) = A000032(k) = F(k-1) + F(k+1). - Alexander Adamchuk, May 18 2007
a(n) = 2*a(n-1) + (Sum_{k=1..n-2} a(k)) + n. - Jon Perry, Sep 01 2012
Sum {n >= 1} 1/a(n) = 3 - phi, where phi = 1/2*(1 + sqrt(5)) is the golden ratio. The ratio of adjacent terms r(n) := a(n)/a(n-1) satisfies the recurrence r(n+1) = (4*r(n) - 1)/(r(n) + 1) for n >= 2. - Peter Bala, Dec 05 2013
a(n) = S(n, 3) - S(n-1, 3) - 1, n >= 0, with Chebyshev's S-polynomials (see A049310), where S(-1, x) = 0. - Wolfdieter Lang, Aug 28 2014
a(n) = -1 + (2^(-1-n)*((3-sqrt(5))^n*(-1+sqrt(5)) + (1+sqrt(5))*(3+sqrt(5))^n)) / sqrt(5). - Colin Barker, Jun 03 2016
E.g.f.: (sqrt(5)*sinh(sqrt(5)*x/2) + 5*cosh(sqrt(5)*x/2))*exp(3*x/2)/5 - exp(x). - Ilya Gutkovskiy, Jun 03 2016
a(n) = Sum_{k=0..n} binomial(n+1,k+1)*Fibonacci(k). - Vladimir Kruchinin, Oct 14 2016
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i+1,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n)*a(n-2) = a(n-1)*(a(n-1) - 1) for n>1. - Robert K. Moniot, Aug 23 2020
a(n) = Sum_{k=1..n} C(2*n-k,k). - Wesley Ivan Hurt, Dec 22 2020
a(n) = Sum_{k = 1..2*n+2} (-1)^k*Fibonacci(k). - Peter Bala, Nov 14 2021
a(n) = (2*cosh((1 + 2*n)*arccsch(2)))/sqrt(5) - 1. - Peter Luschny, Nov 21 2021
a(n) = F(n + (n mod 2)) * L(n+1 - (n mod 2)), where L(n) = A000032(n) and F(n) = A000045(n) (Euler and Sadek, 2001). - Amiram Eldar, Jan 13 2022

Extensions

More terms from James Sellers, Sep 08 2000
Paul Barry's Nov 14 2003 formula, recurrences and g.f. corrected for offset 0 and index link for Chebyshev polynomials added by Wolfdieter Lang, Aug 28 2014

A200648 Length of Stolarsky representation of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 4, 3, 4, 4, 4, 5, 4, 4, 5, 4, 5, 5, 5, 6, 4, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 7, 5, 5, 6, 5, 6, 6, 6, 7, 5, 6, 6, 6, 7, 6, 6, 7, 6, 7, 7, 7, 8, 5, 6, 6, 6, 7, 6, 6, 7, 6, 7, 7, 7, 8, 6, 6, 7, 6, 7, 7, 7, 8, 6, 7, 7, 7, 8, 7, 7, 8, 7, 8, 8
Offset: 1

Views

Author

Casey Mongoven, Nov 19 2011

Keywords

Comments

For the Stolarsky representation of n, see the C. Mongoven link.
Conjecture: a(n) is the sum of row n-1 of A385886. To obtain it, first take maximal anti-run lengths of binary indices of each nonnegative integer (giving A384877), then remove all duplicate rows (giving A385886), and finally take the sum of each remaining row. For length instead of sum we appear to have A200649. - Gus Wiseman, Jul 21 2025

Examples

			The Stolarsky representation of 19 is 11101. This is of length 5. So a(19) = 5.

Links

Crossrefs

Cf. A135817, A200651.
Counting just ones gives A200649.
Counting just zeros gives A200650.
Stolarsky representation is listed by A385888, ranks A200714.
A000120 counts 1's in binary expansion.
A384890 counts maximal anti-runs of binary indices, ranks A385816.
A385886 lists maximal anti-run lengths of binary indices.
Cf. A023758, A048793, A052499, A069010, A072649, A083368, A135818, A245562, A245563, A348366, A384877, A384893.

Programs

  • Mathematica
    stol[n_] := stol[n] = If[n == 1, {}, If[n != Round[Round[n/GoldenRatio]*GoldenRatio], Join[stol[Floor[n/GoldenRatio^2] + 1], {0}], Join[stol[Round[n/GoldenRatio]], {1}]]];
a[n_] := If[n == 1, 1, Length[stol[n]]]; Array[a, 100] (* Amiram Eldar, Jul 07 2023 *)
  • PARI
    stol(n) = {my(phi=quadgen(5)); if(n==1, [], if(n != round(round(n/phi)*phi), concat(stol(floor(n/phi^2) + 1), [0]), concat(stol(round(n/phi)), [1])));}
a(n) = if(n == 1, 1, #stol(n)); \\ Amiram Eldar, Jul 07 2023

Formula

a(n) = A200649(n) + A200650(n). - Michel Marcus, Mar 14 2023

Extensions

More terms from Amiram Eldar, Jul 07 2023

A317208 The Wythoff representation of n: an alternative way of presenting A189921.

Original entry on oeis.org

0, 1, 2, 12, 112, 22, 1112, 212, 122, 11112, 2112, 1212, 1122, 222, 111112, 21112, 12112, 11212, 2212, 11122, 2122, 1222, 1111112, 211112, 121112, 112112, 22112, 111212, 21212, 12212, 111122, 21122, 12122, 11222, 2222, 11111112, 2111112, 1211112, 1121112
Offset: 0

Views

Author

N. J. A. Sloane, Aug 09 2018

Keywords

Comments

This is an encoding of the position of n in the A000201, A001950 "Wythoff" table T.
Let T denote the following 3-rowed table, whose rows are n, A = A000201(n), B = A001950(n):
n: 1 2 3 .4 .5 .6 .7 .8 .9 ...
A: 1 3 4 .6 .8 .9 11 12 14 ...
B: 2 5 7 10 13 15 18 20 23 ...
Set a(0)=0. For n>0, locate n in rows A and B of the table, and indicate how to reach that entry starting from column 1. For example, 18 = B(7) = B(B(3)) = B(B(A(2))) = B(B(A(B(1)))), so the path to reach 18 is BBAB, which we write (encoding A as 1, B as 2) as a(18) = 2212.
This is another way of writing the Wythoff representation of n described in Lang (1996) and A189921.

References

  • Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337.

Links

Crossrefs

Cf. A189921, A135817 (length).
Cf. also A317207.
Cf. A000201, A001950.

Programs

  • Mathematica
    z[n_] := Floor[(n + 1)*GoldenRatio] - n - 1; h[n_] := z[n] - z[n - 1]; w[n_] := Module[{m = n, zm = 0, hm, s = {}}, While[zm != 1, hm = h[m]; AppendTo[s, hm]; If[hm == 1, zm = z[m], zm = z[z[m]]]; m = zm]; s]; a[n_] := FromDigits[ReplaceAll[w[n], {0 :> 2}]]; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Jul 01 2023 *)

Extensions

a(23) and beyond from Lars Blomberg, Aug 11 2018

A001612 a(n) = a(n-1) + a(n-2) - 1 for n > 1, a(0)=3, a(1)=2.

Original entry on oeis.org

3, 2, 4, 5, 8, 12, 19, 30, 48, 77, 124, 200, 323, 522, 844, 1365, 2208, 3572, 5779, 9350, 15128, 24477, 39604, 64080, 103683, 167762, 271444, 439205, 710648, 1149852, 1860499, 3010350, 4870848, 7881197, 12752044, 20633240, 33385283, 54018522
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n+3) = A^(n)B^(2)(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., 5=`00`, 8=`100`, 12=`1100`, ..., in Wythoff code.
From Petros Hadjicostas, Jan 11 2017: (Start)
a(n) is the number of cyclic sequences consisting of zeros and ones that avoid the pattern 001 (or equivalently, the pattern 110) provided the positions of zeros and ones on a circle are fixed. This can easily be proved by considering that sequence A000071(n+3) is the number of binary zero-one words of length n that avoid the pattern 001 and that a(n) = A000071(n+3) - 2*A000071(n). (From the collection of all zero-one binary sequences that avoid 001 subtract those that start with 1 and end with 00 and those that start with 01 and end with 0.)
For n = 1,2, the number a(n) still gives the number of cyclic sequences consisting of zeros and ones that avoid the pattern 001 (provided the positions of zeros and ones on a circle are fixed) even if we assume that the sequence wraps around itself on the circle. For example, when 01 wraps around itself, it becomes 01010..., and it never contains the pattern 001. (End)
For n >= 3, a(n) is also the number of independent vertex sets and vertex covers in the wheel graph on n+1 nodes. - Eric W. Weisstein, Mar 31 2017

Examples

			a(3) = 5 because the following cyclic sequences of length three avoid the pattern 001: 000, 011, 101, 110, 111. - _Petros Hadjicostas_, Jan 11 2017

References

  • 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).

Links

Crossrefs

Cf. A000032, A000071, A274017.

Programs

  • Haskell
    a001612 n = a001612_list !! n
a001612_list = 3 : 2 : (map (subtract 1) $
   zipWith (+) a001612_list (tail a001612_list))
-- Reinhard Zumkeller, May 26 2013
  • Maple
    A001612:=-(-2+3*z**2)/(z-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence except for the initial 3
  • Mathematica
    Join[{b=3},a=0;Table[c=a+b-1;a=b;b=c,{n,100}]] (* Vladimir Joseph Stephan Orlovsky, Mar 15 2011 *)
Table[Fibonacci[n] + Fibonacci[n - 2] + 1, {n, 20}] (* Eric W. Weisstein, Mar 31 2017 *)
LinearRecurrence[{2, 0, -1}, {3, 2, 4}, 20] (* Eric W. Weisstein, Mar 31 2017 *)
CoefficientList[Series[(3 - 4 x)/(1 - 2 x + x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
  • PARI
    a(n)=fibonacci(n+1)+fibonacci(n-1)+1

Formula

G.f.: (3-4*x)/((1-x)*(1-x-x^2)).
a(n) = a(n-1) + a(n-2) - 1.
a(n) = A000032(n) + 1.
a(n) = A000071(n+3) - 2*A000071(n). - Petros Hadjicostas, Jan 11 2017

Extensions

Additional comments from Michael Somos, Jun 01 2000

A135818 Number of 1's (or A's) in the Wythoff representation of n.

Original entry on oeis.org

1, 0, 1, 2, 0, 3, 1, 1, 4, 2, 2, 2, 0, 5, 3, 3, 3, 1, 3, 1, 1, 6, 4, 4, 4, 2, 4, 2, 2, 4, 2, 2, 2, 0, 7, 5, 5, 5, 3, 5, 3, 3, 5, 3, 3, 3, 1, 5, 3, 3, 3, 1, 3, 1, 1, 8, 6, 6, 6, 4, 6, 4, 4, 6, 4, 4, 4, 2, 6, 4, 4, 4, 2, 4, 2, 2, 6, 4, 4, 4, 2, 4, 2, 2, 4, 2, 2, 2, 0, 9, 7, 7, 7, 5, 7, 5, 5, 7, 5, 5, 5, 3, 7, 5, 5
Offset: 1

Views

Author

Wolfdieter Lang, Jan 21 2008

Keywords

Comments

a(n) = number of applications of Wythoff's A sequence A000201 needed in the unique Wythoff representation of n>=1.
See A135817 for references and links for the Wythoff representation for n>=1.

Examples

			6 = A(A(A(B(1)))) = AAAB = `1110`, hence a(6)=3.

Links

Crossrefs

Cf. A000201, A135817 (lengths of Wythoff representation), A007895 (number of 0's (or B's) in the Wythoff representation).

Programs

  • Mathematica
    z[n_] := Floor[(n + 1)*GoldenRatio] - n - 1; h[n_] := z[n] - z[n - 1]; w[n_] := Module[{m = n, zm = 0, hm, s = {}}, While[zm != 1, hm = h[m]; AppendTo[s, hm]; If[hm == 1, zm = z[m], zm = z[z[m]]]; m = zm]; s]; w[0] = 0; a[n_] := Total[w[n]]; Array[a, 100] (* Amiram Eldar, Jul 01 2023 *)
Showing 1-10 of 16 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.