How many ways are there to select $k$ elements from the set $[n]$ such that the numbers selected differ by at least three?
I thought of considering two cases: $n-k$ is even or $n-k$ is odd. If $n-k$ is even, then I arrived at ${\frac{n-k}{2}+1}\choose{k}$ ways and if $n-k$ is odd, then there are ${\left\lfloor \frac{n-k}{2} \right\rfloor +1} \choose {k}$ possibilities. To answer this question, I was analysing the ways of choosing k elements from the empty spaces that exist when considering an array on $n-k$ $\textbf{0's}$. Any suggestions for a better argument and what's the answer for a more general case: the k selected numbers should differ by at least $d$ ?
Best Answer
I had mistakenly the difference as $2$ instead of $3$, amended
For a difference of $3$, after every chosen number (bullet) except the last , there must be at least two spacers (circles), $\boxed{\bullet\circ\circ}\circ\circ\circ\boxed{\bullet\circ\circ}\bullet$
From $n$ unnumbered tokens, take out $2(k-1),\;\; (n-2k+2)$ remain
Choose any $k$ from the above in $\binom{n-2k+2}{k}$ ways, mark them, but don't number them yet.
Insert from the taken out tokens, $2$ immediately after each of the chosen tokens (except the last), and now allot serial numbers
This generalises to $\dbinom{n-(d-1)(k-1)}{k}$
First Approach added back (simpler?)
Add $2$ elements [total now $(n+2)$] and form $k$ blocks of one chosen and two unchosen $\boxed{\bullet\circ\circ}$
There are now $(n+2-2k)$ entities $(k$ blocks plus $(n+2-3k)$ "singles")
Place the blocks in $\binom{n+2-2k}{k}$ ways and discard the last $2$ elements