login
a(2n) = a(2n-1)+a(2n-2), a(2n+1) = a(2n)+a(2n-1)-1, a(0)=2, a(1)=1.
2

%I #42 Sep 08 2022 08:45:00

%S 2,1,3,3,6,8,14,21,35,55,90,144,234,377,611,987,1598,2584,4182,6765,

%T 10947,17711,28658,46368,75026,121393,196419,317811,514230,832040,

%U 1346270,2178309,3524579,5702887,9227466,14930352,24157818,39088169,63245987,102334155,165580142,267914296,433494438

%N a(2n) = a(2n-1)+a(2n-2), a(2n+1) = a(2n)+a(2n-1)-1, a(0)=2, a(1)=1.

%H Vincenzo Librandi, <a href="/A052959/b052959.txt">Table of n, a(n) for n = 0..1000</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1030">Encyclopedia of Combinatorial Structures 1030</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,-1).

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

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

%F a(n) = Sum_{alpha=RootOf(-1+z+z^2)} (1/5)*(1 + 2*alpha)*alpha^(-1-n) + Sum_{beta=RootOf(-1+z^2)} beta^(-n)/2.

%F a(n) = Fibonacci(n+1) + (1+(-1)^n)/2 = A000045(n+1) + A059841(n). - _Vladeta Jovovic_, Apr 23 2003

%F a(n) = Sum_{k=0..n} ( C(k, n-k) + (-1)^(n-k) ). - _Paul Barry_, Jul 21 2003

%p spec:= [S,{S=Union(Sequence(Union(Prod(Z,Z),Z)), Sequence(Prod(Z,Z)))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);

%p seq(coeff(series((2-x-2*x^2)/((1-x^2)*(1-x-x^2)), x, n+1), x, n), n = 0..50); # _G. C. Greubel_, Oct 22 2019

%t LinearRecurrence[{1,2,-1,-1},{2,1,3,3},50] (* _Harvey P. Dale_, Apr 01 2014 *)

%t CoefficientList[Series[(2-x-2*x^2)/((1-x^2)*(1-x-x^2)), {x, 0, 50}], x] (* _Vincenzo Librandi_, Apr 07 2014 *)

%t Sum[Fibonacci[Range[50], k], {k,0,1}] (* _G. C. Greubel_, Oct 22 2019 *)

%o (PARI) my(x='x+O('x^50)); Vec((2-x-2*x^2)/((1-x^2)*(1-x-x^2))) \\ _G. C. Greubel_, Oct 22 2019

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 50); Coefficients(R!( (2-x-2*x^2)/((1-x^2)*(1-x-x^2)) )); // _G. C. Greubel_, Oct 22 2019

%o (Sage)

%o def A052959_list(prec):

%o P.<x> = PowerSeriesRing(ZZ, prec)

%o return P((2-x-2*x^2)/((1-x^2)*(1-x-x^2))).list()

%o A052959_list(50) # _G. C. Greubel_, Oct 22 2019

%o (GAP) a:=[2,1,3,3];; for n in [5..50] do a[n]:=a[n-1]+2*a[n-2]-a[n-3] -a[n-4]; od; a; # _G. C. Greubel_, Oct 22 2019

%K easy,nonn

%O 0,1

%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000

%E More terms from _James A. Sellers_, Jun 05 2000