A093960 a(1) = 1, a(2) = 2, a(n+1) = n*a(1) + (n-1)*a(2) + ... + (n-r)*a(r+1) + ... + a(n).

1, 2, 4, 11, 29, 76, 199, 521, 1364, 3571, 9349, 24476, 64079, 167761, 439204, 1149851, 3010349, 7881196, 20633239, 54018521, 141422324, 370248451, 969323029, 2537720636, 6643838879, 17393796001, 45537549124, 119218851371, 312119004989, 817138163596

Offset: 1

Author

Amarnath Murthy, May 22 2004

Keywords

• nonn
• easy

Comments

a(1) = a(2) = 1 gives A088305, i.e., Fibonacci numbers with even indices. This can be called 'fake Fibonacci sequence'. 4 = 3+1, 11 = 8+3, 29 = 21+8, 76 = 55+21, etc. a(n) = F(2n-2) + F(2n-4).

Except for the initial terms, this is the same as the bisection of the Lucas sequence (A002878). - Franklin T. Adams-Watters, Jul 17 2006

Links

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

Crossrefs

Cf. A000045, A002878, A088305.

Programs

Magma

[1,2] cat [Lucas(2*n-3): n in [3..30]]; // G. C. Greubel, Dec 30 2021

Maple

a[1]:=1: a[2]:=2: for n from 2 to 33 do a[n+1]:=sum((n-r)*a[r+1],r=0..n-1) od: seq(a[n],n=1..33); # Emeric Deutsch, Aug 01 2005
A093960List := proc(m) local A, P, n; A := [1,2]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-1]]);
A := [op(A), P[-1]] od; A end: A093960List(30); # Peter Luschny, Mar 24 2022

Mathematica

Print[1]; Print[2]; Do[Print[Fibonacci[2*n - 2] + Fibonacci[2*n - 4]], {n, 3, 20}] (* Ryan Propper, Jun 19 2005 *)
LinearRecurrence[{3,-1},{1,2,4,11},30] (* Harvey P. Dale, Nov 17 2018 *)

PARI

Vec(x*(x-1)^2*(x+1)/(x^2-3*x+1) + O(x^100)) \\ Colin Barker, Mar 26 2015

Sage

[2^(2-n)*bool(n<3) + lucas_number2(2*n-3, 1, -1) for n in (1..30)] # G. C. Greubel, Dec 30 2021

Formula

a(n) = F(2*n-2) + F(2*n-4), where F(k) is k-th Fibonacci number, n > 2.

a(n) = 3*a(n-1) - a(n-2) for n>4. - Colin Barker, Mar 26 2015

G.f.: x*(1-x)^2*(1+x) / (1-3*x+x^2). - Colin Barker, Mar 26 2015

a(n) = 2^(2-n)*[n<3] + LucasL(2*n-3). - G. C. Greubel, Dec 30 2021

Extensions

More terms from Ryan Propper, Jun 19 2005

More terms from Emeric Deutsch, Aug 01 2005