Looking for expectation of the number of substrings The question is formulated as follows: if we are given $n$ random binary strings of length $n$, what is the expectation of the number of substrings they have in common? 
Sounds pretty simple, but if you look closer...well, a solution would be great but I would much appreciate a hint as well.
 A: You need to specify what counts as a matching substring.  For example, if 3 consecutive digits match, does that count as 1 substring, or is it 1 substring of length 3, plus 2 of length 2, and 3 of length 1? In the later case we have.
$$E(\text{number of substrings}) = \sum_{k=1}^n(n-k+1)/2^k$$
where n-k+1 is the number of substrings of length k, and $1/2^k$ is the probability that a substring of length k matches.  Note it doesn't matter that these overlap and are not independent since the expected value of a sum of random variables is always the sum of expected values.  Here that would be the sum of the matching probabilities for each substring.  You can sum this series as a difference of 2 sums.  One is related to a  geometric series, and the other related to the derivative of a geometric series.  Now if only the longest substring match counts, the probabilities need to be modified to $1/2^{k+2}$ for the substrings that do not include the first or last digit since the digits before and after must not match.  For the substrings that include the first or last digit but not both, it would be $1/2^{k+1}$, and for the ones that include both it would be $1/2^k$.
