Derive the number of subsets of size $k$ such that it does not contain any consecutive numbers 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\}.$$
 A: 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. 
A: Note all valid subsets one-to-one correspond to all permutations of $N-k$ unlabelled white balls and $k$ unlabelled black balls where no two black balls are adjacent. Also, each such permutation can be obtained by inserting the $k$ black balls into the gaps between two white balls (including the leftmost and the rightmost positions) such that no two black balls are inserted into the same gap. There are $N-k+1$ gaps, so there are $\binom{N-k+1}{k}$ ways to insert black balls. The answer to your question is also $\binom{N-k+1}{k}$.
