$(1$ point$)$ Find a recurrence relation for the number of bit strings of length $n$ that do not contain the substring $1111$

a$)a_n=2a_{n-1}+2a_{n-2}+4a_{n-3}$

b$)a_n=2a_{n-1}+2a_{n-2}+2a_{n-3}+2a_{n-4}$;

c$)a_n=a_{n-1}+a_{n-2}+a_{n-3}$

d$)a_n=4a_{n-1}+4a_{n-2}$

e$)a_n=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}$