In how many ways can you choose $k$ numbers out of $\{1,2,3,\dots,n\}$ so none of them is consecutive? I am a newbie in combinatorics and still don't have enough tools to handle this kind of problems.
Assuming I have a set of integers: $ \{1,2,3,4,\dots,n\} $
In how many ways, can I choose $k$ numbers out of those $n$, such that none of them are consecutive?
For instance, for the following set $ \{1,2,3,4,5\} $
For $ k=3 $ I have only 1 option: $\{1,3,5\}$
My purpose is first of all to understand the way you would think about this  problem, not necessarily the solution itself (I have the final answer for it).
Thanks.
 A: 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.

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

If we number the balls from left to right, we see that this particular selection corresponds to the subset $\{1, 3, 6, 9\}$.
A: 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}$.
A: Start with $k$ sticks (representing the numbers chosen) and $n-k$ dots (representing the other numbers), 
and remove $k-1$ dots (which will be our "blockers").
This leaves $k$ sticks and $n-2k+1$ dots, which can be arranged in $\color{blue}{\dbinom{n-k+1}{k}}$ ways;
and then we can insert the $k-1$ blockers between the sticks to make sure they are not consecutive.
