Question

Find the number of subsets of the set of n consecutive positive integers, {1,2,...,n} that do not contain two elements whose difference is k, where k≤n−1

This problem has been asked before and it is now closed. I will write in the comment a formula for it.

Answer 1

Let f(k,n) be the number of subsets of {1,2,...,n}
that do not contain two integers whose difference is k.

Define the Fibonacci sequence by F(0)=F(1)=1 and
F(N)=F(N-2)+F(N-1) for N=2,3,4,...

The formula I get for f(k,n) is as follows.

Using the division algorithm there are unique integers q,r
such that n=kq+r and 0 <= r < k. Note that q=[n/k]
(the greatest integer not exceeding n/k) and r=n - k*[n/k];
that is, both q and r are functions of n and k.

Then

f(k,n) = F(q+3)^r * F(q+2)^(k-r)

One can work out a closed form for this expression using
the closed form for Fibonacci numbers.

Answer 2

In the case k=1, q=1, r=0 so
f(1,n)= F(n+2)^2 as found by @ganeshie8

Answer 3

The initial problem that was asked, k=2, n=20
so q=10, r=0
f(2,20)=F(12)^2

Answer 4

@SithsAndGiggles @sidsiddhartha @Miracrown
@ikram002p

Answer 5

The original problem was posted by @SithsAndGiggles

Answer 6

Nice :) this looks more general as it avoids the dependency \(k|n\) XD

Answer 7

yes thank you prof. :)

Answer 8

YW @sidsiddhartha

Answer 9

;)