If $N$ is a natural number, then how many subsets of $\{1,2,\dots,N\}$ are there of size $k$ such that it does not contain consecutive integers?
Take $N = 6$ and $k = 3$. Then, for the set $\{ 1, 2, 3, 4, 5, 6 \}$, there are $4$ subsets possible, i.e., $$\{1, 3, 5\}, \; \{1, 3, 6\}, \; \{1, 4, 6\} \quad \text{and} \quad \{2, 4, 6\}.$$
Best Answer
Think in terms of characteristic functions.
If $A\subset B$, then the characteristic function of $A$ is the function $\chi_A:B\to\{0,1\}$ such that for any given $b\in B$ we have $\chi_A(b)=1$ if $b\in A$ and $\chi_X(b)=0$ if $b\notin A$.
For example, if we have $A=\{1,3,6\}$ and $B=\{1,2,3,4,5,6\}$, then the characteristic function is given as:
\begin{array}{r|llllll} b&1&2&3&4&5&6\\ \chi_A(b)&1&0&1&0&0&1 \end{array}
In other words, if we have some natural number $N$, then each subset of $\{1,2,\dots,N\}$ can be represented as some binary string of length $N$. Those subsets with consecutive numbers are represented by those strings with consecutive $1$'s.
If a subset $A\subset\{1,\dots,N\}$ has size $k$, then it is represented by a string with exactly a $k$ number of $1$'s. Each of these $1$'s has to be separated by at least one $0$, since we do not allow consecutive numbers. Note that therefore the total number of subsets of size $k$ for $N<2k-1$, must be $0$, since the representative string would be longer than $N$.
Finally, given $k$, how many subsets without consecutive numbers exist with $N=2k-1$? Well, there could be only a single one. This is because in the representative string all of the $1$'s, except for the last one, have to be followed by a $0$. For example, if $k=3$, then there is only one subset of $\{1,2,3,4,5\}$ with three nonconsecutive elements, given by the string $10101$, i.e. the subset $\{1,3,5\}$.
Now, given $k$ and $N>2k-1$, how many subsets of $\{1,2,\dots, N\}$ without consecutive numbers do there exist? Such subsets are given by strings that have a $k$ number of $1$'s, and an $N-k$ number of $0$'s. Of these $0$'s, we know that there are $k-1$ of them that follow the first $k-1$ number of $1$'s in the string, i.e., each string for $k=3$ looks as follows, where the $\cdot$'s represent the places where the other $0$'s could occur:
$$ \cdot 10\cdot10\cdot1\cdot $$
So the question becomes, in how many ways could we distribute the remaining $N-k - (k-1)=N-2k+1$ number of $0$'s in the $k+1$ positions, given by the dots?
This is effectively the problem of the number of ways to put $N-2k+1$ indentical balls in $k+1$ labelled boxes, also known as the Stars & Bars problem.