OFFSET
0,3
COMMENTS
Number of times certain simple recursive programs (such as the Lisp program shown) call themselves on an input of length n.
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
REFERENCES
E. Hyvönen and J. Seppänen, LISP-kurssi, Osa 6 (Funktionaalinen ohjelmointi), Prosessori 4/1983, pp. 48-50 (in Finnish).
LINKS
T. D. Noe, Table of n, a(n) for n = 0..200
A. Karttunen, More information
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Index entries for linear recurrences with constant coefficients, signature (4,-2,-1).
FORMULA
From R. J. Mathar, Aug 22 2008: (Start)
O.g.f.: (1-3*x+3*x^2)/((1-x)*(1-3*x-x^2)).
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
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
MAPLE
a := proc(n) option remember; if(n < 2) then RETURN(1); else RETURN(3*a(n-1)+a(n-2)+1); fi; end;
MATHEMATICA
CoefficientList[ Series[(1-3x+3x^2)/(1-4x+2x^2+x^3), {x, 0, 40}], x](* Jean-François Alcover, Nov 30 2011 *)
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 *)
Table[(4*(Fibonacci[n, 3] +Fibonacci[n-1, 3]) -1)/3, {n, 0, 30}] (* G. C. Greubel, Oct 13 2019 *)
PROG
(Lisp) (defun rewerse (lista) (cond ((null (cdr lista)) lista) (t (cons (car (rewerse (cdr lista))) (rewerse (cons (car lista) (rewerse (cdr (rewerse (cdr lista))))))))))
(Haskell)
a033538 n = a033538_list !! n
a033538_list =
1 : 1 : (map (+ 1) $ zipWith (+) a033538_list
$ map (3 *) $ tail a033538_list)
-- Reinhard Zumkeller, Aug 14 2011
(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
(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
(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
(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
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved