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)}.$
 A: 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<a_k$, 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<a_k$, 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$.
A: The generating function approach is sound. We show the following is valid for $M:=\min\{k-1,\lfloor(n-k)/2\rfloor\}$.
\begin{align*}
\color{blue}{[x^{n-k}]\frac{\left(1-x+x^2\right)^{k-1}}{(1-x)^{k+1}}=\sum_{j=0}^{M}\binom{k-1}{j}\binom{n-k-j+1}{n-2j-k}}\tag{1}
\end{align*}
In (1) we use the upper limit $M$ to assure that the lower index of $\binom{n-k-j+1}{n-2j-k}$ is non-negative.

We obtain
\begin{align*}
\color{blue}{[x^{n-k}]}&\color{blue}{\frac{\left((1-x)+x^2\right)^{k-1}}{(1-x)^{k+1}}}\\
&=[x^{n-k}]\sum_{j=0}^{k-1}\binom{k-1}{j}x^{2j}(1-x)^{-j-2}\tag{2.1}\\
&=\sum_{j=0}^{M}\binom{k-1}{j}[x^{n-k-2j}](1-x)^{-j-2}\tag{2.2}\\
&=\sum_{j=0}^{M}\binom{k-1}{j}\binom{-j-2}{n-k-2j}(-1)^{n-k-2j}\tag{2.3}\\
&\,\,\color{blue}{=\sum_{j=0}^M\binom{k-1}{j}\binom{n-k-j+1}{n-k-2j}}\tag{2.4}
\end{align*}
and the claim (1) follows.

Comment:

*

*In (2.1) we apply the binomial theorem multiplying with the denominator $(1-x)^{-k-1}$.


*In (2.2) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and set the upper limit to $M$ to assure the power $n-k-2j$ of $x$ is non-negative.


*In (2.3) we select the coefficient of $x^{n-k-2j}$.


*In (2.4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
Note: We can derive a very similar binomial identity by using $1-x+x^2=(1-x)^2+x$.

We derive:
\begin{align*}
\color{blue}{[x^{n-k}]}&\color{blue}{\frac{\left((1-x)^2+x\right)^{k-1}}{(1-x)^{k+1}}}\\
&=[x^{n-k}]\sum_{j}\binom{k-1}{j}x^{j}(1-x)^{k-3-2j}\\
&=\sum_{j}\binom{k-1}{j}[x^{n-k-j}](1-x)^{k-3-2j}\\
&=\sum_{j}\binom{k-1}{j}\binom{k-3-2j}{n-k-j}(-1)^{n-k-j}\\
&=\sum_{j}\binom{k-1}{j}\binom{n-2k+j+2}{n-k-j}\tag{3.1}\\
&=\sum_{j}\binom{k-1}{j}\binom{n-k-j+1}{n-2k+j+1}\tag{3.2}\\
&\,\,\color{blue}{=\sum_{j}\binom{k-1}{j}\binom{n-k-j+1}{k-2j}}\tag{3.3}
\end{align*}

Comment:

*

*In (3.1) we use $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.


*In (3.2) we change the order of summation $j\to k-1-j$.


*In (3.3) we use $\binom{p}{q}=\binom{p}{p-q}$.

From (2.4) and (3.3) we find the nice binomial identity
\begin{align*}
\color{blue}{\sum_{j}\binom{k-1}{j}\binom{n-k-j+1}{n-k-2j}=\sum_{j}\binom{k-1}{j}\binom{n-k-j+1}{k-2j}}
\end{align*}

