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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 17:30 EST 2017. Contains 295959 sequences.