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

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.
