I am trying to solve this question in different ways, but results don't tally, and some of them look incorrect to me. Can someone point out where are the loopholes in these logics?
Count the number of $n$-binary strings with at least $(n − 3)$ consecutive $1$s
1. Using inclusion-exclusion:
To obtain the number of binary strings of length $n$ and $(n − 3)$ consecutive $1$s, count number of ways $1$ can be placed in $(n-3)$ consecutive places, subtract number of ways $1$ can be placed in $(n-2)$ consecutive places (because those are counted twice for $(n-3)$), add number of ways $1$ can be placed in $(n-1)$ consecutive places (because those are subtracted twice for $(n-2)$), subtract number of ways $1$ can be placed in $n$ consecutive places (because those are counted twice for $(n-1)$).
Counting for $(n-3)$ case above. These $(n-3)$ $1$s can be placed among the remaining 3 digits in 4 ways. (left most position, right most position, left to the middle digit, right to the middle digit), and those 3 digits can be written in $2^3$ ways (each can be either 0 or 1). So the count for $(n-3)$ consecutive $1$s = $4.2^3=32$.
Similarly, count for $(n-2)$ is $3.2^2=12$.
count for $(n-1)$ is $2.2=4$.
count for $n$ is $1$.
So required count = $32 -12+4-1=23$.
2. Using recurrence:
Let $a_n$ be the count of ways an $n$-binary string can be made without $(n-3)$ consecutive $1$s. Then our required count will be $2^n - a_n$.
Now, consider the set of these $a_n$ arrangements. If we place a binary bit after them, then total number of possible binaries will be $2 a_n$ (as the last bit is either a $0$ or a $1$). The invalid cases will be only those cases where the last $(n-4)$ digits were all $1$ in the n-binary, and an $1$ is placed at the end, resulting in $(n-3)$ consecutive $1$s. Number of such cases = $2^3$ (because the 4th bit should be 0, and 5th to nth bit all 1s.)
So we get the recurrence relation, $2a_n=a_{n+1}+2^3$.
Solving this ..
$2a_{n-1}-a_{n}=2^3$
$2^2a_{n-2}-2a_{n-1}=2^4$
...
$2^{n-4}a_{4}-2^{n-5}a_{5}=2^{n-2}$
Adding all, we get, $2^{n-4}a_{4}-a_{n}=8(2^{n-4}-1)$
Base case $a_4=1$ (all 0s to place in one way).
So, $a_n=2^{n-4}-8(2^{n-4}-1)$
Required count = $2^n - 2^{n-4}+8(2^{n-4}-1)=2^n+2^{n-1}-2^{n-4}-2^3=3.2^{n-1}-2^{n-4}-2^3=23.2^{n-4}-8.$
3. Using generating function:
Coefficient of x less than n+1 and more than (n-3) in $(1+x+x^{n-3})^4$
Now, checking results for n=5, by manually counting all possible binaries, I am getting 19.
But inclusion-exclusion formula above gives 32, the recurrence formula gives 38, the generating function gives 55. All are mismatch. Please suggest where am I wrong in calculating these.