Recursion formula to number of binary vectors without $k$ $1$'s

Question

Find a recursion formula for the number of binary vectors in length n that doesn't contain $k$ consecutive $1$'s. $(k\geq 2)$

If $n<k$ it's clear there are not limitations therefore $2^n$.
If $n\geq k$, I was thinking about 2 forms, define $F(n)$ a legal vector:

$\ \ $I. The vector starts with $0$ - remains $n-1$ bits $\Rightarrow F(n-1)$
$\ \ $II. The vector starts with $k-1$ 1's and must have 0 after $\Rightarrow F(n-k)$ .

My problem is first that I'm not sure about the concept of solution, second, how to sum it all up, third, what are my non recursively defined values ($F(0),F(k-1)?)$?

Thanks.

Answer 1

Assume that $F(k, n)$ is the number of different $n$-bit vectors and less than $k$ consecutive $1$ bits.

A complementary function $G(k, n)$ is the number of different $n$-bit vectors with at least $k$ consecutive $1$ bits.

In the following, $k$ is assumed to be less than or equal to $n$.

The sum of both functions is the total number of different $n$-bit vectors: $$F(k, n) + G(k, n) = 2^n$$ There is only one $n$-bit vector with all bits set to $1$ $$G(k=n, n) = 1$$ Reducing $k$ from $n$ to $n-1$ results in additional $2$ vectors, as the reduced $1$ bit can be replaced by $0$ on both ends: $$G(k=n-1,n) = G(n, n) + 2 = 3$$ Similarly, extending the bit-length from $n$ to $n+1$ while keeping $k$ constant: $$G(k=n, n+1) = G(n+1, n+1) + 2 = 3$$

The following table lists values for $G(k, n)$:

.   n=2 n=3 n=4 n=5 n=6 n=7 n=8
k=2  1   3   8   19  43  94 201   2^n - Fibonacci(n+2)
k=3      1   3    8  20  47 107   2^n - Tribonacci(n+3)
k=4          1    3   8  20  48
k=5               1   3   8  20
k=6                   1   3   8
k=7                       1   3
k=8                           1

You'll find the first two sequences as A008466 and A050231.