Number of particles at time $t$ A following problem appears in my text book under the section of induction:
At time $0$, a particle resides at the point $0$ on the real line. Within $1$
second, it divides into $2$ particles that fly in opposite directions and
stop at distance $1$ from the original particle. Within the next second,
each of these particles again divides into $2$ particles flying in opposite
directions and stopping at distance $1$ from the point of division, and so
on. Whenever particles meet they annihilate (leaving nothing behind).
How many particles will there be at time $2^{11} + 1$?
I checked the values up to time 16 and observed that each time we are dealing with the time point that corresponds to some power of 2 the distribution of particles is such that only the 2 "outer" particles (the left-most and right-most on the real line) remain, all of the "inner particles" are annihilated because they happen to "collide".
So, I think the answer is that at time $2^{11} + 1$ the number of particles is exactly four, because at time $2^{11}$ only the outer particles remain (thus there are 2), and at the next time point ($2^{11}+1$) 2 more particles will be created from each (none are annihilated), so there must be two more, altogether 4.
However, this hardly seems like a proof and lacks all mathematical rigour (although the problem does not ask for a proof). So, how would I come about proving this result? 
 A: There will be 4 particles after $2^{11}$ + 1 seconds, coz after every $2^{n}$ sec there remains only 2 particles, so on the very next step these two will become 4.
You can refer to the snap below:

A: You would get the same numbers of particles at each step if one particle stayed in place and the other moved two units to the right. Using $1$ for a particle and $0$ for a space, we start with $1$ and then go successively to $101$, $10001$, $1010101$, and $100000001$. As you've noticed, after $2^n$ steps you have two $1$s that are $2^{n+1}$ units apart. You can prove by induction on $n$ that this is actually true in general. Suppose that it's true for some $n$. It takes $2^n$ stages for anything deriving from the first $1$ to reach the second $1$, so for $2^n-1$ stages the two $1$s develop independently, just as the original $1$ did in the first $2^n$ steps. This means that at stage $2^n+2^n=2^{n+1}$, just before annihilation, we have $$1\underbrace{0\ldots 0}_{2^{n+1}-1}2\underbrace{0\ldots 0}_{2^{n+1}-1}1\;,$$ which reduces to a pair of $1$s $2^{n+2}$ units apart. This completes the induction, and of course once you have this, your conclusion that there are four $1$s after $2^{11}+1$ steps is immediate.
