$k$-element subsets of $[n]$ that do not contain $2$ consecutive integers Let $k,n\in \mathbb{N}$ with $k\leq n$. Find the total number of $k$-element selections from $[n] = \{1, 2, \ldots, n\}$ that do not contain any 2 consecutive integers
 A: Hints:
It's the same as counting bitstrings of length $n$ containing exactly $k$ ones, no two of them consecutive,
which is the same as counting solutions of $x_0+x_1+\cdots+x_k=n-k$ in integers $x_j$ such that $x_0\ge0$, $x_k\ge0$, and $x_j\gt0$ for $0\lt j\lt k$,
which is the same as counting solutions of $y_0+y_1+\cdots+y_k=n+2-k$ in positive integers $y_j$,
which is the same as counting solutions of $z_0+z_1+\cdots+z_k=n+1-2k$ in nonnegative integers $z_j$.
Don't use inclusion-exclusion. It's a simple binomial coefficient.
A: Using generating functions and the binary string of length $n$ with $k$ ones model we need to select the size of the $k+1$ gaps between the ones, where the first and last one may be empty and the inner gaps must have size at least one. This gives
$$f(z) = \frac{1}{1-z}\times\frac{z}{1-z}\times\frac{z}{1-z}\times\cdots
\times\frac{z}{1-z}\times\frac{z}{1-z}\times\frac{1}{1-z}.$$
This simplifies to
$$f(z) = \frac{z^{k-1}}{(1-z)^{k+1}}.$$
Now the gaps must add up to $n-k$ so the answer is
$$[z^{n-k}] f(z)
= [z^{n-k}]  \frac{z^{k-1}}{(1-z)^{k+1}}
= [z^{n+1-2k}] \frac{1}{(1-z)^{k+1}}.$$
By Newton's binomial series this is
$$\binom{n+1-2k + k}{n+1-2k}
= \binom{n+1-k}{n+1-2k} = \binom{n+1-k}{k}.$$
A: Try looking at the Fibonacci Sequence! $F_{n+2}$ (where $F_n$ is Fibonacci) will also create this sequence.
