login
A208742
Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 5.
4
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,2
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
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.: 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
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
KEYWORD
nonn,easy
AUTHOR
David Nacin, Mar 01 2012
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Sep 17 2024
STATUS
approved