number of n length binary strings not containing specific factor [SOLVED].

Question

EDIT: Thanks to RobPratt's insight, (https://oeis.org/A005251), I wrote a quick and dirty python program to generate the number of bin strings not containing a 3 length string;

sols=[0,1,1,1]

def alg(n):
    n=int(n)
    x=len(sols)
    while x <= n+3:
        sols.append(sols[x-1]+sols[x-2]+sols[x-4])
        x+=1
    return sols[n+3]

def generate(n):
    n=int(n)
    for i in range(0,n):
        print(alg(i))


while True:
    prompt = input("Input either 'alg n' or 'generate n' >>   ").split(" ")
    if prompt[0] == 'alg':
        print(alg(prompt[1]))
    else:
        generate(prompt[1])

Wish me luck for my exam!!!

ORIGINAL POST:

Hey Maths StackExchange!

I apologise if any of the things I say in this post are naive or stupid; Im a first year comp sci student with an upcoming discrete maths test and Im in no way a competent mathematician.

I was doing a problem in which I had to count the number of binary strings of length n which do not contain the factor '101'.

I played around with the problem a little bit, and I think I found a general formula.

There are obviously 2^n binary strings, so the number of strings which don't contain the factor is 2^n - {strings that do contain the factor}.

For a string of length n=6, for example, this would mean that the strings;

101XXX
X101XX
XX101X
XXX101 

are defined as strings that contain the factor, where X ∈ {0,1}.

Im sure there is a more rigorous reason for this combinatorially, but by inspection I determined that there are always n-2 of these strings.

For each of these strings, I treated the X's as their own binary string, and given that there are n-3 X's in each string, the X's can form a possible 2^(n-3) binary strings.

Therefore, for an n length string, there are (n-2) formats, each containing 2^(n-3) possible strings, and therefore for an n length string there are; $$2^n - (n-2)2^{n-3}$$ strings not containing the factor '101'.

I also realise that this formula only relies on the length of the factor '101', so it could be generalised to; $$2^n - (n-(k-1))2^{n-k}$$ where k is the length of the factor.

The reason I am writing this is pretty much just to ask if my formula seems correct, because if it does, I intend to use it in my test.

Thanks!