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

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, 1565109, 2528253, 4084101, 6612354, 10705716, 17333064, 28063056, 45435424, 73498480, 118894600

Offset: 0

Author

David Nacin, Mar 01 2012

Keywords

• nonn
• easy

Examples

			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.
		

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 = 0..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).

Crossrefs

Cf. A006498, A006500, A208741, A208743.

Programs

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]

PARI

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

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.: 1-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

Extensions

a(0)=1 prepended by Alois P. Heinz, Sep 17 2024