|
%I #48 Dec 16 2023 17:31:16
%S 1,1,5,17,57,189,625,2065,6821,22529,74409,245757,811681,2680801,
%T 8854085,29243057,96583257,318992829,1053561745,3479678065,
%U 11492595941,37957465889,125364993609,414052446717,1367522333761,4516619448001,14917380677765,49268761481297
%N a(0)=1, a(1)=1, a(n) = 3*a(n-1) + a(n-2) + 1.
%C Number of times certain simple recursive programs (such as the Lisp program shown) call themselves on an input of length n.
%C This is the sequence A(1,1;3,1;1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - _Wolfdieter Lang_, Oct 18 2010
%D E. Hyvönen and J. Seppänen, LISP-kurssi, Osa 6 (Funktionaalinen ohjelmointi), Prosessori 4/1983, pp. 48-50 (in Finnish).
%H T. D. Noe, <a href="/A033538/b033538.txt">Table of n, a(n) for n = 0..200</a>
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/software/stacks.lsp">More information</a>
%H Wolfdieter Lang, <a href="/A033538/a033538.pdf">Notes on certain inhomogeneous three term recurrences.</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-1).
%F From _R. J. Mathar_, Aug 22 2008: (Start)
%F O.g.f.: (1-3*x+3*x^2)/((1-x)*(1-3*x-x^2)).
%F a(n) = (4*A006190(n+1) - 8*A006190(n) - 1)/3. (End)
%F a(n) = 4*a(n-1) - 2*a(n-2) - a(n-3), a(0)=1=a(1), a(2)=5. Observed by G. Detlefs. See the W. Lang link. - _Wolfdieter Lang_, Oct 18 2010
%F a(n) = (4*(F(n,3) + F(n-1,3)) -1)/3, where F(n,x) is the Fibonacci polynomial (see A102426). - _G. C. Greubel_, Oct 13 2019
%p a := proc(n) option remember; if(n < 2) then RETURN(1); else RETURN(3*a(n-1)+a(n-2)+1); fi; end;
%t CoefficientList[ Series[(1-3x+3x^2)/(1-4x+2x^2+x^3), {x,0,40}], x](* _Jean-François Alcover_, Nov 30 2011 *)
%t RecurrenceTable[{a[0]==a[1]==1,a[n]==3a[n-1]+a[n-2]+1},a,{n,40}] (* or *) LinearRecurrence[{4,-2,-1},{1,1,5},41] (* _Harvey P. Dale_, Jan 05 2012 *)
%t Table[(4*(Fibonacci[n,3] +Fibonacci[n-1,3]) -1)/3, {n,0,30}] (* _G. C. Greubel_, Oct 13 2019 *)
%o (Lisp) (defun rewerse (lista) (cond ((null (cdr lista)) lista) (t (cons (car (rewerse (cdr lista))) (rewerse (cons (car lista) (rewerse (cdr (rewerse (cdr lista))))))))))
%o (Haskell)
%o a033538 n = a033538_list !! n
%o a033538_list =
%o 1 : 1 : (map (+ 1) $ zipWith (+) a033538_list
%o $ map (3 *) $ tail a033538_list)
%o -- _Reinhard Zumkeller_, Aug 14 2011
%o (PARI) a(n)=([0,1,0; 0,0,1; -1,-2,4]^n*[1;1;5])[1,1] \\ _Charles R Greathouse IV_, Feb 19 2017
%o (Magma) I:=[1,1]; [n le 2 select I[n] else 3*Self(n-1) +Self(n-2) +1: n in [1..40]]; // _G. C. Greubel_, Jul 10 2019
%o (Sage) ((1-3*x+3*x^2)/((1-x)*(1-3*x-x^2))).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, Jul 10 2019
%o (GAP) a:=[1,1];; for n in [3..40] do a[n]:=3*a[n-1]+a[n-2] +1; od; a; # _G. C. Greubel_, Jul 10 2019
%Y Cf. A001595, A006190, A033539, A102426.
%K nonn,nice,easy
%O 0,3
%A _Antti Karttunen_
|
