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.

A006190 a(n) = 3*a(n-1) + a(n-2), with a(0)=0, a(1)=1.

Original entry on oeis.org

0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Denominators of continued fraction convergents to (3+sqrt(13))/2. - Benoit Cloitre, Jun 14 2003
a(n) and A006497(n) occur in pairs: (a,b): (1,3), (3,11), (10,36), (33,119), (109,393), ... such that b^2 - 13a^2 = 4(-1)^n. - Gary W. Adamson, Jun 15 2003
Form the 4-node graph with matrix A = [1,1,1,1; 1,1,1,0; 1,1,0,1; 1,0,1,1]. Then this sequence counts the walks of length n from the vertex with degree 5 to one (any) of the other vertices. - Paul Barry, Oct 02 2004
a(n+1) is the binomial transform of A006138. - Paul Barry, May 21 2006
a(n+1) is the diagonal sum of the exponential Riordan array (exp(3x),x). - Paul Barry, Jun 03 2006
Number of paths in the right half-plane from (0,0) to the line x=n-1, consisting of steps U=(1,1), D=(1,-1), h=(1,0) and H=(2,0). Example: a(3)=10 because we have hh, H, UD, DU, hU, Uh, UU, hD, Dh and DD. - Emeric Deutsch, Sep 03 2007
Equals INVERT transform of A000129. Example: a(5) = 109 = (29, 12, 5, 2, 1) dot (1, 1, 3, 10, 33) = (29 + 12 + 15 + 20 + 33). - Gary W. Adamson, Aug 06 2010
For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 3's along the main diagonal, 1's along the superdiagonal and subdiagonal, and 0's everywhere else. - John M. Campbell, Jul 08 2011
These numbers could also be called "bronze Fibonacci numbers". Indeed, for n >= 1, F(n+1) = ceiling(phi*F(n)), if n is even and F(n+1) = floor(phi*F(n)), if n is odd, where phi is the golden ratio; analogously, for Pell numbers (A000129), or "silver Fibonacci numbers", P(n+1) = ceiling(delta*a(n)), if n is even and P(n+1) = floor(delta*a(n)), if n is odd, where delta = delta_S = 1 + sqrt(2) is the silver ratio. Here, for n >= 1, we have a(n+1) = ceiling(c*a(n)), if n is even and a(n+1) = floor(c*a(n)), if n is odd, where c = (3 + sqrt(13))/2 is the bronze ratio (cf. comment in A098316). - Vladimir Shevelev, Feb 23 2013
Let p(n,x) denote the Fibonacci polynomial, defined by p(1,x) = 1, p(2,x) = x, p(n,x) = x*p(n-1,x) + p(n-2,x). Let q(n,x) be the numerator polynomial of the rational function p(n, x + 1 + 1/x). Then q(n,1) = a(n). - Clark Kimberling, Nov 04 2013
The (1,1)-entry of the matrix A^n where A = [0,1,0; 1,2,1; 1,1,2]. - David Neil McGrath, Jul 18 2014
a(n+1) counts closed walks on K2, containing three loops on the other vertex. Equivalently the (1,1)-entry of A^(n+1) where the adjacency matrix of digraph is A = (0,1; 1,3). - David Neil McGrath, Oct 29 2014
For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,2,3} avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015
With offset 1 is the INVERTi transform of A001076. - Gary W. Adamson, Jul 24 2015
Apart from the initial 0, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = 1 - 3 S. See A291219. - Clark Kimberling, Sep 02 2017
From Rogério Serôdio, Mar 30 2018: (Start)
This is a divisibility sequence (i.e., if n|m then a(n)|a(m)).
gcd(a(n),a(n+k)) = a(gcd(n, k)) for all positive integers n and k. (End)
Numbers of straight-chain fatty acids involving oxo and/or hydroxy groups, if cis-/trans isomerism and stereoisomerism are neglected. - Stefan Schuster, Apr 04 2018
Number of 3-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
From Michael A. Allen, Jan 25 2023: (Start)
Also called the 3-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.
a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 3 kinds of squares available. (End)
a(n) is the number of compositions of n when there are P(k) sorts of parts k, with k,n >= 1, P(k) = A000129(k) is the k-th Pell number (see example below). - Enrique Navarrete, Dec 15 2023

Examples

			From _Enrique Navarrete_, Dec 15 2023: (Start)
From the comment on compositions with Pell number of parts, A000129(k), there are A000129(1)=1 type of 1, A000129(2)=2 types of 2, A000129(3)=5 types of 3, A000129(4)=12 types of 4, A000129(5)=29 types of 5 and A000129(6)=70 types of 6.
The following table gives the number of compositions of n=6:
Composition, number of such compositions, number of compositions of this type:
  6,              1,     70;
  5+1,            2,     58;
  4+2,            2,     48;
  3+3,            1,     25;
  4+1+1,          3,     36;
  3+2+1,          6,     60;
  2+2+2,          1,      8;
  3+1+1+1,        4,     20;
  2+2+1+1,        6,     24;
  2+1+1+1+1,      5,     10;
  1+1+1+1+1+1,    1,      1;
for a total of a(6)=360 compositions of n=6. (End).

References

  • H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
  • A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 128.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • L.-N. Machaut, Query 3436, L'Intermédiaire des Mathématiciens, 16 (1909), 62-63. - N. J. A. Sloane, Mar 08 2022

Links

Crossrefs

Row sums of Pascal's rhombus (A059317). Also row sums of triangle A054456(n, m).
Sequences with g.f. 1/(1-k*x-x^2) or x/(1-k*x-x^2): A000045 (k=1), A000129 (k=2), this sequence (k=3), A001076 (k=4), A052918 (k=5), A005668 (k=6), A054413 (k=7), A041025 (k=8), A099371 (k=9), A041041 (k=10), A049666 (k=11), A041061 (k=12), A140455 (k=13), A041085 (k=14), A154597 (k=15), A041113 (k=16), A178765 (k=17), A041145 (k=18), A243399 (k=19), A041181 (k=20).
Cf. A006497, A052906, A175182 (Pisano periods), A201001 (prime subsequence), A092936 (squares).
Cf. A243399.

Programs

  • GAP
    a:=[0,1];; for n in [3..30] do a[n]:=3*a[n-1]+a[n-2]; od; a; # Muniru A Asiru, Mar 31 2018
  • Haskell
    a006190 n = a006190_list !! n
a006190_list = 0 : 1 : zipWith (+) (map (* 3) $ tail a006190_list) a006190_list
-- Reinhard Zumkeller, Feb 19 2011
  • Magma
    [ n eq 1 select 0 else n eq 2 select 1 else 3*Self(n-1)+Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011
  • Maple
    a[0]:=0: a[1]:=1: for n from 2 to 35 do a[n]:= 3*a[n-1]+a[n-2] end do: seq(a[n],n=0..30); # Emeric Deutsch, Sep 03 2007
A006190:=-1/(-1+3*z+z**2); # Simon Plouffe in his 1992 dissertation, without the leading 0
seq(combinat[fibonacci](n,3),n=0..30); # R. J. Mathar, Dec 07 2011
  • Mathematica
    a[n_] := (MatrixPower[{{1, 3}, {1, 2}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, -1, 24}] (* Robert G. Wilson v, Jan 13 2005 *)
LinearRecurrence[{3,1},{0,1},30] (* or *) CoefficientList[Series[x/ (1-3x-x^2), {x,0,30}], x] (* Harvey P. Dale, Apr 20 2011 *)
Table[If[n==0, a1=1; a0=0, a2=a1; a1=a0; a0=3*a1+a2], {n, 0, 30}] (* Jean-François Alcover, Apr 30 2013 *)
Table[Fibonacci[n, 3], {n, 0, 30}] (* Vladimir Reshetnikov, May 08 2016 *)
  • PARI
    a(n)=if(n<1,0,contfracpnqn(vector(n,i,2+(i>1)))[2,1])
  • PARI
    a(n)=([1,3;1,2]^n)[2,1] \\ Charles R Greathouse IV, Mar 06 2014
  • PARI
    concat([0],Vec(x/(1-3*x-x^2)+O(x^30))) \\ Joerg Arndt, Apr 30 2013
  • Sage
    [lucas_number1(n,3,-1) for n in range(0, 30)] # Zerinvary Lajos, Apr 22 2009

Formula

G.f.: x/(1 - 3*x - x^2).
From Benoit Cloitre, Jun 14 2003: (Start)
a(3*n) = 2*A041019(5*n-1), a(3*n+1) = A041019(5*n), a(3*n+2) = A041019(5*n+3).
a(2*n) = 3*A004190(n-1); a(3*n) = 10*A041613(n-1) for n >= 1. (End)
From Gary W. Adamson, Jun 15 2003: (Start)
a(n-1) + a(n+1) = A006497(n).
A006497(n)^2 - 13*a(n)^2 = 4(-1)^n. (End)
a(n) = U(n-1, (3/2)i)(-i)^(n-1), i^2 = -1. - Paul Barry, Nov 19 2003
a(n) = Sum_{k=0..n-1} binomial(n-k-1,k)*3^(n-2*k-1). - Paul Barry, Oct 02 2004
a(n) = F(n, 3), the n-th Fibonacci polynomial evaluated at x=3.
Let M = {{0, 1}, {1, 3}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = Abs[v[n][[1]]]. - Roger L. Bagula, May 29 2005 [Or a(n) = [M^(n+1)]{1,1}. - _L. Edson Jeffery, Aug 27 2013]
From Paul Barry, May 21 2006: (Start)
a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(k-j).
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(n-j-k).
a(n+1) = Sum_{k=0..floor(n/2)} C(n-k,k)*3^(n-2*k).
a(n) = Sum_{k=0..n} C(k,n-k)*3^(2*k-n). (End)
E.g.f.: exp(3*x/2)*sinh(sqrt(13)*x/2)/(sqrt(13)/2). - Paul Barry, Jun 03 2006
a(n) = (ap^n - am^n)/(ap - am), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2.
Let C = (3 + sqrt(13))/2 = exp arcsinh(3/2) = 3.3027756377... Then C^n, n > 0 = a(n)*(1/C) + a(n+1). Let X = the 2 X 2 matrix [0, 1; 1, 3]. Then X^n = [a(n-1), a(n); a(n), a(n+1)]. - Gary W. Adamson, Dec 21 2007
1/3 = 3/(1*10) + 3/(3*33) + 3/(10*109) + 3/(33*360) + 3/(109*1189) + ... . - Gary W. Adamson, Mar 16 2008
a(n) = ((3 + sqrt(13))^n - (3 - sqrt(13))^n)/(2^n*sqrt(13)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009
a(p) == 13^((p-1)/2) mod p, for odd primes p. - Gary W. Adamson, Feb 22 2009
From Johannes W. Meijer, Jun 12 2010: (Start)
Limit_{k->oo} a(n+k)/a(k) = (A006497(n) + a(n)*sqrt(13))/2.
Limit_{n->oo} A006497(n)/a(n) = sqrt(13). (End)
Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (sqrt(13)-3)/2. - Vladimir Shevelev, Feb 23 2013
From Vladimir Shevelev, Feb 24 2013: (Start)
(1) Expression a(n+1) via a(n): a(n+1) = (3*a(n) + sqrt(13*a(n)^2 + 4*(-1)^n))/2;
(2) a^2(n+1) - a(n)*a(n+2) = (-1)^n;
(3) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
(4) a(n)/a(n+1) = (sqrt(13)-3)/2 + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
a(n) = sqrt(13*(A006497(n))^2 + (-1)^(n-1)*52)/13. - Vladimir Shevelev, Mar 13 2013
Sum_{n >= 1} 1/( a(2*n) + 1/a(2*n) ) = 1/3; Sum_{n >= 1} 1/( a(2*n + 1) - 1/a(2*n + 1) ) = 1/9. - Peter Bala, Mar 26 2015
From Rogério Serôdio, Mar 30 2018: (Start)
Some properties:
(1) a(n)*a(n+1) = 3*Sum_{k=1..n} a(k)^2;
(2) a(n)^2 + a(n+1)^2 = a(2*n+1);
(3) a(n)^2 - a(n-2)^2 = 3*a(n-1)*(a(n) + a(n-2));
(4) a(m*(p+1)) = a(m*p)*a(m+1) + a(m*p-1)*a(m);
(5) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
(6) a(2*n) = a(n)*(3*a(n) + 2*a(n-1));
(7) 3*Sum_{k=2..n+1} a(k)*a(k-1) is equal to a(n+1)^2 if n odd, and is equal to a(n+1)^2 - 1 if n is even;
(8) a(n) = alpha(k)*a(n-2*k+1) + a(n-4*k+2), where alpha(k) = ap^(2*k-1) + am^(2*k-1), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2;
(9) 131|Sum_{k=n..n+9} a(k), for all positive n. (End)
From Kai Wang, Feb 10 2020: (Start)
a(n)^2 - a(n+r)*a(n-r) = (-1)^(n-r)*a(r)^2 - Catalan's identity.
arctan(1/a(2n)) - arctan(1/a(2n+2)) = arctan(a(2)/a(2n+1)).
arctan(1/a(2n)) = Sum_{m>=n} arctan(a(2)/a(2m+1)).
The same formula holds for Fibonacci numbers and Pell numbers. (End)
a(n+2) = 3^(n+1) + Sum_{k=0..n} a(k)*3^(n-k). - Greg Dresden and Gavron Campbell, Feb 22 2022
G.f. = 1/(1-Sum_{k>=1} P(k)*x^k), P(k)=A000129(k) (with a(0)=1). - Enrique Navarrete, Dec 17 2023
G.f.: x/(1 - 3*x - x^2) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (m*k + 3 - m + x)/(1 + m*k*x) ) for arbitrary m (a telescoping series). - Peter Bala, May 08 2024
Sum_{n>=0} a(n)/phi^(3*n) = 1, where phi = A001622 is the golden ratio. - Diego Rattaggi, Apr 07 2025

Extensions

Second formula corrected by Johannes W. Meijer, Jun 02 2010

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

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