In how many ways can you choose $k$ numbers out of $\{1,2,3,\dots,n\}$ so none of them is consecutive?

Place $n - k$ blue balls in a row, leaving gaps between them. We now have $n - k - 1$ spaces between successive blue balls and the two spaces at the ends of the row for a total of $n - k + 1$ spaces in which to place $k$ green balls. We choose $k$ of these $n - k + 1$ spaces for the green balls. We now number the balls from left to right. The numbers on the green balls are the desired set of non-consecutive integers. Hence, the number of ways of selecting $k$ integers from the set $\{1, 2, 3, \ldots, n\}$ so that no two of them are consecutive is $$\binom{n - k + 1}{k}$$

To illustrate the idea, let $n = 10$ and $k = 4$. We start with $n - k = 6$ blue balls.

$$\color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}$$

We choose four of the seven available spaces in which to place a green ball.

$$\color{green}{\bullet}\color{blue}{\bullet}\color{green}{\bullet} \color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{blue}{\bullet}$$

If we number the balls from left to right, we see that this particular selection corresponds to the subset $\{1, 3, 6, 9\}$.

Denote the # of ways to choose $k$ non-consecutive numbers from $\{1, 2, \cdots, n\}$ as $C_{n, k}$. There are two cases.

• $n$ is chosen. In this case, you have to choose $k - 1$ non-consecutive numbers from $\{1, 2, \cdots, n - 2\}$, i.e, $C_{n - 2, k - 1}$.

• $n$ is not chosen. In this case, you have to choose $k$ non-consecutive numbers from $\{1, 2, \cdots, n -1 \}$, i.e., $C_{n-1, k}$.

In other words, $C_{n, k} = C_{n-2,k-1} + C_{n-1,k}$.