login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033538 a(0)=1, a(1)=1, a(n)=3*a(n-1)+a(n-2)+1. 4
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 (list; graph; refs; listen; history; text; internal format)
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. [From 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

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. - R. J. Mathar, Aug 22 2008

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. [From Wolfdieter Lang, Oct 18 2010]

a(n) = -1/3+2/39*(3/2-1/2*sqrt(13))^n*sqrt(13)-2/39*sqrt(13)*(3/2+1/2*sqrt(13))^n+2/3 *(3/2-1/2*sqrt(13))^n+2/3*(3/2+1/2*sqrt(13))^n, with n>=0 [From Paolo P. Lava, Sep 01 2008]

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, 25}], 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, 30}] (* or *) LinearRecurrence[{4, -2, -1}, {1, 1, 5}, 31] (* Harvey P. Dale, Jan 05 2012 *)

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

CROSSREFS

Cf. A033539, A001595.

Sequence in context: A145371 A112044 A027030 * A027093 A027032 A027095

Adjacent sequences:  A033535 A033536 A033537 * A033539 A033540 A033541

KEYWORD

nonn,nice,easy

AUTHOR

Antti Karttunen

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 12 09:07 EST 2018. Contains 318053 sequences. (Running on oeis4.)