I am working with two terms like this
$$\sum_{i=0}^n {2i \choose i} {2n-2i \choose n-i}, \quad \sum_{i=0}^n {2n - 2i \choose n-i} 4^i$$
The latter will be
$$\sum_{i=0}^n {2n - 2i \choose n-i} 4^i = (2n+1) {2n \choose n}$$
I wonder how to prove such a result.
Thank you.
On
The first one is easy to compute with generating functions: it is the convolution of $\binom{2n}{n}$ with itself, hence its generating function is $$\left(\sum_{n=0}^\infty\binom{2n}{n}x^n\right)^2 = \frac{1}{1-4x}$$ so $\sum_{i=0}^n\binom{2i}{i}\binom{2(n-i)}{n-i} = 4^n$.
A combinatorial argument is suprisingly hard, see Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$
The generating function of the central binomial coefficients $\binom{2n}n$ is $\frac1{\sqrt{1-4x}}$ (see Generating functions and central binomial coefficient). We have
\begin{eqnarray} \sum_{n=0}^\infty\sum_{i=0}^n\binom{2n-2i}{n-i}4^ix^n &=& \sum_{i=0}^\infty\sum_{n=i}^\infty\binom{2n-2i}{n-i}4^ix^n \\ &=& \sum_{i=0}^\infty4^ix^i\sum_{n=i}^\infty\binom{2n-2i}{n-i}x^{n-i} \\ &=& \sum_{i=0}^\infty4^ix^i\sum_{n=0}^\infty\binom{2n}nx^n \\ &=& \frac1{1-4x}\cdot\frac1{\sqrt{1-4x}} \\ &=& (1-4x)^{-\frac32} \\ &=& \frac12\frac{\mathrm d}{\mathrm dx}\frac1{\sqrt{1-4x}} \\ &=& \frac12\frac{\mathrm d}{\mathrm dx}\sum_{n=0}^\infty\binom{2n}nx^n \\ &=& \frac12\sum_{n=1}^\infty\binom{2n}nnx^{n-1} \\ &=& \frac12\sum_{n=0}^\infty\binom{2n+2}{n+1}(n+1)x^n \\ &=& \sum_{n=0}^\infty\binom{2n}n(2n+1)x^n\;. \end{eqnarray}