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

Question

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$

Answer 1

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.

Answer 2

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