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)}.$

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*}

