A cloning problem from a reddit math contest

 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}$)