Recursive solution to "Number of subsets of a set without 3 following numbers"

Question

so I got the following problem: For a given natural n number, let A be the set A={1,2,...,n}

I need to provide a recursive solution that will return the number of possible subsets that doesn't contain 3 following numbers.

For i.e.

n=3, A={1,2,3}. Possible subsets are: {empty}{1}{2}{3}{1,2}{1,3}{2,3}, so the recusrive function will return $a_3$=7

I started with $a_n=a_{n-1}+2b_{n-1}$, $b_n=$The number of subgroups that contain n or n-1 but not both. But I got no idea how to get rid of the b.

Answer 1

Given a legit subset $S$ for $n-1$, you get two legit subsets for $n$, one by just taking $S$, the other by sticking $n$ into $S$, provided $S$ doesn't contain both $n-1$ and $n-2$. So, $a_n=2a_{n-1}-c_{n-1}$, where $c_m$ is the number of legit subsets for $m$ using both $m$ and $m-1$. But then $c_m$ is the number of legit subsets for $m-3$, because you can take any such subset and stick in $m-1$ and $m$. So, $c_m=a_{m-3}$.

So, a recurrence for $a_n$ is ....