A003476 a(n) = a(n-1) + 2*a(n-3).

1, 2, 3, 5, 9, 15, 25, 43, 73, 123, 209, 355, 601, 1019, 1729, 2931, 4969, 8427, 14289, 24227, 41081, 69659, 118113, 200275, 339593, 575819, 976369, 1655555, 2807193, 4759931, 8071041, 13685427, 23205289, 39347371, 66718225, 113128803, 191823545, 325259995

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• D. E. Daykin and S. J. Tucker, Introduction to Dragon Curves. Unpublished, 1976. See links in A003229 for an earlier version.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..500
• D. E. Daykin, Letter to N. J. A. Sloane, Mar 1974.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
• Kevin Ryde, Iterations of the Dragon Curve, see index "RQ", "BQ", and "S".
• Index entries for linear recurrences with constant coefficients, signature (1,0,2).

Crossrefs

Cf. A003229, A052537, A078044.

Programs

Maple

A003476:=-(1+z+z**2)/(-1+z+2*z**3); # Simon Plouffe in his 1992 dissertation

Mathematica

LinearRecurrence[{1,0,2},{1,2,3},30] (* Harvey P. Dale, Jun 01 2020 *)

PARI

my(P=Mod('x,'x^3-'x^2-2)); a(n) = subst(lift(P^n),'x,2) >> 1; \\ Kevin Ryde, Oct 16 2021

Formula

a(n) = A003229(n-1) + A052537(n-2).

a(n) = (1/4)*abs(A078044(n+2)).