How many bitstrings of length n contain 3 consecutive ones ("111")?

Question

I tried creating a recurrence formula. Can someone evaluate it?

a(n) =a(n-1)+2^(n-3)+a(n-3)

0-> followed by bitstring of length n-1 (represented by a(n-1))

1->10->101;

1->10->100;

1->11->110;

so on

Answer 1

The correct recurrence is $a(n)=2^{n-3}+a(n-1)+a(n-2)+a(n-3)$ and it doesn't have a nice closed form solution. See OEIS A050231 for more information.

The explanation is: $2^{n-3}$ strings starting with $111$; $a(n-1)$ strings starting with $0$; $a(n-2)$ strings starting with $10$ and $a(n-3)$ strings starting with $110$.