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?
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.