Subsets of $\{1,2 \dots n\}$ with no consecutive integers How many subsets with cardinality k of $\{1, 2, \dots n\}$ contain no consecutive integers? I know that there are $F_{n+2}$ subsets of $\{1, 2, \dots n\}$ with no consecutive integers, but I do not know how to go about finding the number for a given $k$.
 A: This is equivalent to chooosing a sequence of $k$ ones and $n-k$ zeroes with no adjacent ones. An example with $n=8$ and $k=3$ is 
$$
00101001, \text{ corresponding to the set }\{3,5,8\}
$$
To choose such a sequence, start with a string of $n-k$ zeroes, with $n-k-1$ spaces between the zeroes, plus two extra spaces before and after, for $n-k+1$ spaces total:
$$
\;\_\; 0\;\_\;0\;\_\;0\;\_\;0\;\_\;0\;\_\qquad,\text{ with $8-3+1=6$ gaps}. 
$$
Each of the $k$ $1$'s goes into exactly one gap. We need to choose $k$ of these gaps to put a $1$ in. This can be done in
$$
\binom{n-k+1}{k}\text{ ways.}
$$
A: Without loss of generality, let your $k$ elements from a selected subset be $x_1<x_2<x_3<\dots<x_k$
Given such a $k$-tuple $(x_1,x_2,\dots,x_k)$, construct the related $(k+1)$-tuple $(x_1-1, x_2-x_1, x_3-x_2,\dots, x_k-x_{k-1}, n-x_k)$ describing the distance between each number and/or the boundaries in the case of the first and last numbers.
Renaming those values in the $(k+1)$-tuple $(y_1,y_2,\dots,y_{k+1})$ we can recognize that $y_1+y_2+\dots+y_{k+1} = n-1$ as the sum telescopes.
Now, consider the related problem of finding the number of integer solutions to the system:
$$\begin{cases}y_1+y_2+\dots+y_{k+1} = n-1\\ y_1\geq 0\\ y_{k+1}\geq 0\\ y_i\geq 2~~~\text{for all other }i\end{cases}$$
The inequalities here coming from that the elements may not be consecutive.  This should now be in a known problem format for you or can be slightly modified further with another change of variable to be in a known format and the problem can be completed using stars-and-bars.
A: We select the first value of the set:
$$\frac{z}{1-z}$$
followed by $k-1$ differences that are at least two:
$$\frac{z}{1-z} \left(\frac{z^2}{1-z}\right)^{k-1}$$
and we conclude by collecting the count for all subsets with maximum
element $\le n:$
$$[z^n] \frac{1}{1-z} \times \frac{z}{1-z}
\left(\frac{z^2}{1-z}\right)^{k-1}.$$
This is
$$[z^n] \frac{z^{2k-1}}{(1-z)^{k+1}}
= [z^{n+1-2k}] \frac{1}{(1-z)^{k+1}}
= {n+1-2k+k\choose k}$$
or equivalently
$$\bbox[5px,border:2px solid #00A000]{
{n+1-k\choose k}.}$$
We get for the total
$$\sum_{k=0}^{\lfloor (n+1)/2 \rfloor} {n+1-k\choose k}
= \sum_{k=0}^{\lfloor (n+1)/2 \rfloor} [z^{n+1-2k}] \frac{1}{(1-z)^{k+1}}
\\ = [z^{n+1}] \frac{1}{1-z}
\sum_{k=0}^{\lfloor (n+1)/2 \rfloor} z^{2k} \frac{1}{(1-z)^{k}}.$$
Here the coefficient extractor enforces the range and we may continue
with
$$[z^{n+1}] \frac{1}{1-z}
\sum_{k\ge 0} z^{2k} \frac{1}{(1-z)^{k}}
\\ = [z^{n+1}] \frac{1}{1-z} \frac{1}{1-z^2/(1-z)}
\\ = [z^{n+1}] \frac{1}{1-z-z^2}
= [z^{n+2}] \frac{z}{1-z-z^2} = F_{n+2}.$$
The above construction works for $k\ge 1.$ For $k=0$ we get the empty set, for a total count of one. Note however that ${n+1\choose 0} = 1$ so the formula holds there as well.
A: Hint: Choose $k$ pairs of consecutive numbers from $\{1, 2, \ldots, n, n+1\}$, then choose the lowest number in each pair.
