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

Author

Antti Karttunen

Keywords

• nonn
• nice
• easy

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).

Crossrefs

Cf. A001595, A006190, A033539, A102426.

Programs

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

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

Lisp

(defun rewerse (lista) (cond ((null (cdr lista)) lista) (t (cons (car (rewerse (cdr lista))) (rewerse (cons (car lista) (rewerse (cdr (rewerse (cdr lista))))))))))

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

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 *)

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

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

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