A027934 a(0)=0, a(1)=1, a(2)=2; for n > 2, a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3).

0, 1, 2, 5, 11, 24, 51, 107, 222, 457, 935, 1904, 3863, 7815, 15774, 31781, 63939, 128488, 257963, 517523, 1037630, 2079441, 4165647, 8342240, 16702191, 33433039, 66912446, 133899917, 267921227, 536038872, 1072395555, 2145305339

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

Number of compositions of n with at least one even part (offset 2). - Vladeta Jovovic, Dec 29 2004

First differences of A008466. a(n) = A008466(n+2) - A008466(n+1). - Alexander Adamchuk, Apr 06 2006

Starting with "1" = eigensequence of a triangle with the Fibonacci series as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010

An elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 11 and 416, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A099036 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010

a(n) = Sum_{k=1..n} A108617(n,k) / 2. - Reinhard Zumkeller, Oct 07 2012

a(n) is the number of binary strings that contain the substring 11 or end in 1. a(3) = 5 because we have: 001, 011, 101, 110, 111. - Geoffrey Critzer, Jan 04 2014

a(n-1), n >= 1, is the number of nonexisting (due to the maturation delay) "[male-female] pairs of Fibonacci rabbits" at the beginning of the n-th month. - Daniel Forgues, May 06 2015

a(n-1) is the number of subsets of {1,2,..,n} that contain n that have at least one pair of consecutive integers. For example, for n=5, a(4) = 11 and the 11 subsets are {4,5}, {1,2,5}, {1,4,5}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}. Note that A008466(n) is the number of all subsets of {1,2,..,n} that have at least one pair of consecutive integers. - Enrique Navarrete, Aug 15 2020

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Patrick Letendre, Polynomials with integer roots, arXiv:1911.00480 [math.NT], 2019. See p. 4.
• Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
• Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
• Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
• OEIS Wiki, Fibonacci rabbits
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Crossrefs

Row sums of triangle A131767. - Gary W. Adamson, Jul 13 2007

a(n) = A101220(1, 2, n+1).

T(n, n) + T(n, n+1) + ... + T(n, 2n), T given by A027926.

Diagonal sums of A055248.

Cf. A000045, A000079, A008466, A059570, A099036, A047967, A000032.

Programs

GAP

List([0..35], n-> 2^n - Fibonacci(n+1) ); # G. C. Greubel, Sep 27 2019

Haskell

a027934 n = a027934_list !! n
a027934_list = 0 : 1 : 2 : zipWith3 (\x y z -> 3 * x - y - 2 * z)
               (drop 2 a027934_list) (tail a027934_list) a027934_list
-- Reinhard Zumkeller, Oct 07 2012

Magma

[2^n - Fibonacci(n+1): n in [0..35]]; // G. C. Greubel, Sep 27 2019

Maple

A027934:= proc(n) local K; K:= Matrix ([[2,0,0], [0,1,1], [0,1,0]])^n; K[1,1]-K[2,2] end: seq (A027934(n), n=0..31); # Alois P. Heinz, Jul 28 2008
a := n -> 2^n - combinat:-fibonacci(n+1): seq(a(n),n=0..31); # Peter Luschny, May 09 2015

Mathematica

nn=31; a:=1/(1-x-x^2); b:=1/(1-2x); CoefficientList[Series[a*x*(1+x*b), {x,0,nn}], x] (* Geoffrey Critzer, Jan 04 2014 *)
LinearRecurrence[{3,-1,-2}, {0,1,2}, 32] (* Jean-François Alcover, Jan 09 2016 *)
nxt[{a_,b_,c_}]:={b,c,3c-b-2a}; NestList[nxt,{0,1,2},40][[;;,1]] (* Harvey P. Dale, Feb 02 2025 *)

PARI

a(n)=2^n-fibonacci(n+1) \\ Charles R Greathouse IV, Jun 11 2015

Sage

[2^n - fibonacci(n+1) for n in (0..35)] # G. C. Greubel, Sep 27 2019

Formula

a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..n-2*j} binomial(n-j, n-2*j-k). - Paul Barry, Feb 07 2003

From Paul Barry, Jan 23 2004: (Start)

Row sums of A105809.

G.f.: x*(1-x)/((1-2*x)*(1-x-x^2)).

a(n) = 2^n - Fibonacci(n+1). (End) - corrected Apr 06 2006 and Oct 05 2012

a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j). - Paul Barry, Aug 29 2004

a(n) = (Sum of (n+1)-th row of the triangle in A108617) / 2. - Reinhard Zumkeller, Jun 12 2005

a(n) = term (1,1) - term (2,2) in the 3 X 3 matrix [2,0,0; 0,1,1; 0,1,0]^n. - Alois P. Heinz, Jul 28 2008

a(n) = 2^n - A000045(n+1). - Geoffrey Critzer, Jan 04 2014

a(n) ~ 2^n. - Daniel Forgues, May 06 2015

From Bob Selcoe, Mar 29 2016: (Start)

a(n) = 2*a(n-1) + A000045(n-2).

a(n) = 4*a(n-2) + A000032(n-2). (End)

a(n) = 2^(n-1) - ( ((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5). - Haider Ali Abdel-Abbas, Aug 17 2019

Extensions

Simpler definition from Miklos Kristof, Nov 24 2003

Initial zero added by N. J. A. Sloane, Feb 13 2008

Definition fixed by Reinhard Zumkeller, Oct 07 2012