A291916 Number of (not necessarily maximal) cliques in the n-Fibonacci cube graph.

4, 6, 11, 19, 34, 60, 106, 186, 325, 565, 978, 1686, 2896, 4958, 8463, 14407, 24466, 41456, 70102, 118322, 199369, 335401, 563426, 945194, 1583644, 2650230, 4430291, 7398331, 12342850, 20573220, 34262338, 57013866, 94800781, 157517533, 261545778, 433993662

Offset: 1

Author

Eric W. Weisstein, Sep 05 2017

Keywords

• nonn

Links

• Eric Weisstein's World of Mathematics, Clique
• Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Crossrefs

Cf. A022137, A001629 (maximum and maximal cliques).

Programs

Mathematica

LinearRecurrence[{3, -1, -3, 1, 1}, {4, 6, 11, 19, 34}, 20]
Table[((25 - 19 Sqrt[5]) (1 - Sqrt[5])^n + (1 + Sqrt[5])^n (25 + 19 Sqrt[5]))/(25 2^(n + 1)) + n LucasL[n + 1]/5 + 1, {n, 20}] // Expand
CoefficientList[Series[(-4 + 6 x + 3 x^2 - 4 x^3 - 2 x^4)/((-1 + x) (-1 + x + x^2)^2), {x, 0, 20}], x]
Table[(n LucasL[n + 1] + LucasL[n + 4] - Fibonacci[n - 3])/5 + 1, {n, 40}] (* Eric W. Weisstein, Nov 29 2017 *)

Formula

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

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

a(n) = (n*Lucas(n + 1) + Lucas(n + 4) - Fibonacci(n - 3))/5 + 1. - Ehren Metcalfe, Oct 16 2017