How many subsets does the set {1, 2, ... , n} have that contain no three consecutive integers

Find a recurrence

This problem is isomorphic to one I just answered a little while ago.
http://answers.yahoo.com/question/index?…

Let the subsets be represented by bit strings of length n.
Number the bits as:
1 2 3 . . . . . n

If a number is in the subset, then put a 1 bit.
If a number is missing from a subset, then put a 0 bit.

So for n = 4, the bit string
1001 represents the subset {1, 4}
and
0010 represents the subset {3}.

Then the question reduces to: how many bit strings of length n do not have "111" in them?

Those that DO have 111 are described here: https://oeis.org/A050231
which has recursive formula:
a(n) = 2 * a(n-1) + 2^(n-4) - a(n-4)
because we can add 0 or 1 to such a string of length n-1
and 1 to such a string of length n-1 which ends in 011
if the preceding bits do not have 111 in them, and there are 2^(n-4) - a(n-4) of those.

The complementary sequence which is wanted here is
2^n - a(n) above.

It is described here: https://oeis.org/A000073
These are the Tribonacci numbers, and have formula
a(n) = a(n-1) + a(n-2) + a(n-3)
because
a sequence with no 111 in it of length n can be formed by:
adding a 0 to one of length (n-1)
adding 01 to one of length (n-2) or
adding 011 to one of length (n-3)