choosing $3$ numbers from a set of $n$ numbers so no consecutive numbers are selected Let $A  = \{1,2,3, \ldots , n\}$
and the question is: in how many ways can you pick $3$ numbers from $A$, so there won't be any consecutive numbers.
I was thinking of a recursive solution:
$A_k =$ number of ways of picking $k$ numbers without consecutive numbers.
$a_3 =$ if $1$ is chosen then any legal pick of size $a_{k-2}$ is ok.
$a_3 =$ if $n$ is chosen, same case.
$a_3 =$ if $2$ till $n-2$ is chosen then any legal pick of size $a_{k-3}$ is ok

However, I am not sure if I could actually come up with an actual solution while dealing with two variables. 
Could someone please suggest a good approach to this?
Thanks.
 A: Look at the set of $n$ integers.
Either you take $1$ or you do not. If you take $1$, then you can't take $2$, so you have to pick $2$ numbers out of $n-2$ numbers which are not consecutive.
If you don't pick $1$, then you get the same situation for $n-1$ numbers.
Hence, $a_n = a_{n-1} + m_{n-2}$, where $m_{n-2}$ is the number of ways of picking two non-consecutive numbers from a list of $n-2$ numbers. Let's study $m$. 
Consider $n-2$ numbers. If you pick $1$, you can pick all except $2$, so that gives $(n-4)$ ways. Similarly,  if you pick $2$, you can pick all except $1$ and $3$. Thus, every number except $1$ and $n-2$ admits $n-5$ valid choices, while $1$ and $(n-2)$ themselves admit $(n-4)$ valid choices. Hence $m_{n-2} = 2(n-4) + (n-4)(n-5) = (n-4)(n-3)$. However, every choice comes twice, because it's possible that we first choose $1$ then $3$, while the next time we choose $3$ and $1$, which amount to the same choice but are counted differently here. So we have to divide by $2$.
That gives $a_n = a_{n-1}+ \frac{1}{2}(n-4)(n-3)$. Now, we can perform the addition: $a_n = \frac{1}{2}\sum_4^n n^2-7n+12 = \dfrac{n^3-9n^2+26n-24}{6}  = \dfrac{(n-2)(n-3)(n-4)}{6}$
As an example, let us consider $5$:
$$
a_5=\frac{3*2*1}{6} = 1
$$ 
Similarly,
$$
a_6=\frac{4*3*2}{6} = 4
$$
which is true, because $1,3,5$, $1,3,6$, $1,4,6$ and $2,4,6$ are the only satisfactory triples.
A: Here is an approach that yields an explicit formula:
Place $n - 3$ blue balls in a row, leaving spaces between them and at the ends of the row.  There are $n - 2$ such spaces, $n - 4$ spaces between successive blue balls and two at the ends of the row.  Choose three of these $n - 2$ spaces in which to place the three green balls.  Now, number the balls from $1$ to $n$ from left to right.  The numbers on the green balls are the desired subset of three numbers of set $A$ in which no two elements of the subset are consecutive.  The number of ways of choosing the subset is equal to the number of ways of placing the three green balls in the $n - 2$ spaces, which is $$\binom{n - 2}{3}$$ 
A: Make this question in some parts:

1.We first choose $1$:Then we cannot choose either $2$then it's answer will be $f_{n-2}$
2.For any other numbers that we choose first except $n$ you can't either take other two that are next to it that this kinds will give us the answer $n-2(f_{n-3})$
3.And for $n$ the answer will be $f_{n-2}$

Then the totall answer will be:
$f_n=2f_{n-2}+(n-2)f_{n-3}$
Hint for solving upper equation:Because $n=0$ and $n=1$ is impossible you should try $n=5$ and $n=6$.
A: Suppose the three numbers chosen, in order, are $a$, $b$ and $c$.  We then have $1 \le a < b < c \le n$.  However, since we know the numbers are not consecutive, we in fact have some stronger inequalities: $a + 2 \le b$, and $b + 2 \le c$.
However, having the $+2$ makes things a little inconvenient.  One way to get rid of them is to change variables slightly: make the larger ones a bit smaller.
Full solution:

 Let $b' = b-1$ and $c' = c-2$.  Then we have $b' = b - 1 \ge (a+2) - 1 = a+1$, or simply $b' > a$.  Similarly, $c' = c - 2 \ge (b + 2) - 2 = b = b' + 1$, or $c' > b'$.  We also have $c' = c - 2 \le n - 2$.  Hence with the new variables, the conditions can be simplified to $1 \le a < b' < c' \le n - 2$.  That is, $\{a, b', c'\}$ is a set of three distinct integers between $1$ and $n-2$.  By definition of the binomial coefficient, there are $\binom{n-2}{3}$ ways of choosing $\{a, b', c'\}$.

A: In general, let $n\geq 0$ and $k\geq 0$ be integers.  Then, the number of ways to choose $k$ non-consecutive elements from $\{1,2,\ldots,n\}$ is $\dbinom{n-k+1}{k}$.  If the $k$ chosen numbers must differ by at least $d$ for some fixed integer $d\geq 0$, then the answer is $\dbinom{n-(d-1)(k-1)}{k}$.
