Probability of binary string prefix divisibility by 3 What is the probability of an evenly distributed binary string of length $n$ to have a prefix that is divisible by $3$? I know that divisibility by $3$ of a binary string is equivalent to the divisibility of the (sum of bits on even positions)-(sum of bits on odd positions), but that doesn't help much.
I've noticed that any string starting with $0$ has a divisible by $3$ prefix, and so does any string starting with $11$. However, I cannot put enough restrictions on the $3$rd bit, because both $101$ and $100$ aren't divisible by zero. This calls for a solution using dynamic programming, but I need to find a closed-form solution.
A solution for any $p$, not just $3$ would be also much appreciated.
 A: I turns out that it’s easier to count the strings that don’t have a prefix divisible by $3$ and subtract the result from $2^n$. We just need to keep track of their remainder modulo $3$. 
So let $a_n$ and $b_n$ be the number of binary strings of length $n$ without prefix divisible by $3$ and with remainder $1$ and $2$ modulo $3$, respectively.
If we append a $0$ to a string of length $n$, we get $a_n$ strings with remainder $2$ and $b_n$ strings with remainder $1$. If we append a $1$, we only get $b_n$ strings with remainder $2$ (because if we append a $1$ to a string with remainder $1$, it becomes divisible by $3$). Thus
\begin{eqnarray}
a_{n+1}&=&b_n\;,\\
b_{n+1}&=&a_n+b_n\;.\\
\end{eqnarray}
Substituting the first equation into the second yields $b_{n+1}=b_{n-1}+b_n$, the recurrence for the Fibonacci numbers. The initial values are $b_1=0$, $b_2=1$, shifted by $1$ respect to the Fibonacci numbers, so $b_n=F_{n-1}$, and thus $a_n=F_{n-2}$. It follows that the number of binary strings of length $n$ with a prefix divisible by $3$ is $2^n-F_{n-1}-F_{n-2}=2^n-F_n$, so the probability for a uniformly random binary string of length $n$ to have a prefix divisible by $3$ is $1-2^{-n}F_n$.
For prefixes divisible by $4$, we can keep track of strings ending in $10$ and in $1$ and subtract them from $2^n$. If we denote their counts by $a_n$ and $b_n$, respectively, we get the same recurrence again as above, but with different initial values: $b_1=1$, $b_2=1$, so now we have $b_n=F_n$ and $a_n=F_{n-1}$, so the proportion of binary strings of length $n$ with a prefix divisible by $4$ is $1-2^{-n}F_{n+1}$.
If you look at the OEIS entry for the Fibonacci numbers, you’ll find that they count binary strings that fulfill various conditions, but having a prefix divisible by $3$ or $4$ isn’t mentioned there yet.
For modulo $5$, things get slightly more complicated. We need to keep track of all four remainders. Denoting the counts for remainders $1$, $2$, $3$ and $4$ by $a_n$, $b_n$, $c_n$ and $d_n$, respectively, we have
\begin{eqnarray}
a_{n+1}&=&c_n\;,\\
b_{n+1}&=&a_n+c_n\;,\\
c_{n+1}&=&d_n+a_n\;,\\
d_{n+1}&=&b_n+d_n\;,\\
\end{eqnarray}
or in matrix form,
$$
\pmatrix{a_{n+1}\\b_{n+1}\\c_{n+1}\\d_{n+1}}=\pmatrix{
0&0&1&0\\
1&0&1&0\\
1&0&0&1\\
0&1&0&1\\
}\pmatrix{a_n\\b_n\\c_n\\d_n}\;.
$$
Unfortunately this matrix has a rather messy eigensystem (I dare you to click “exact form” :-), so we can’t express the result in a nice closed form, but we do find that the largest eigenvalue (and the only one of magnitude greater than $1$) is approximately $1.75488$, so whereas the number of binary strings of length $n$ grows as $2^n$, the number of binary strings of length $n$ without prefix divisible by $5$ grows approximately as $1.75488^n$, compared to the golden section ratio $\left(\frac{1+\sqrt5}2\right)^n\approx1.61803^n$ for the Fibonacci numbers in the case of modulo $3$ or $4$.
