A036605 a(n) = a(n-2) + 2*a(n-3) + a(n-4).

1, 4, 4, 7, 13, 19, 31, 52, 82, 133, 217, 349, 565, 916, 1480, 2395, 3877, 6271, 10147, 16420, 26566, 42985, 69553, 112537, 182089, 294628, 476716, 771343, 1248061, 2019403, 3267463, 5286868, 8554330, 13841197, 22395529, 36236725

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.4.2, Eq. (25).

Links

• Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Crossrefs

Cf. A004695.

Programs

Maple

A036605 := proc(n) option remember; if n <= 0 then 1 else A036605(n-2)+2*A036605(n-3)+A036605(n-4); fi; end;

Mathematica

LinearRecurrence[{0, 1, 2, 1}, {1, 4, 4, 7}, 36] (* Jean-François Alcover, Apr 01 2020 *)

Formula

3 * [Fibonacci(n+2)/2] + 1. - Ralf Stephan, Dec 02 2004

a(n) = (A099837(n+2)+A022086(n+2))/2. G.f. ( -1-4*x-3*x^2-x^3 ) / ( (1+x+x^2)*(x^2+x-1) ). - R. J. Mathar, Mar 21 2011