Prove that $a_n = 2^n$

Question

Let the recurrence relation

$$ a_0 = 1 \\ a_{n+1} = \frac{2 \sum_{k=0}^n a_ka_{n-k}}{n+1} $$

I need to find a close formula for this recurrence. I've noticed that $a_n = 2^n$.

I tried to prove it by induction: assuming the the statement is true for $n-1$, lets prove it for $n$:

$$a_n = \frac{2 \sum_{k=0}^n a_k a_{n-k}}{n} = \frac{2 \left( \sum_{k=0}^{n-2} a_k a_{n-k} + a_{n-1}a_1 \right)}{n} = ?$$

Somehow I need to utilize the induction assumption, but I don't know how.

Answer 1

$$a_{n+1}=\frac{2\sum_{k=0}^na_ka_{n-k}}{n+1}=\frac{2\sum_{k=0}^n2^k2^{n-k}}{n+1}=\frac{2\sum_{k=0}^n2^n}{n+1}=2^{n+1}$$

Answer 2

Let $f(z) = \sum_{n=0}^\infty a_n z^n$. Then the recurrence relation reads: $$ f^\prime(z) = 2 f(z)^2 \quad f(0) = 1 $$ which is easily solved into $f(z) = \frac{1}{1 - 2z}$. Extracting the series coefficient: $$ a_n = [z^n] \frac{1}{1 - 2z} = 2^n $$