Find a linear reccurrence relation where a(n) is the number of subsets of {1,2,3,...,n} not containing three consecutive numbers.

Question

Find a linear constant coefficient for the recurrence relation $a(n)$ where $a(n)$ is the number of subsets of $\{1,2,3,\dots,n\}$ not containing three consecutive numbers.

So $a(n)$ must have a recurrence relation where it can be traced that the the two numbers are not greater or higher than the first?

Answer 1

Let $A(n)$ be the number that don't include $n$.
Let $B(n)$ be the number that include $n$ but not $n-1$.
Let $C(n)$ be the number that include $n$ and $n-1$.
Find recursions for all three.