I would like to know if the following is a valid question. How can I choose $x$ integers from the first $n$ integers such that there is a minimum difference of 2 between any two chosen integers.
My method: Seeing the bijection between chosen integers and $n$-digit long binary sequences($1$ if integer is selected, $0$ if not), let $a_n$ be the number of ways required to choose digits from $n$ integers such that no two are consecutive[sorry if my language is unclear]. So, sequences can either start from $100...$ or $0...$. Hence $a_n=a_{n-1}+a_{n-3}$. But could you help me with the initial conditions? And, with further proceedings too. Thank you.
If you dont need to use recurrences, this question has a simple closed form solution hinted at here and here.
If you want to use recurrences, it is $a(n,x) = a(n-1, x) + a(n-3,x-1)$. However, I don't know how to turn that into a closed form solution. (I'm not good with generating functions.) I suppose, since you can find the closed form (from the links above), you can then prove that it fits the recurrence, and thereby prove it inductively. But that's a bit of cheating, right? Because how would you know what the closed form solution looks like in the first place?