Find the general term of the recursive relation $a_{n+1}=\frac{1}{n+1}\sum\limits_{k=0}^n a_k 2^{2n-2k+1}$ I need to find the general term of the recursive relation $a_{n+1}=\frac{1}{n+1}\sum\limits_{k=0}^n a_k 2^{2n-2k+1}$
I know it's the central binomial sequence but I can't find a way to show it.
$a_0=1$
 A: We are given the recurrence relation
$$a_{n+1}=\frac{1}{n+1}\sum_{k=0}^{n}a_{k}2^{2n-2k+1}.$$
Then,
$$a_{n}=\frac{1}{n}\sum_{k=0}^{n-1}a_{k}2^{2n-2k-1}.$$
Multiplying the relation for $a_n$ on both sides by $\frac{2^2n}{n+1}$,
$$\frac{2^2n}{n+1}a_{n}=\frac{1}{n+1}\sum_{k=0}^{n-1}a_{k}2^{2n-2k+1}.$$
Subtracting this from the original recurrence relation, we get
$$a_{n+1}-\frac{2^2n}{n+1}a_{n} = \frac{1}{n+1}a_{n}2^{2n-2n+1} = \frac{2\,a_{n}}{n+1}\\
\implies a_{n+1} = \frac{2(2n-1)}{n+1}a_{n}.$$
Now we have a simple linear recurrence relation which may be solved by more familiar methods.
A: Use generating functions. Define:
$$
A(z) = \sum_{n \ge 0} a_n z^n
$$
Write:
$$
(n + 1) a_{n + 1} = 2 \sum_{0 \le k \le n} a_k 4^{n - k}
$$
Note that the right hand side is the convolution of $4^n$ with $a_n$. Using properties of ordinary generating functions this gives:
$$
(z \mathrm{D} + 1) \frac{A(z) - a_0}{z} = 2 \frac{A(z)}{1 - 4 z}
$$
This is a first order linear differential equation ($\mathrm{D}$ is derivative), but it has an ugly solution...
Update: I made a mistake in the original, the correct ODE has a pleasant solution:
\begin{align}
A(z) &= (1 - 4 z)^{-1/2} \\
     &= \sum_{n \ge 0} \binom{2n}{n} z^n
\end{align}
so that:
$$
a_n = \binom{2 n}{n}
$$
