A295687 a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 2, a(3) = 1.

1, 2, 2, 1, 4, 8, 11, 16, 28, 47, 74, 118, 193, 314, 506, 817, 1324, 2144, 3467, 5608, 9076, 14687, 23762, 38446, 62209, 100658, 162866, 263521, 426388, 689912, 1116299, 1806208, 2922508, 4728719, 7651226, 12379942, 20031169, 32411114, 52442282, 84853393

Offset: 0

Author

Clark Kimberling, Nov 29 2017

Keywords

• nonn
• easy

Comments

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Links

• Clark Kimberling, Table of n, a(n) for n = 0..2000
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Crossrefs

Cf. A000045, A001622, A001654, A002878, A005248, A192883, A295690.

Programs

Mathematica

LinearRecurrence[{1, 0, 1, 1}, {1, 2, 2, 1}, 100]

Formula

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 2, a(3) = 1.

G.f.: (-1 - x + 2*x^3)/(-1 + x + x^3 + x^4).

From Peter Bala, Nov 27 2021: (Start)

a(2*n) = 3*a(2*n-2) - a(2*n-4) - (-1)^n, for n >= 2;

a(2*n+1) = 3*a(2*n-1) - a(2*n-3) + 7*(-1)^n, for n >= 2.

a(2*n) = Lucas(2*n-1) - Fibonacci(n-3)*Fibonacci(n-2) = A002878(n-1) - A001654(n-3);

a(2*n+1) = Lucas(2*n) - Fibonacci(n-4)*Fibonacci(n) = A005248(n) - A192883(n-3).

a(4*n-1) = Fibonacci(2*n+1)^2 - Fibonacci(2*n)^2 + Fibonacci(2*n-1)^2 - Fibonacci(2*n-2)^2 - 3, for n >= 1;

a(4*n+1) = Fibonacci(2*n+2)^2 - Fibonacci(2*n+1)^2 + Fibonacci(2*n)^2 - Fibonacci(2*n-1)^2 + 3, for n >= 0.

Conjecture: a(2*n+7) = Fibonacci(n)^3*Sum_{k >= 1} k^2 * Fibonacci(n*k)/ Fibonacci(n+2)^(k+1), n >= 1. (End)