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

 

Logo


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, 14917380677765, 49268761481297 (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. - 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) = -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. - Paolo P. Lava, Sep 01 2008

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: A145371 A112044 A027030 * A027093 A027032 A027095

Adjacent sequences:  A033535 A033536 A033537 * A033539 A033540 A033541

KEYWORD

nonn,nice,easy,changed

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 October 22 14:44 EDT 2019. Contains 328318 sequences. (Running on oeis4.)