Solving the recurrence $x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$

Question

In my answer over at cstheory.stackexchange.com I set variables according to the recurrence $$x_0=1, x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$$ Wolfram Alpha tells me that apparently the solution to this recurrence is $$x_n = \frac{\binom{2n}{n}}{4^n}$$ I would like to know why this is the case, but I don't know enough about sums of binomial coefficients to figure this out myself.

Answer 1

We can rewrite the recursion. We have

$$x_{n+1} = \frac{1}{2(n+1)}\sum_{i=0}^n x_i = \frac{1}{2(n+1)}\left(x_n + \sum_{i=0}^{n-1}x_i\right) = \frac{1}{2(n+1)}(x_n + 2nx_n) = \frac{2n+1}{2n+2}x_n.$$

In that form, it is easy to see that

$$\frac{2n+1}{2n+2}4^{-n}\binom{2n}{n} = \frac{(2n+2)(2n+1)}{4(n+1)^2}4^{-n}\binom{2n}{n} = 4^{-(n+1)}\binom{2n+2}{n+1}.$$