b[1] = {"0", "1"};
 b[n_] := b[n] =
   Join[Table[b[n - 1][[i]] <> "1", {i, 1, Length[b[n - 1]]}],
     Table[b[n - 1][[i]] <> "0", {i, 1, Length[b[n - 1]]}]];
NO111[n_] :=
  Cases[b[n],
   x_ /; StringMatchQ[x, RegularExpression["(?s).*(111)(?s).*"]] ==
     False];
T = Table[{n, Length[NO111[n]]}, {n, 1, 20}];
TableForm[T,
 TableHeadings -> {None, {"n",
    "# bit strings of length n NOT containing 111"}}]