How many combinations of choosing $k$ numbers out of $\{1,2...,n\}$ so there are no consecutive numbers in a group, example: $\{1,4,9\}$. Find a recursion formula for $n\geq 0, k\geq0$.
I was thinking about $n\cdot F(n-3,k-1)$, means we have $n$ numbers to choose at first and then have to choose another $k-1$ out of the remaining $n-3$ (when taking off the chosen and it's consecutives), But might need times $n!$.
Would love if someone can explain what is wrong in this solution.
Thank you.
Also might need to break it apart to inner chosen numbers and numbers on edges like $1$ and $n$
Your solution is not quite right because of two reasons:
If a middle number is picked, then three numbers are excluded. If an end number, $1$ or $n$, is picked, then only two numbers are excluded. So it is not always $n-3$.
Taking a number from the middle destroys the non-consecutive condition. If take $5$, then what remains is e.g. $\{1,2,3,7,8,9\}$, but now it is OK to contain both $3$ and $7$, even though they are ordered next to each other.
Hint:
If $n$ is not in the set, you have a non-consecutive subset of $\{1,2,\dots,n-1\}$ of size $k$.
If $n$ is in the set, everything else is a non-consecutive subset of $\{1,2,\dots,n-2\}$ of size $k-1$.