A049651 -id:A049651 - cp's OEIS frontend

A001077 Numerators of continued fraction convergents to sqrt(5).

1, 2, 9, 38, 161, 682, 2889, 12238, 51841, 219602, 930249, 3940598, 16692641, 70711162, 299537289, 1268860318, 5374978561, 22768774562, 96450076809, 408569081798, 1730726404001, 7331474697802, 31056625195209

Offset: 0

N. J. A. Sloane

a(2*n+1) with b(2*n+1) := A001076(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 5*b^2 = -1.
a(2*n) with b(2*n) := A001076(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 5*b^2 = +1 (see Emerson reference).
Bisection: a(2*n) = T(n,9) = A023039(n), n >= 0 and a(2*n+1) = 2*S(2*n, 2*sqrt(5)) = A075796(n+1), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.
From Greg Dresden, May 21 2023: (Start)
For n >= 2, 8*a(n) is the number of ways to tile this T-shaped figure of length n-1 with four colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 8*a(6) = 23112 different tilings.
    _
   || _  
   |||_|||
   |_|
(End)

			1  2  9  38  161  (A001077)
-, -, -, --, ---, ...
0  1  4  17   72  (A001076)
1 + 2*x + 9*x^2 + 38*x^3 + 161*x^4 + 682*x^5 + 2889*x^6 + 12238*x^7 + ... - _Michael Somos_, Aug 11 2009

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).
V. Thébault, Les Récréations Mathématiques, Gauthier-Villars, Paris, 1952, p. 282.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242, Ex. 1, pp. 237-238.
Tanya Khovanova, Recursive Sequences
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A000032, A001076, A023039, A049629, A052924, A078343, A164581, A179237, A180148, A329723, A374439.

I:=[1, 2]; [n le 2 select I[n] else 4*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Dec 19 2017

A001077:=(-1+2*z)/(-1+4*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation
with(combinat): a:=n->fibonacci(n+1, 4)-2*fibonacci(n, 4): seq(a(n), n=0..30); # Zerinvary Lajos, Apr 04 2008

LinearRecurrence[{4, 1}, {1, 2}, 30]
Join[{1},Numerator[Convergents[Sqrt[5],30]]] (* Harvey P. Dale, Mar 23 2016 *)
CoefficientList[Series[(1-2*x)/(1-4*x-x^2), {x, 0, 30}], x] (* G. C. Greubel, Dec 19 2017 *)
LucasL[3*Range[0,30]]/2 (* Rigoberto Florez, Apr 03 2019 *)
a[ n_] := LucasL[n, 4]/2; (* Michael Somos, Nov 02 2021 *)

{a(n) = fibonacci(3*n) / 2 + fibonacci(3*n - 1)}; /* Michael Somos, Aug 11 2009 */

a(n)=if(n<2,n+1,my(t=4);for(i=1,n-2,t=4+1/t);numerator(2+1/t)) \\ Charles R Greathouse IV, Dec 05 2011

x='x+O('x^30); Vec((1-2*x)/(1-4*x-x^2)) \\ G. C. Greubel, Dec 19 2017

[lucas_number2(n,4,-1)/2 for n in range(0, 30)] # Zerinvary Lajos, May 14 2009

G.f.: (1-2*x)/(1-4*x-x^2).
a(n) = 4*a(n-1) + a(n-2), a(0)=1, a(1)=2.
a(n) = ((2 + sqrt(5))^n + (2 - sqrt(5))^n)/2.
a(n) = A014448(n)/2.
Limit_{n->infinity} a(n)/a(n-1) = phi^3 = 2 + sqrt(5). - Gregory V. Richardson, Oct 13 2002
a(n) = ((-i)^n)*T(n, 2*i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.
Binomial transform of A084057. - Paul Barry, May 10 2003
E.g.f.: exp(2x)cosh(sqrt(5)x). - Paul Barry, May 10 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*5^k*2^(n-2k). - Paul Barry, Nov 15 2003
a(n) = 4*a(n-1) + a(n-2) when n > 2; a(1) = 1, a(2) = 2. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004
a(n) = A001076(n+1) - 2*A001076(n) = A097924(n) - A015448(n+1); a(n+1) = A097924(n) + 2*A001076(n) = A097924(n) + 2(A048876(n) - A048875(n)). - Creighton Dement, Mar 19 2005
a(n) = F(3*n)/2 + F(3*n-1) where F() = Fibonacci numbers A000045. - Gerald McGarvey, Apr 28 2007
a(n) = A000032(3*n)/2.
For n >= 1: a(n) = (1/2)*Fibonacci(6*n)/Fibonacci(3*n) and a(n) = integer part of (2 + sqrt(5))^n. - Artur Jasinski, Nov 28 2011
a(n) = Sum_{k=0..n} A201730(n,k)*4^k. - Philippe Deléham, Dec 06 2011
a(n) = A001076(n) + A015448(n). - R. J. Mathar, Jul 06 2012
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(5*k-4)/(x*(5*k+1) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 27 2013
a(n) is the (1,1)-entry of the matrix W^n with W=[2, sqrt(5); sqrt(5), 2]. - Carmine Suriano, Mar 21 2014
From Rigoberto Florez, Apr 03 2019: (Start)
a(n) = A099919(n) + A049651(n) if n > 0.
a(n) = 1 + Sum_{k=0..n-1} L(3*k + 1) if n >= 0, L(n) = n-th Lucas number (A000032). (End)
From Christopher Hohl, Aug 22 2021: (Start)
For n >= 2, a(2n-1) = A079962(6n-9) + A079962(6n-3).
For n >= 1, a(2n) = sqrt(20*A079962(6n-3)^2 + 1). (End)
a(n) = Sum_{k=0..n-2} A168561(n-2,k)*4^k + 2 * Sum_{k=0..n-1} A168561(n-1,k)*4^k, n>0. - R. J. Mathar, Feb 14 2024
a(n) = 4^n*Sum_{k=0..n} A374439(n, k)*(-1/4)^k. - Peter Luschny, Jul 26 2024
From Peter Bala, Jul 08 2025: (Start)
The following series telescope:
Sum_{n >= 1} 1/(a(n) + 5*(-1)^(n+1)/a(n)) = 3/8, since 1/(a(n) + 5*(-1)^(n+1)/a(n)) = b(n) - b(n+1), where b(n) = (1/4) * (a(n) + a(n-1)) / (a(n)*a(n-1)).
Sum_{n >= 1} (-1)^(n+1)/(a(n) + 5*(-1)^(n+1)/a(n)) = 1/8, since 1/(a(n) + 5*(-1)^(n+1)/a(n)) = c(n) + c(n+1), where c(n) = (1/4) * (a(n) - a(n-1)) / (a(n)*a(n-1)). (End)

Chebyshev comments from Wolfdieter Lang, Jan 10 2003

A033887 a(n) = Fibonacci(3*n + 1).

Original entry on oeis.org

1, 3, 13, 55, 233, 987, 4181, 17711, 75025, 317811, 1346269, 5702887, 24157817, 102334155, 433494437, 1836311903, 7778742049, 32951280099, 139583862445, 591286729879, 2504730781961, 10610209857723, 44945570212853, 190392490709135, 806515533049393, 3416454622906707

Offset: 0

N. J. A. Sloane

Binomial transform of A063727, and second binomial transform of (1,1,5,5,25,25,...), which is A074872 with offset 0. - Paul Barry, Jul 16 2003
Equals INVERT transform of A104934: (1, 2, 8, 28, 100, 356, ...) and INVERTi transform of A005054: (1, 4, 20, 100, 500, ...). - Gary W. Adamson, Jul 22 2010
a(n) is the number of compositions of n when there are 3 types of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010
F(3*n+1) = 3^n*a(n;2/3), where a(n;d), n = 0, 1, ..., d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also the papers by Witula et al.). - Roman Witula, Jul 12 2012
We note that the remark above by Paul Barry can be easily obtained from the following scaling identity for delta-Fibonacci numbers y^n a(n;x/y) = Sum_{k=0..n} binomial(n,k) (y-1)^(n-k) a(k;x) and the fact that a(n;2)=5^floor(n/2). Indeed, for x=y=2 we get 2^n a(n;1) = Sum_{k=0..n} binomial(n,k) a(k;2) and, by A000045: Sum_{k=0..n} binomial(n,k) 2^k a(k;1) = Sum_{k=0..n} binomial(n,k) F(k+1) 2^k = 3^n a(n;2/3) = F(3n+1). - Roman Witula, Jul 12 2012
Except for the first term, this sequence can be generated by Corollary 1 (iv) of Azarian's paper in the references for this sequence. - Mohammad K. Azarian, Jul 02 2015
Number of 1’s in the substitution system {0 -> 110, 1 -> 11100} at step n from initial string "1" (1 -> 11100 -> 111001110011100110110 -> ...). - Ilya Gutkovskiy, Apr 10 2017
The o.g.f. of {F(m*n + 1)}A000045%20and%20L%20=%20A000032.%20-%20_Wolfdieter%20Lang">{n>=0}, for m = 1, 2, ..., is G(m,x) = (1 - F(m-1)*x) / (1 - L(m)*x + (-1)^m*x^2), with F = A000045 and L = A000032. - _Wolfdieter Lang, Feb 06 2023

			a(5) = Fibonacci(3*5 + 1) = Fibonacci(16) = 987. - _Indranil Ghosh_, Feb 04 2017

Indranil Ghosh, Table of n, a(n) for n = 0..1592
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, 7(38) (2012), 1871-1876.
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010), #10.8.2, Example 13.
Gary Detlefs and Wolfdieter Lang, Improved Formula for the Multi-Section of the Linear Three-Term Recurrence Sequence, arXiv:2304.12937 [math.CO], 2023.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013), #13.4.5.
Edyta Hetmaniok, Bożena Piątek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Mathematics, 15(1) (2017), 477-485.
Tanya Khovanova, Recursive Sequences.
Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Mathematica, 46(1) (2013), 15-27.
Roman Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009), 310-329, MR2555042.
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A000032, A000045, A104934, A005054, A063727 (inverse binomial transform), A082761 (binomial transform), A001076, A001077.

Cf. A016777, A049310, A049651, A074872, A122070, A167808, A185384.

[Fibonacci(3*n+1): n in [0..100]]; // Vincenzo Librandi, Apr 17 2011

Fibonacci[Range[1,5!,3]] (* Vladimir Joseph Stephan Orlovsky, May 18 2010 *)

a(n)=fibonacci(3*n+1) \\ Charles R Greathouse IV, Feb 03 2014

Vec((1-x)/(1-4*x-x^2) + O(x^100)) \\ Altug Alkan, Dec 10 2015

a(n) = A001076(n) + A001077(n) = A001076(n+1) - A001076(n).
a(n) = 2*A049651(n) + 1.
a(n) = 4*a(n-1) + a(n-2) for n>1, a(0)=1, a(1)=3;
G.f.: (1 - x)/(1 - 4*x - x^2).
a(n) = ((1 + sqrt(5))*(2 + sqrt(5))^n - (1 - sqrt(5))*(2 - sqrt(5))^n)/(2*sqrt(5)).
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(n,j)*C(n-j,k)*F(n-j+1). - Paul Barry, May 19 2006
First differences of A001076. - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009
a(n) = A167808(3*n+1). - Reinhard Zumkeller, Nov 12 2009
a(n) = Sum_{k=0..n} C(n,k)*F(n+k+1). - Paul Barry, Apr 19 2010
Let p[1]=3, p[i]=4, (i>1), and A be a Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1] (i <= j), A[i,j]=-1 (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = det A. - Milan Janjic, Apr 29 2010
a(n) = Sum_{i=0..n} C(n,n-i)*A063727(i). - Seiichi Kirikami, Mar 06 2012
a(n) = Sum_{k=0..n} A122070(n,k) = Sum_{k=0..n} A185384(n,k). - Philippe Deléham, Mar 13 2012
a(n) = A000045(A016777(n)). - Michel Marcus, Dec 10 2015
a(n) = F(2*n)*L(n+1) + F(n-1)*(-1)^n for n > 0. - J. M. Bergot, Feb 09 2016
a(n) = Sum_{k=0..n} binomial(n,k)*5^floor(k/2)*2^(n-k). - Tony Foster III, Sep 03 2017
2*a(n) = Fibonacci(3*n) + Lucas(3*n). - Bruno Berselli, Oct 13 2017
a(n)^2 is the denominator of continued fraction [4,...,4, 2, 4,...,4], which has n 4's before, and n 4's after, the middle 2. - Greg Dresden and Hexuan Wang, Aug 30 2021
a(n) = i^n*(S(n, -4*i) + i*S(n-1, -4*i)), with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. From the simplified trisection formula. See the first entry above with A001076. - Gary Detlefs and Wolfdieter Lang, Mar 06 2023
E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) + sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, May 24 2024

A077259 First member of the Diophantine pair (m,k) that satisfies 5*(m^2 + m) = k^2 + k; a(n) = m.

Original entry on oeis.org

0, 2, 6, 44, 116, 798, 2090, 14328, 37512, 257114, 673134, 4613732, 12078908, 82790070, 216747218, 1485607536, 3889371024, 26658145586, 69791931222, 478361013020, 1252365390980, 8583840088782, 22472785106426, 154030760585064, 403257766524696, 2763969850442378

Offset: 0

Bruce Corrigan (scentman(AT)myfamily.com), Nov 01 2002

			a(3) = (2*6) - 2 + (2*17) = 12 - 2 + 34 = 44.
G.f. = 2*x + 6*x^2 + 44*x^3 + 116*x^4 + 798*x^5 + 2090*x^6 + 14328*x^7 + ... - _Michael Somos_, Jul 15 2018

G. C. Greubel, Table of n, a(n) for n = 0..1000
Jeremiah Bartz, Bruce Dearden, and Joel Iiams, Counting families of generalized balancing numbers, The Australasian Journal of Combinatorics (2020) Vol. 77, Part 3, 318-325.
Vladimir Pletser, Recurrent Relations for Multiple of Triangular Numbers being Triangular Numbers, arXiv:2101.00998 [math.NT], 2021.
Vladimir Pletser, Closed Form Equations for Triangular Numbers Multiple of Other Triangular Numbers, arXiv:2102.12392 [math.GM], 2021.
Vladimir Pletser, Triangular Numbers Multiple of Triangular Numbers and Solutions of Pell Equations, arXiv:2102.13494 [math.NT], 2021.
Vladimir Pletser, Using Pell equation solutions to find all triangular numbers multiple of other triangular numbers, 2022.
Hermann Stamm-Wilbrandt, 6 interlaced bisections
Index entries for linear recurrences with constant coefficients, signature (1,18,-18,-1,1).

Cf. A007805, A077260, A077261, A077262.

Cf. A053141.

R:=PowerSeriesRing(Integers(), 30); [0] cat Coefficients(R!(2*x*(x+1)^2/((1-x)*(x^2-4*x-1)*(x^2+4*x-1)))); // G. C. Greubel, Jul 15 2018

f := gfun:-rectoproc({a(-2) = 2, a(-1) = 0, a(0) = 0, a(1) = 2, a(n) = 18*a(n - 2) - a(n - 4) + 8}, a(n), remember): map(f, [$ (0 .. 40)])[]; # Vladimir Pletser, Jul 24 2020

LinearRecurrence[{1, 18, -18, -1, 1}, {0, 2, 6, 44, 116}, 30] (* G. C. Greubel, Jul 15 2018 *)
a[ n_] := With[{m = Max[n, -1 - n]}, SeriesCoefficient[ 2 x (x + 1)^2 / ((1 - x) (x^2 - 4 x - 1) (x^2 + 4 x - 1)), {x, 0, m}]]; (* Michael Somos, Jul 15 2018 *)

my(x='x+O('x^30)); concat([0], Vec(2*x*(x+1)^2/((1-x)*(x^2-4*x-1)*(x^2+4*x-1)))) \\ G. C. Greubel, Jul 15 2018

Let b(n) be A007805(n). Then with a(0)=0, a(1)=2, a(2*n+2) = 2*a(2*n+1) - a(2*n) + 2*b(n), a(2*n+3) = 2*a(2*n+2) - a(2*n+1) + 2*b(n+1).
a(n) = (A000045(A007310(n+1))-1)/2. - Vladeta Jovovic, Nov 02 2002 [corrected by R. J. Mathar, Sep 16 2009]
a(0)=0, a(1)=2, a(n+2) = 4 + 9*a(n) + 2*sqrt(1 +20*a(n) +20*a(n)^2). - Herbert Kociemba, May 12 2008
a(0)=0, a(1)=2, a(2)=6, a(3)=44, a(n) = 18*a(n-2) - a(n-4) + 8. - Robert Phillips, Sep 01 2008
G.f.: 2*x*(1+x)^2/((1-x)*(1+4*x-x^2)*(1-4*x-x^2)). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009
a(n) = a(-1-n) for all n in Z. - Michael Somos, Jul 15 2018
a(2*n) = A049651(2*n); a(2*n+1) = A110679(2*n+1). See "6 interlaced bisections" link. - Hermann Stamm-Wilbrandt, Apr 18 2019
a(n) = a(n-1) + 18*a(n-2) - 18*a(n-3) - a(n-4) + a(n-5). - Wesley Ivan Hurt, Jul 24 2020
From Vladimir Pletser, Feb 07 2021: (Start)
a(n) = ((5+sqrt(5))*(2+sqrt(5))^n + (5-sqrt(5))*(2-sqrt(5))^n)/20 - 1/2 for even n;
a(n) = ((5+3*sqrt(5))*(2+sqrt(5))^n + (5-3*sqrt(5))*(2-sqrt(5))^n)/20 - 1/2 for odd n. (End)

More terms from Colin Barker, Mar 23 2014

A110679 a(n+3) = 3a(n+2) + 5a(n+1) + a(n), a(0) = 1, a(1) = 2, a(2) = 11.

Original entry on oeis.org

1, 2, 11, 44, 189, 798, 3383, 14328, 60697, 257114, 1089155, 4613732, 19544085, 82790070, 350704367, 1485607536, 6293134513, 26658145586, 112925716859, 478361013020, 2026369768941, 8583840088782, 36361730124071, 154030760585064, 652484772464329

Offset: 0

Creighton Dement, Aug 02 2005

2tesseq[A*B*cyc(A)] (see program code) gives an alternative formula for A110528.

a(n) is the number of tilings of a 2 X n rectangle by using 1 X 1 squares, dominoes and right trominoes. - Roberto Tauraso, Mar 21 2017

Colin Barker, Table of n, a(n) for n = 0..1000
Robert Munafo, Sequences Related to Floretions
Hermann Stamm-Wilbrandt, 6 interlaced bisections
Index entries for linear recurrences with constant coefficients, signature (3,5,1).

Cf. A110528, A110680, A001076, A110526, A110526, A033887.

[(Fibonacci(3*n+2) +(-1)^n)/2: n in [0..30]]; // G. C. Greubel, Apr 19 2019

seriestolist(series((-1+x)/((x+1)*(x^2+4*x-1)), x=0,25)); -or- Floretion Algebra Multiplication Program, FAMP Code: -1jesseq[A*B*cyc(A)] with A = - 'j + 'k - 'ii' - 'ij' - 'ik' and B = - .5'i - .5i' - .5'ii' + .5'jj' - .5'kk' + .5'jk' + .5'kj' - .5e

a[n_] := (Fibonacci[3*n+2] + (-1)^n)/2; a /@ Range[0, 22] (* Giovanni Resta, Mar 21 2017 *)

Vec((1 - x) / ((1 + x)*(1 - 4*x - x^2)) + O(x^30)) \\ Colin Barker, Mar 21 2017

{a(n) = -(-1)^n * (fibonacci(-2 - 3*n)\2)}; /* Michael Somos, Mar 26 2017 */

[(fibonacci(3*n+2) +(-1)^n)/2 for n in (0..30)] # G. C. Greubel, Apr 19 2019

Program "FAMP" finds: 2*(-1^(n+1)) = A110528(n) - A001076(n+1) - 2*a(n). Program "Superseeker" finds: a(n) = A110526(n+1) - A110526(n); a(n) + a(n+1) = A033887(n+1).
a(n) = (-1)^n*Sum_{k=0..n} (-1)^k*Fibonacci(3*k+1). - Gary Detlefs, Jan 22 2013
a(n) = (Fibonacci(3*n+2)+(-1)^n)/2. - Roberto Tauraso, Mar 21 2017
From Colin Barker, Mar 21 2017: (Start)
G.f.: (1 - x) / ((1 + x)*(1 - 4*x - x^2)).
a(n) = 3*a(n-1) + 5*a(n-2) + a(n-3) for n>2.
(End)
a(n) = -(-1)^n * A049651(-1 - n) for all n in Z. - Michael Somos, Mar 26 2017
a(2*n) = A254627(2*n+1); a(2*n+1) = A077259(2*n+1). See "6 interlaced bisections" link. - Hermann Stamm-Wilbrandt, Apr 18 2019
2*a(n) = A015448(n+1)+(-1)^n. - R. J. Mathar, Oct 03 2021

Typo in program code fixed by Creighton Dement, Dec 11 2009

A214973 Number of terms in greedy representation of n using Fibonacci and Lucas numbers.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 2, 3, 3, 3, 3, 2, 3, 3, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3

Offset: 1

Clark Kimberling, Oct 20 2012

nonn

Consider the sequence b = A116470 consisting of all the Fibonacci numbers and Lucas numbers.  For n>=0, let k(1) be the greatest k in the basis b = {b(k)} such that b(k) <= n, let k(2) be the greatest k in b such that k <= n-b(k(1)), and so on, resulting in the greedy b-representation (to be abbreviated as "rep") of n.  For comparison with the rep using A000045 as basis (called Zeckendorf, or Fibonacci, rep) and also with the rep using A000032 as basis (called the Lucas rep), it is natural to ask this:  what terms in b can possibly follow a given term b(k)?  The answer follows.
If b(k) < 21 = b(11), the terms that can follow b(k) are easily found and not recorded here.  Otherwise, if k is odd, then b(k) can be followed by b(k-i) for some i>=5; if k is even, then b(k) can be followed by b(k-i) for some i>=8.  In Zeckendorf and Lucas reps, the "lag" is k-i for i>=2.
Conjecture: a(A049651(n)) = n and this is the first instance of n in the sequence for all n > 0. In other words, apart from its initial term, A049651 is the RECORDS transform of this sequence. - Charles R Greathouse IV, Oct 14 2021

			Let F, L, U denote the Fibonacci (aka Zeckendorf), Lucas, and greedy F-union-L representations.  Then 45 = 34+8+3 (F) = 29+11+4+1 (L) = 34+11 (U), which shows that a(45) = 2 and that the U representation of 45 requires fewer terms than the others; 45 is the least number having this property.

Clark Kimberling, Table of n, a(n) for n = 1..10000
Jon Maiga, Computer-generated formulas for A214973, Sequence Machine.

Cf. A000032, A000045, A007895, A116470.

s = Reverse[Union[Flatten[Table[{Fibonacci[n + 1], LucasL[n - 1]}, {n, 1, 22}]]]]; Map[Length[Select[Reap[FoldList[(Sow[Quotient[#1, #2]]; Mod[#1, #2]) &, #, s]]
[[2, 1]], # > 0 &]] &, Range[120]]
(* Peter J. C. Moses, Oct 18 2012 *)

w(n)=if(n%2, fibonacci(n\2+3), fibonacci(n\2) + fibonacci(n\2+2));
k(n)=if(n<9, return(if(n==6,5,n))); for(i=8,n, if(w(i)>n, return(w(i-1))));
a(n)=my(s); while(n, n-=k(n); s++); s; \\ Charles R Greathouse IV, Oct 14 2021

Conjecture: a(n) = A329320(A048679(n)) for n > 0 (noticed by Sequence Machine). - Mikhail Kurkov, Oct 13 2021

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

Original entry on oeis.org

1, 0, 3, 0, 8, 0, 21, 0, 55, 0, 144, 0, 377, 0, 987, 0, 2584, 0, 6765, 0, 17711, 0, 46368, 0, 121393, 0, 317811, 0, 832040, 0, 2178309, 0, 5702887, 0, 14930352, 0, 39088169, 0, 102334155, 0, 267914296, 0, 701408733, 0, 1836311903, 0, 4807526976, 0

Offset: 0

Roger L. Bagula, Nov 08 2008

S(n,sqrt(5)), with the Chebyshev polynomials A049310, is an integer sequence in the real quadratic number field Q(sqrt(5)) with basis numbers <1,phi>, phi:=(1+sqrt(5))/2. S(n,sqrt(5)) = A(n) + 2*B(n)*phi, with A(n) = A005013(n+1)*(-1)^n and B(n) = a(n-1), n>=0, with a(-1)=0. - Wolfdieter Lang, Nov 24 2010
The sequence (s(n)) given by s(0) = 0 and s(n) = a(n-1) for n > 0 is the p-INVERT of (0, 1, 0, 1, 0, 1, ...) using p(S) = 1 - S^2; see A291219. - Clark Kimberling, Aug 30 2017
From Jean-François Alcover, Sep 24 2017: (Start)
Consider this array of successive differences:
    0,   0,    0,   1,    0,    3,    0,    8,    0,     21, ...
    0,   0,    1,  -1,    3,   -3,    8,   -8,    21,   -21, ...
    0,   1,   -2,   4,   -6,   11,  -16,   29,   -42,    76, ...
    1,  -3,    6, -10,   17,  -27,   45,  -71,   118,  -186, ...
   -4,   9,  -16,  27,  -44,   72, -116,  189,  -304,   495, ...
   13, -25,   43, -71,  116, -188,  305, -493,   799, -1291, ...
  -38,  68, -114, 187, -304,  493, -798, 1292, -2090,  3383, ...
...
First row = even-index Fibonacci numbers with interleaved zeros = this sequence right-shifted 3 positions.
Main diagonal = 0,0,-2,-10,-44,-188,-798,... = -A099919 right-shifted.
First upper subdiagonal = 0,1,4,17,72,305,1292,... = A001076 right-shifted.
Second upper subdiagonal = 0,-1,-6,-27,-116,-493,-2090,... = -A049651.
Third upper subdiagonal = 1,3,11,45,189,799,3383,... = A292278.
(End) (Comment based on an e-mail from Paul Curtz)

			G.f. = 1 + 3*x^2 + 8*x^4 + 21*x^6 + 55*x^8 + 144*x^10 + 377*x^12 + 987*x^14 + ...

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,3,0,-1).

Cf. A000045, A001076, A001906, A005013, A049310.

Cf. A049651, A088305, A099919, A291219, A292278.

[(1+(-1)^n)*Fibonacci(n+2)/2: n in [0..60]]; // G. C. Greubel, Oct 25 2022

f[x_]= -1 -x +x^2; CoefficientList[Series[-1/(x^2*f[x]*f[1/x]), {x,0,60}], x]
(* or *)
M={{0,1,0,0}, {0,0,1,0}, {0,0,0,1}, {-1,0,3,0}}; v[0]= {1,0,3,0}; v[n_]:= v[n]= M.v[n-1]; Table[v[n][[1]], {n,0,60}]
LinearRecurrence[{0,3,0,-1}, {1,0,3,0}, 60] (* Jean-François Alcover, Sep 23 2017 *)

Vec(1/(1 - 3*x^2 + x^4)+O(x^99)) \\ Charles R Greathouse IV, Sep 23 2012

[((n+1)%2)*fibonacci(n+2) for n in range(60)] # G. C. Greubel, Oct 25 2022

O.g.f.: 1/(1 - 3*x^2 + x^4).
a(2*k) = F(2*(k+1)), a(2*k+1) = 0, k>=0, with F(n)=A000045(n). - Richard Choulet, Nov 13 2008
a(n) + a(n-1) + a(n-2) = A005013(n + 1). - Michael Somos, Apr 13 2012
a(n) = (2^(-2-n)*((1 + (-1)^n)*((-3+sqrt(5))*(-1+sqrt(5))^n + (1+sqrt(5))^n*(3+sqrt(5)))))/sqrt(5). - Colin Barker, Mar 28 2016

A345253 Maximal Fibonacci tree: Arrangement of the positive integers as labels of a complete binary tree.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 13, 11, 14, 16, 21, 12, 15, 17, 22, 18, 23, 26, 34, 19, 24, 27, 35, 29, 37, 42, 55, 20, 25, 28, 36, 30, 38, 43, 56, 31, 39, 44, 57, 47, 60, 68, 89, 32, 40, 45, 58, 48, 61, 69, 90, 50, 63, 71, 92, 76, 97, 110, 144, 33, 41, 46, 59, 49

Offset: 1

J. Parker Shectman, Jun 12 2021

Every positive integer occurs exactly once, so that, as a sequence, a(n) is a permutation of the positive integers.
Descending from the root node 1, generate tree by outer composition of L(n) = n + F(Finv(n)) and R(n) = n + F(Finv(n) + 1), respectively, according to left or right branching, where F(n) = A000045(n) are the Fibonacci numbers and Finv(n) = A130233(n) is the 'lower' Fibonacci inverse. This produces each number by maximal Fibonacci expansion (cf. example below of Method 2, entry A343152, and links).
(Level of tree): The number of terms in this expansion of n is the level of the tree on which n appears, A112310(n-1) + 1 = A200648(n+1). The number of terms in the expansion of a(n) is floor(log_2(n)) + 1 = A113473(n) = A070939(n) = A029837(n+1).
"Maximal Fibonacci expansion" maximizes the sum of coefficients over all Fibonacci numbers (of positive index), allowing both F(1) = 1 and F(2) = 1. Thus, it is just an expansion and not a representation (like "greedy" and "lazy"), as it "breaks the rule" by using two bits that correspond to elements of equal value, rather than using distinct basis elements (link). This reveals connections to the cf. sequences: Binary strings that emerge in lexicographic order from "maximal Fibonacci gaps" (example), binary trees of the positive integers, and I-D arrays "harvested" from the trees. To define the expansion uniquely, always include F(1), so that the expansion of positive integer n equals F(1) for n = 1 and F(1) prepended to the lazy Fibonacci representation of n-1 for n > 1. Hence, a(1) = 1, and for n > 1, a(n) = A095903(n-1) + 1. The "redundant" expansion arranges the positive integers in the single binary tree {T(n,k)}, rather than the two trees at A255773 and A255774 that result from representation (see link).
(Left-to-right order in tree): Each F(t)-sized block (F(t+1), ..., F(t+2) - 1) of successive positive integers ("Fibonacci cohort" t) appears in right-to-left order in the tree as reordered in A343152, where elements of each cohort appear consecutively (see link).
Descending from the root node 1, generate tree by the inner composition of A026351 and A026352, that is, one plus the sequences of lower and upper Wythoff numbers, A000201 and A001950, respectively, according to left or right branching (see example below of Method 1 and links).
Generate tree from (one plus) the number of (initial) zeros on the positive integers for the outer composition of sequences, A060143 and A060144, respectively, according to left or right branching descending from the identity (c.f example below of Method 3 and links).
The lower Wythoff numbers, A000201, appear exclusively in the 1st, 3rd, 5th, ... right clades of the tree, while the upper Wythoff numbers A001950, appear exclusively in the 2nd, 4th, 6th, ... right clades of the tree. Here, the k-th right clade comprises the nodes at positions 2^(k+1) and 2^k + 1, together with all descendants of the latter (link).
(Duality with tree A232560, and related arrays): Consider the labeled binary trees a(n) = A232560(A059893(n)) and A232560(n) = a(A059893(n)). Labels along maximal straight paths that always branch left in a(n) give rows of array A345252, while labels along maximal straight paths that always branch left in A232560 give rows of array A083047.
Sorting the labels from each successive right clade of the binary tree a(n) gives the successive columns of A083047, while sorting labels from each successive right clade of A232560 gives each successive column of A345252. This makes the trees a(n) and A232560 "blade-duals," blade being a contraction of branch-clade (see entry for A345254 and link). A200648(n)+1 gives the level of the tree on which elements of array first-columns A345252(n,1) and A083047(n,1) appear.
(Palindromes and coincidence of elements): Trees a(n) and A232560 coincide when the sequence of left and right branching is a palindrome: a(A329395(n)) = A232560(A329395(n)). As Kimberling notes (cf. A059893), this happens at fixed points of A059893(n) or, equivalently, at n for which A081242(n) is a palindrome.
The inverse permutation of a(n) as a sequence can be read from a "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row t, for t = 1, 2, 3, ..., in which an entry on row t is 2*x the entry x immediately above it on row t-1, if such exists, or otherwise 2*x + 1 the entry x in the corresponding position on row t-2 (thus generating new rows as in A243571 but without sorting the numbers into increasing order, linked reference):
                               1,
                               2,
                           3,  4,
                       5,  6,  8,
               7,  9, 10, 12, 16,
  11, 13, 17, 14, 18, 20, 24, 32,
  ...
With the right-justified tableau substituted by a left-justified tableau, the same procedure yields the inverse permutation for the "minimal Fibonacci tree," A048680(A059893(n)), the "cohort-dual" tree of a(n), where "cohort" t is the F(t)-sized block of successive entries in the tableau (see entry for A345252, linked reference).
(Coincidence of elements): a(A020988(n)) = A048680(A059893(A020988(n))) = A099919(n) and a(A020989(n)) = A048680(A059893(A020989(n))) = A049651(n). Collectively, a(A061547(n)) = A048680(A059893(A061547(n))) = union(A049651(n), A099919(n)).
With two types of duality, the tree forms a quartet of binary-tree arrangements of the positive integers, together with its blade dual A232560, its cohort dual A048680(A059893), and blade dual A048680 of the latter.
Order in the tree is "memory-less": Let a(n) and a(m) label nodes at positions n and m, respectively. Let d1 and d2 be two descending paths, i.e., sequences branching left or right from a starting node. (Nodal positions for the left and right children of the node at position p are given by 2*p and 2*p + 1, resp., and d1 and d2 are compositions of these.) Then a(d1(n)) < a(d2(n)) if and only if a(d1(m)) < a(d2(m)) (linked reference).

			As a complete binary tree:
                    1
           /                 \
          2                   3
      /       \          /        \
     4         5        6          8
    / \       / \      / \        / \
   7    9    10   13   11   14   16   21
  / \  / \  /  \ /  \ /  \ /  \ /  \ /  \
  ...
By maximal Fibonacci expansion:
                                        F(1)
                      /                                       \
                F(1) + F(2)                               F(1) + F(3)
           /                    \                    /                  \
  F(1) + F(2) + F(3)   F(1) + F(2) + F(4)   F(1) + F(3) + F(4)   F(1) + F(3) + F(5)
  ...
"Fibonacci gaps," or differences between successive indices in maximal Fibonacci expansion above, are A007931(n-1) for n > 1 (see link):
                   *
          /                  \
         1                    2
     /       \           /        \
    11        12        21        22
   /  \      /  \      /  \      /  \
  111  112  121  122  211  212  221  222
  / \  / \  / \  / \  / \  / \  / \  / \
  ...
In examples of the three methods below:
Branch left-right-right down the tree to arrive at nodal position n = 2*(2*(2*1) + 1) + 1 = 11;
Branch right-left-left down the tree to arrive at nodal position n = 2*(2*(2*1 + 1)) = 12.
Tree by inner composition of (one plus) the lower and upper Wythoff sequences, A000201 and A001950 (Method 1):
a(11) = A000201(A001950(A001950(1) + 1) + 1) + 1 = 13.
a(12) = A001950(A000201(A000201(1) + 1) + 1) + 1 = 11.
Tree by (outer) composition of branching functions L(n) = n + F(Finv(n)) and R(n) = n + F(Finv(n) + 1), where F(n) = A000045(n) and Finv(n) = A130233(n) (Method 2):
a(11) = R(R(L(1))) = 13.
a(12) = L(R(R(1))) = 11.
Tree by outer composition of A060143 and A060144 (Wythoff inverse sequences) (Method 3):
a(11) = 13, position of first nonzero in A060144(A060144(A060143(m))) = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ..., for m = 1, 2, 3, ....
a(12) = 11, position of first nonzero in A060143(A060143(A060144(m))) = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ..., for m = 1, 2, 3, ....

Parker Shectman, A Quilt after Fibonacci, Part 2 of 3: Cohorts, Free Monoids, and Numeration
J. Parker Shectman, Mathematica codes for generating A345253 as a binary tree

Cf. A000045, A000201, A001950, A007931, A020988, A020989, A026351, A026352, A029837, A048680, A049651, A059893, A061547, A070939, A081242, A083047, A095903, A099919, A112310, A113473, A130233, A200648, A232560, A243571, A255773, A255774, A329395, A343152, A345252, A345254.

(* For binary tree implementations, see supporting file under LINKS *)
a[n_] := (x = 0; y = 0; BDn = Reverse[IntegerDigits[n, 2]]; imax = Length[BDn] - 1; For[i = 0, i <= imax, i++, {x, y} = {y + 1, x + y}; If[BDn[[i + 1]] == 1, {x, y} = {y, x + y}]]; y);
(* Adapted from PARI code of Kevin Ryde *)

a(n) = my(x=0,y=0); for(i=0,logint(n,2), [x,y]=[y+1,x+y]; if(bittest(n,i), [x,y]=[y,x+y])); y; \\ Kevin Ryde, Jun 19 2021

a(1) = 1 and for n > 1, a(n) = A095903(n-1) + 1.

a(n) = A232560(A059893(n)).

A294262 a(n) = 3a(n-1) + 5a(n-2) + a(n-3), with a(0) = a(1) = 1 and a(2) = 7, a linear recurrence which is a trisection of A005252.

Original entry on oeis.org

1, 1, 7, 27, 117, 493, 2091, 8855, 37513, 158905, 673135, 2851443, 12078909, 51167077, 216747219, 918155951, 3889371025, 16475640049, 69791931223, 295643364939, 1252365390981, 5305104928861, 22472785106427, 95196245354567, 403257766524697, 1708227311453353, 7236167012338111, 30652895360805795, 129847748455561293, 550043889183050965

Offset: 0

Jean-François Alcover and Paul Curtz, Oct 26 2017

Hermann Stamm-Wilbrandt, 6 interlaced bisections
Index entries for linear recurrences with constant coefficients, signature (3,5,1).

Cf. A001076, A005252, A110679.

[(Fibonacci(3*n+1) +(-1)^n)/2 : n in [0..30]]; // G. C. Greubel, Apr 19 2019

Mathematica
```
LinearRecurrence[{3,5,1},{1,1,7},30]
```

{a(n) = (fibonacci(3*n+1) +(-1)^n)/2}; \\ G. C. Greubel, Apr 19 2019

[(fibonacci(3*n+1) +(-1)^n)/2 for n in (0..30)] # G. C. Greubel, Apr 19 2019

a=1
b=1
c=7
print 0," ",a,"\n"
print 1," ",b,"\n"
print 2," ",c,"\n"
for(x=3;x<=1000;++x){
d=3*c+5*b+1*a
print x," ",d,"\n"
a=b
b=c
c=d
} # Hermann Stamm-Wilbrandt, Apr 18 2019

G.f.: (1 - 2*x - x^2)/(1 - 3*x - 5*x^2 - x^3).
a(n) = (1/20)*(10*(-1)^n + (2-sqrt(5))^n*(5-sqrt(5)) + (2+sqrt(5))^n*(5+sqrt(5))).
a(n) = A005252(3*n).
a(n) = 4*a(n-1) + a(n-2) + 2*(-1)^n for n >= 2.
a(n) = Sum_{k=0..floor(3*n/4)} binomial(3*n-2*k, 2*k).
a(n) = A110679(n) - A001076(n).
a(n) = (Fibonacci(3*n + 1) + (-1)^n)/2.
a(2*n) = A232970(2*n); a(2*n+1) = A049651(2*n+1). See "6 interlaced bisections" link. - Hermann Stamm-Wilbrandt, Apr 18 2019

A307268 Partial sums of the Lucas numbers of the form L(3n+2) (A163063).

Original entry on oeis.org

3, 14, 61, 260, 1103, 4674, 19801, 83880, 355323, 1505174, 6376021, 27009260, 114413063, 484661514, 2053059121, 8696898000, 36840651123, 156059502494, 661078661101, 2800374146900, 11862575248703, 50250675141714, 212865275815561, 901711778403960, 3819712389431403

Offset: 0

Rigoberto Florez, Apr 01 2019

			L(2) + L(5) = 14;
L(2) + L(5) + L(8) = 61;
L(2) + L(5) + L(8) + L(11) = 260.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-3,-1).

Cf. A001076, A014448, A049651, A099919, A163063.

Table[(LucasL[3*n + 4] - 1)/2, {n, 0, 20}]
LinearRecurrence[{5,-3,-1},{3,14,61},30] (* Harvey P. Dale, Aug 10 2022 *)

L(n) = fibonacci(n+1)+fibonacci(n-1);
a(n) = (L(3*n+4)-1)/2; \\ Michel Marcus, Apr 01 2019

Vec((3 - x) / ((1 - x)*(1 - 4*x - x^2)) + O(x^25)) \\ Colin Barker, Apr 02 2019

a(n) = A001076(n+1) + A099919(n+1).
a(n) = Sum_{i=0..n} L(3i+2), L(i) = A000032(i).
a(n) = (L(3*n+4)-1)/2.
From Colin Barker, Apr 02 2019: (Start)
G.f.: (3 - x) / ((1 - x)*(1 - 4*x - x^2)).
a(n) = (-2 + (7-3*sqrt(5))*(2-sqrt(5))^n + (2+sqrt(5))^n*(7+3*sqrt(5))) / 4.
a(n) = 5*a(n-1) - 3*a(n-2) - a(n-3) for n > 2.
(End)

cp's OEIS Frontend

A001077 Numerators of continued fraction convergents to sqrt(5).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

A033887 a(n) = Fibonacci(3*n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A077259 First member of the Diophantine pair (m,k) that satisfies 5*(m^2 + m) = k^2 + k; a(n) = m.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A110679 a(n+3) = 3*a(n+2) + 5*a(n+1) + a(n), a(0) = 1, a(1) = 2, a(2) = 11.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A214973 Number of terms in greedy representation of n using Fibonacci and Lucas numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

A110679 a(n+3) = 3a(n+2) + 5a(n+1) + a(n), a(0) = 1, a(1) = 2, a(2) = 11.

A294262 a(n) = 3a(n-1) + 5a(n-2) + a(n-3), with a(0) = a(1) = 1 and a(2) = 7, a linear recurrence which is a trisection of A005252.