Number of distinct binary strings made by inserting m characters into a given string Let $s$ be a length $n$ binary string. It is natural to ask how many distinct length $n+m$ binary strings can be made by inserting $m$ binary characters into $s$. 
As an example, we can consider the distinct strings made by inserting two characters into the string $001$. Since we are inserting two characters, we are either inserting two $0$'s, one $1$ and one $0$, or two $1$'s. Inserting two $0$'s may be done in the three following distinct ways: $$00001, 00010, 00100~.$$ Inserting one $1$ and one $0$ may be done in the seven following distinct ways: $$10001, 01001, 00101, 00011, 10010, 01010, 00110~.$$ Finally, inserting two $1$'s may be done in the six following distinct ways: $$11001, 10101, 10011, 01101, 01011, 00111~.$$ Therefore we have 16 distinct strings made by inserting two characters into $001$.
Using a similar process, we can show that there are $16$ distinct strings made by inserting two characters into $000$. Similarly, there are $16$ distinct strings made by inserting two characters into $010$. In fact, for any length $3$ binary string $s$ there are $16$ distinct strings made by inserting two characters into $s$. 
After discovering this, I wrote some Python code to see if this sort of thing holds more generally. As it turns out, the number of distinct strings made by inserting $m$ characters into a binary string $s$ is the same for all $s$ of length $n$. Furthermore, we get the following formula for the number of distinct strings $S$ as a function of $n$ and $m$:
$$S(n,m) = {n+m \choose 0} + {n+m \choose 1} + {n+m \choose 2} + ... + {n+m \choose m}~.$$
If we assume that $S(n,m)$ is well-defined for all $n$ and $m$ (that is, if different base strings of length $n$ give the same answer), then proving this formula is relatively straightforward. In the case of the base string $00 \ldots 0$ of length $n$, the strings of length $n+m$ formed by inserting $m$ characters are precisely the binary strings of length $n+m$ containing at least $n$ zeros. These can be counted by ignoring the strings of length $n+m$ with fewer than $n$ zeros.
$$\begin{align}S(n,m) &= 2^{n+m} - {n+m \choose 0} - {n+m \choose 1} - ... - {n+m \choose n-1} \\ &= {n+m \choose n} + {n+m \choose n+1} + ... + {n+m \choose n+m} \\ &= {n+m \choose 0} + {n+m \choose 1} + ... + {n+m \choose m}.\end{align}$$
This proof of the formula only works, however, if we are willing to grant that the number of distinct strings depends only on $m$ and on the length $n$ of the base string. I was unable to prove this fact. Can someone provide a deeper explanation of what's going on here?
 A: Think of it in a different way.  Given binary strings $T$ and $S$ of lengths $n+m$ and $n$ respectively, $T$ can be obtained from $S$ by inserting $m$ characters if and only if $S$ is a subsequence of $T$.  Now, when is that true?
If it is, the subsequence can be obtained as follows.
Starting at the left, let $i_1$ be the first position $i$ where $T_i = S_1$,
let $i_2$ be the first $i > i_1$ where $T_i = S_2$, ..., $i_n$ the first $i > i_{n-1}$ where $T_i = S_n$.  If you can define $i_1, \ldots, i_n$ in this way, i.e. you never get to a point where there are no $i > i_{k-1}$ such that $T_i = S_k$, 
then  $S$ is the subsequence $T_{i_1},\ldots, T_{i_n}$.  
Now, given two binary strings $S$ and $S'$ of length $n$, I will define a map $f$
from $\{0,1\}^{n+m}$ to itself such that $S$ is a subsequence of $T$ if and only if 
$S'$ is a subsequence of $f(T)$.  Consider the construction above for $T$ and $S$, obtaining $i_1, \ldots, i_k$ (where either $k=n$, in which case $S$ is a subsequence of $T$, or $k < n$ and $i_{k+1}$ does not exist).  For convenience, take $i_0 = 0$, and $i_{k+1} = n+m+1$. If $i_{j-1} < i \le i_{j}$, let $f(T)_i = T_i$ if $S_j = S'_j$ (or $j = n+1$),
$1-T_i$ if $S_j \ne S'_j$.  It is easy to see that $f$ is a one-to-one correspondence and has the desired property.  This shows that the number of $T$ with $S$ as a subsequence is equal to the number with $S'$ as a subsequence. 
A: A direct proof of the formula for $S(n,m)$ inspired by Robert's approach. Taking after Robert, we can reformulate this question as "how many length $n+m$ binary strings have a given length $n$ string as a subsequence?" Also taking from Robert, we know that if a length $n$ sub-sequence $S$ appears in a length $n+m$ binary string $T$, then it must appear a "first time" in the sense that there exist indices $i_1<i_2<...<i_n$ such that $i_1$ is the smallest index such that $T_{i_1} = S_1$, and such that each of the $i_k$'s is the smallest $i$ such that $i_k > i_{k-1}$ and such that $T_{i_k} = S_k$. 
To count the number of length $n+m$ binary strings containing $S$ as a sub-sequence, we add together the number of strings such that $i_n = n$, the number such that $i_n = n+1$, the number such that $i_n = n+2$, etc. out to the number of strings such that $i_n = n+m$.  
How many length $n+m$ strings are there such that $i_n = n$? Such strings must have the string $S$ as the first $n$ characters, but are allowed to vary freely in their last $m$ characters. Hence we have $2^m$ such strings. 
How many length $n+m$ strings are there such that $i_n = n+1$? Such strings must be such that $T_{n+1} = S_n$, and they must contain exactly one index $i < n+1$ such that $i \not\in i_1,i_2,...,i_n$. There are ${n \choose 1}$ ways this $i$ can be placed. Since the placement of this $i$ determines the value ($1$ or $0$) that $T_i$ takes (in order to be consistent with the fact that $i \not\in i_1,i_2,...,i_n$), and since the $m-1$ characters after $T_{n+1}$ can vary freely, we deduce that there are ${n \choose 1} \cdot 2^{m-1}$  strings such that $i_n = n + 1$.
How many length $n+m$ strings are there such that $i_n = n+2$? Such strings must be such that $T_{n+2} = S_n$, and they must contain indices $i_a<i_b < n+2$ such that $i_a,i_b \not\in i_1,i_2,...,i_n$. There are ${n+1 \choose 2}$ ways $i_a$ and $i_b$ can be placed. Since the placement of these indices determines the values ($1$ or $0$) that $T_{i_a}$ and $T_{i_b}$ take (in order to be consistent with the fact that $i_a,i_b \not\in i_1,i_2,...,i_n$), and since the $m-2$ characters after $T_{n+2}$ can vary freely, we deduce that there are ${n+1 \choose 2} \cdot 2^{m-2}$  strings such that $i_n = n + 2$.
Continuing this pattern, we deduce that
$$S(n,m) = \sum_{i = 0}^{m}2^{m-i}{n-1+i \choose i}.$$
The goal, however, was to prove that 
$$S(n,m) = \sum_{i=0}^{m}{n+m \choose i}.$$
The equivalence of these two sums can be seen using Pascal's Triangle. This approach, which I won't give in full detail, relies on repeated applications of Pascal's Rule, and is similar in spirit to the proof by induction that the sum of the terms in the $n$th row of Pascal's Triangle is $2^n$.
A: For each length $n$ string $A$ contained in a length $m+n$ string $B$, there is a unique first occurrence of $A$ in $B$.  To find it, just start looking for the first character of $A$ (either a 0 or a 1) at the left side of $B$ and move right until you find one.  Then move right until you find the second character of $A$, and so on until you've found all the characters of $A$.  
For how many strings $B$ will the first occurrence of $A$ be found in the leftmost $n+k$ characters of $B$ (and in no fewer)?  Well, there must be $k$ instances where you moved right without finding the next character of $A$.  So  between the successive characters of $A$ in $B$, there had to have been $k$ instances of the "wrong" character.  There are $n$ bins to put these "wrong" characters into (before the first character of $A$, between the first and second, between the second and third, etc.), so using the formula for number of ways to put $k$ balls in $n$ boxes, there are $\binom{n+k-1}{k}$ choices for the first $n+k$ characters of $B$.  Then the remaining $m-k$ characters of $B$ are totally unconstrained, so there are $2^{m-k}$ choices for these.  Summing over $k$, the total number of strings $B$ containing $A$ is
$$\sum_{k=0}^m \binom{n+k-1}{k}2^{m-k}$$
This formula is independent of the string $A$, which proves your point.  It also establishes a combinatorial proof of equality between this sum and the one you discovered. 
