I'm thinking about the problem below. I know that I have to find a polynomial formula for that first, and then from that polynomial formula I can find the recurrence relation. I actually attempted finding a polynomial formula, but I think I'm leaving some options while thinking about three consecutive integers. Anyway, without further ado, here is the problem and your suggestions are appreciated:
Let $f_n$ be the number of subsets of $\{1,2,3,\ldots, n\}$ that contain no three consecutive integers. Find a recurrence for $f_n$.