A cute problem from reddit.
You have $2n$ people standing in an infinite row at spots say $1,2,3,..,2n$ (one person at each spot). A scientist performs the following steps repeatedly.
Clone every person on the row, and move the clones one position the right i.e. if there were $x$ people at position $k$, you create $x$ clones and place them at position $k+1$. Note that this is done for every position in parallel (so no moving clones twice etc). Previously empty positions could see folks being moved there.
After $2n-1$ repeats of the above steps, how many people will be there at position $n$?
Scroll down for a solution.
.
.
.
Suppose there are $p_j$ people at position $j$ ($j >= 1$).
Then the steps is basically replacing $p_{k+1}$ with $p_{k+1} + p_{k}$
This looks ripe for matrices, the steps are basically a linear transformation, but the matrix is large, of size $4n-1$ or so.
There is another way to look at this: polynomials!
Let $$f(z) = \sum_{n=1}^{\infty} p_n z^n$$
(Even though there is infinity, it is still a finite polynomial as all $p_i = 0$ after a certain point)
Then the steps are basically replacing $f(z)$ by $f(z) (z+1)$
Initially $$f(z) = z + z^2 + \dots + z^{2n}$$
After $2n-1$ steps we get
$$(z+z^2 +\dots +z^{2n})(1+z)^{2n-1} = $$
$$(z + z^2 + \dots + z^{2n}) (\sum_{r=0}^{2n-1} \binom{2n-1}{r} z^r)$$
(using binomial theorem on $(1+z)^{2n-1}$)
The number of people in row $n$ is coefficient of $z^n$ and that comes out to be
$$\sum_{r=0}^{n} \binom{2n-1}{r} = \frac{2^{2n-1}}{2} = 2^{2n-2}$$
(using $\binom{2n-1}{r} = \binom{2n-1}{2n-1-r}$ and adding them up to get $2^{2n-1}$)
