Number of subsets that do not contain $4$ consecutive integers. How many subsets of the set $\{1,2,3,4,5,6,7,8,9,10\}$ are there that do not contain $4$ consecutive integers.
My Attempt:
Hint given is 'try recursive sequence'.But do not know how to proceed.
 A: We recurse over the elements from $10$ to $1$. At each point, we determine whether or not we wish to include that number in our subset. But we also need to keep track of how many consecutive elements we've taken so far as we've traversed through the recursion, making sure not to take more than $3$.
Let $W_0(n)$ be the number of subsets with $n$ elements left under the assumption that the previous element was not $n+1$.
Let $W_1(n)$ be the number of subsets with $n$ elements left under the assumption that the previous element was $n+1$.
Let $W_2(n)$ be the number of subsets with $n$ elements left under the assumption that the previous two elements selected were $n+1$ and $n+2$.
Let $W_3(n)$ be the number of subsets with $n$ elements left under the assumption that the previous two elements selected were $n+1$, $n+2$, and $n+3$.
Then we have:
$$W_0(n) = W_1(n-1) + W_0(n-1)$$
$$W_1(n) = W_2(n-1) + W_0(n-1)$$
$$W_2(n) = W_3(n-1) + W_0(n-1)$$
$$W_3(n) = W_0(n-1)$$
This all simplifies to 
$$W_0(n) = W_0(n-4) + W_0(n-3) + W_0(n-2) + W_0(n-1)$$
Where $W_0(k) = 2^k$ for $0 \leq k \lt 4$. And in particular:
$$W_0(10) = 773$$
