I came to know that, in a random string, one expects the longest sequence of zeros to be roughly of length $\log n$. I want to be able to prove this. For this I need to know the probability that the longest sequence of zeros in a random $n$-bit string is of length $k$. Basically I need a good counting strategy to count the number of such $n$-bit strings i.e., where maximum run of zeros is of length $k$.
Can somebody give a hint on how to proceed? I don't want a full answer.
The number of $n$-bit strings with fewer than $k$ consecutive zeros is essentially a $k$-nacci number.
So (starting from $n=0$), the number of $n$-bit strings with fewer than $2$ consecutive zeros gives the sequence $1,2,3,5,8,13,21,34,\ldots$ which should be familiar, while the number of $n$-bit strings with fewer than $5$ consecutive zeros gives the sequence $1,2,4,8,16,31,61,120,\ldots$ which are essentially OEIS A001591, the pentanacci numbers (i.e. $120=61+31+16+8+4$).
Take differences and divide by $2^n$ to get the probability that the longest sequence of zeros in a random $n$-bit string is of length $k$.
I am not sure this will help in your proof.