A208742 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 5.

2, 4, 8, 16, 32, 48, 72, 108, 162, 243, 405, 675, 1125, 1875, 3125, 5000, 8000, 12800, 20480, 32768, 53248, 86528, 140608, 228488, 371293, 599781, 968877, 1565109, 2528253, 4084101, 6612354, 10705716, 17333064, 28063056, 45435424, 73498480, 118894600

Offset

1,1

References

M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1 k=5.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.

Index entries for linear recurrences with constant coefficients, signature (1, 1, 0, 0, -3, 3, 3, 0, 0, 6, -6, -6, 0, 0, 3, -3, -3, 0, 0, -1, 1, 1).

Formula

a(n) = F(floor(n/5) + 3)^(n mod 5)*F(floor(n/5) + 2)^(5 - (n mod 5)) where F(n) is the n-th Fibonacci number.

a(n) = a(n-1) + a(n-2) - 3*a(n-5) + 3*a(n-6) + 3*a(n-7) + 6*a(n-10) - 6*a(n-11) - 6*a(n-12) + 3*a(n-15) - 3*a(n-16) - 3*a(n-17) - a(n-20) + a(n-21) + a(n-22).

G.f.: -x*(x^21 +2*x^20 +x^19 +x^18 +x^17 -2*x^16 -6*x^15 -4*x^14 -3*x^13 -3*x^12 -9*x^11 -12*x^10 -3*x^9 -6*x^8 -6*x^7 -2*x^6 +6*x^5 +8*x^4 +4*x^3 +2*x^2 +2*x +2) / ((x^2 +x -1) * (x^10 -4*x^5 -1) * (x^10 +x^5 -1)). - Colin Barker, Jun 02 2013

Example

If n=6 then we must count all subsets not containing both 1 and 6.  There are 2^4 subsets containing 1 and 6, giving us 2^6 - 2^4 = 48.  Thus a(6) = 48.

Mathematica

Table[Fibonacci[Floor[n/5] + 3]^Mod[n, 5] * Fibonacci[Floor[n/5] + 2]^(5 - Mod[n, 5]), {n, 1, 40}]
LinearRecurrence[{1, 1, 0, 0, -3, 3, 3, 0, 0, 6, -6, -6, 0, 0, 3, -3, -3, 0, 0, -1, 1, 1}, {2, 4, 8, 16, 32, 48, 72, 108, 162, 243, 405, 675, 1125, 1875, 3125, 5000, 8000, 12800, 20480, 32768, 53248, 86528, 140608, 228488, 371293, 599781, 968877}, 80]

Prog

(PARI) a(n)=fibonacci(n\5+3)^(n%5)*fibonacci(n\5+2)^(5-n%5) \\ Charles R Greathouse IV, Mar 05 2012

Crossrefs

Cf. A006498, A006500, A208741, A208743.

Sequence in context: A316758 A316750 A008382 * A323395 A326079 A222193

Adjacent sequences: A208739 A208740 A208741 * A208743 A208744 A208745

Keyword

nonn,easy

Author

David Nacin, Mar 01 2012

Status

approved