A033538 a(0)=1, a(1)=1, a(n) = 3*a(n-1) + a(n-2) + 1.

1, 1, 5, 17, 57, 189, 625, 2065, 6821, 22529, 74409, 245757, 811681, 2680801, 8854085, 29243057, 96583257, 318992829, 1053561745, 3479678065, 11492595941, 37957465889, 125364993609, 414052446717, 1367522333761, 4516619448001, 14917380677765, 49268761481297

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*A006190(n+1) - 8*A006190(n) - 1)/3. (End)

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

Cf. A001595, A006190, A033539, A102426.

Sequence in context: A347750 A112044 A027030 * A027093 A027032 A027095

Adjacent sequences: A033535 A033536 A033537 * A033539 A033540 A033541

Keyword

nonn,nice,easy

Author

Antti Karttunen

Status

approved