subsets where consecutive difference is never $2$

Show that the number of subsets of $$\{1,\cdots, n\}$$ with size $$k$$ and where the difference between consecutive pairs of elements is never equal to $$2$$ is $$\sum_{j=0}^{k-1} {k-1\choose j}{n-k-j+1\choose n-2j-k}.$$

I got that the desired number is equal to $$\sum_{j=0}^{k-1} {k-1\choose j} \sum_{i=j}^{2j} {j\choose i- j}(-1)^i {n-k-i+k\choose n-k-i}$$ as follows, but this may be incorrect. Let $$C_k$$ be the set of ordered pairs $$(A, n)$$ so that $$A$$ is a $$k$$-subset of $$\{1,\cdots, n\}$$ where the difference between consecutive pairs of elements is never equal to $$2$$. Then each difference vector (e.g. the difference vector corresponding to the pair $$(\{a_1,\cdots, a_k\},n)$$ would be $$(a_1,a_2-a_1,\cdots, a_k-a_{k-1}, n-a_k)$$) would have a first element that's a positive integer, a nonnegative integer as the last argument, and $$k-1$$ differences in between, none of which are $$2$$. This gives the generating series $$\dfrac{x}{1-x}\cdot (x+\frac{x^3}{1-x})^{k-1} (\frac{1}{1-x}) = x^k (1-x+x^2)^{k-1} (1-x)^{-(k+1)}.$$ The coefficient of $$x^n,$$ denoted $$[x^n]x^k (1-x+x^2)^{k-1} (1-x)^{-(k+1)},$$ is thus \begin{align} [x^{n-k}] (1-x+x^2)^{k-1} (1-x)^{-(k+1)} &= \sum_{i\geq 0} \big([x^i] (1-x+x^2)^{k-1}\big) \big([x^{n-k-i}](1-x)^{-(k+1)}\big)\\ &= \sum_{i\geq 0} \left([x^i] \sum_{j=0}^{k-1} {k-1\choose j}(x^2-x)^j \right) {n-i\choose k}\\ &= \sum_{i\geq 0} \left([x^i]\sum_{j=0}^{k-1} {k-1\choose j}(-x)^j \sum_{m=0}^j {j\choose m} (-x)^m\right)\binom{n-i}k\\ &= \sum_{i\geq 0} \left([x^i] \sum_{j=0}^{k-1} \sum_{m=0}^{k-1} {k-1\choose j}{j\choose m} (-1)^{j+m} x^{j+m}\right){n-i\choose k}\\ &=\sum_{i\geq 0} \left(\sum_{j=0}^{k-1} {k-1\choose j}{j\choose i-j}\right)(-1)^i {n-i\choose k}\\ &= \sum_{j=0}^{k-1} {k-1\choose j}\sum_{i=j}^{2j} {j\choose i-j} (-1)^i {n-i\choose k}, \end{align} but apparently $$\sum_{i=j}^{2j} {j\choose i-j} (-1)^i {n-i\choose k} \neq {n-k-j+1\choose n-2j-k},$$ and despite checking this over many times, I am unable to figure out what went wrong. I used the binomial theorem and summation properties. Another possibility, though possibly even messier, would be to split the generating series up as $$(1-\frac{x^2}{1-x})^k\cdot \dfrac{1}{(1-x-x^2)(1-x)}.$$

I’ve not yet worked through the generating function argument, but I can prove the desired result directly.

If $$\{a_1,\ldots,a_k\}$$ is a $$k$$-element subset of $$[n]$$ such that $$a_1<\ldots, and $$a_{i+1}-a_i\ne 2$$ for $$i=1,\ldots,k-1$$, say that there is a gap at $$i$$ if $$a_{i+1}-a_i>1$$. Let $$A(n,k)$$ be the set of $$\{a_1,\ldots,a_k\}\subseteq[n]$$ such that if $$a_1<\ldots, then $$a_{i+1}-a_i\ne 2$$ for $$i=1,\ldots,k-1$$. For $$j=0,\ldots,k-1$$ let $$A(n,k,j)$$ be the set of members of $$A(n,k)$$ having exactly $$j$$ gaps. I claim that

$$|A(n,k,j)|=\binom{k-1}j\binom{n-k-j+1}{j+1}\,.$$

Suppose that $$S=\{a_1,\ldots,a_k\}\in A(n,k,j)$$. Let $$J$$ be the set of indices at which $$S$$ has a gap. If $$a_i,\ldots,a_j$$ is a maximal string of consecutive integers, imagine gluing it together to form a single object, and if $$j\in J$$, include $$a_j+1$$ and $$a_j+2$$ as well; every member of $$J$$ will be accounted for in this way, and there will be one more object containing $$a_k$$. Each remaining member of $$[n]$$ is treated as a single object. We now have $$j+1$$ objects containing members of $$S$$ and $$n-k-2j$$ singleton objects, for a total of $$n-k-j+1$$ distinct objects. Any $$j+1$$ of them can be the objects that contain members of $$S$$, so there are $$\binom{n-k-j+1}{j+1}$$ members of $$A(n,k,j)$$ having gaps at the indices in $$J$$.

Example: Let $$n=10$$, $$k=4$$, and $$j=2$$; the members of $$A(10,4,2)$$ having gaps at $$i=1$$ and $$i=2$$ are \begin{align*}&\{1,4,7,8\}, \{1,4,8,9\},\{1,4,9,10\},\{2,5,8,9\}\\&\{2,5,9,10\},\{2,6,9,10\},\{1,5,8,9\},\{1,5,9,10\}\\&\{1,6,9,10\},\text{ and }\{2,6,9,10\}\,.\end{align*} For $$\{2,6,9,10\}$$ the $$5$$ objects are $$\{1\},\{2,3,4\},\{5\},\{6,7,9\}$$, and $$\{9,10\}$$. For $$\{2,3,6,10\}$$, with gaps at $$2$$ and $$3$$, the $$5$$ objects are $$\{1\},\{2,3,4,5\}$$, $$\{6,7,8\}$$, $$\{9\}$$, and $$\{10\}$$.

There are $$\binom{k-1}j$$ possible choices for the set $$J$$ of indices at which $$S$$ has a gap, so altogether

\begin{align*} |A(n,k,j)|&=\binom{k-1}j\binom{n-k-j+1}{j+1}\\ &=\binom{k-1}j\binom{n-k-j+1}{n-2j-k}\,, \end{align*}

and the result follows by summing over the possible values of $$j$$.

• This may sound stupid, but I can't get $6$ objects when $n=12, k=5, j=2$ for the subset $\{4,5,6,9,12\}.$ I think one of the objects should be $\{12\}$, and the rest should be $\{9,10,11\}, \{6,7,8\}, \{4,5\}, \{1\}, \{2\},\{3\}.$ What am I doing wrong? Aug 26 '20 at 15:00
• @FredJefferson: That’s my fault for not explaining it more clearly: a string of consecutive members of $S$ that ends in a gap should be taken with the gap, so that here the pieces are $\{1\}$, $\{2\}$, $\{3\}$, $\{4,5,6,7,8\}$, $\{9,10,11\}$, and $\{12\}$. I’ll try to rewrite it to make that clearer. Aug 26 '20 at 15:57