Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same.
Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, 010, 011, 100$)
I am trying to get a recurrent formula of this problem but I don't know how to.
Let $T(n, k)$ represent the number of strings with k consecutive characters that are the same. We assume that a character can only hold either $0$ or $1$ just by going your example.
$T(n, n) = 2*1$ since there's only one string that has n consecutive characters for each character and we have 2 such characters.
$T(n, n-1)$ includes $T(n,n)$ as the strings counted by the latter already have $n-1$ consecutive identical characters. What remains is for us to find strings that have exactly $n-1$ consecutive characters which is given by $2 * (n - (n-1) + 1)$. Therefore:
$$T(n, n-1) = T(n,n) + 2 * (n- (n-1) + 1)$$
In general, we can count the number of strings with exactly k consecutive identical characters by $2 * (n - k + 1)$ where the $2$ factor comes from the # of characters possible ($0$ or $1$) and the $(n - k + 1)$ factor comes from the possible ways for a character to appear exactly k consecutively.
To find $T(n, k)$, we simply add up the possible strings that has exactly k consecutive identical characters, then the strings that has more than k consecutive exact characters given by $%T(n, k+1)$:
$$T(n, k) = 2 * (n - k + 1) + T(n, k + 1)$$
Therefore, the number of strings that do not have k consecutive identical characters in recurrence form is:
$$2^n - T(n,k) = 2^n - 2*(n-k+1) - T(n, k+1)$$
where $2^n$ is the total number of strings possible of n length and 2 characters.
