2
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Exactly what I was looking for, thanks. I like the trick to get rid of the sum in the recurrence. $\endgroup$ Dec 21, 2013 at 12:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .