3
$\begingroup$

I am trying to prove the following identity:

$$\sum_{k=0}^N\left({2 \, N - 2 \, k \choose N - k}{2 \, k \choose k}\right)=4^N$$

I have tried writing $4^N=2^{2N}=(1+1)^{2N}=(1+1)^N(1+1)^N$, and expanding each of these as a binomial expansion, but I have found nothing but dead ends so far. Any ideas?

I am currently working through a Ch. 3 "Generating Functions" from Analysis of Algorithms by Sedgewick/Flajolet. This is problem #30.

Thanks.

$\endgroup$

marked as duplicate by Brian M. Scott, Amzoti, Start wearing purple, Hagen von Eitzen, Jared Jul 17 '13 at 21:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You could try Herbert Wilf's Snake Oil Method here $\endgroup$ – Torsten Hĕrculĕ Cärlemän Jul 17 '13 at 19:58
  • $\begingroup$ You’ll find both combinatorial and non-combinatorial proofs here and here. $\endgroup$ – Brian M. Scott Jul 17 '13 at 20:46
5
$\begingroup$

Let, $f(x)=\displaystyle\sum_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$. Then your LHS will be coefficient of $x^N$ of $f^2(x)=(1-4x)^{-1}$ which is $4^N$=RHS.

$\endgroup$
1
$\begingroup$

Start off by noting $$ \sum_{k=0}^{N}\binom{2N-2k}{N-k}\binom{2k}{k}=[x^{N}]\left(\sum_{k=0}^{\infty}\binom{2k}{k}x^{k}\right)^2. $$ Now, what's inside the square is the OGF for the central binomial coefficients; you may have seen it before. It happens that $$ \sum_{k=0}^{\infty}\binom{2k}{k}x^k=\frac{1}{\sqrt{1-4x}}. $$ So, we find that $$ \sum_{k=0}^{N}\binom{2N-2k}{N-k}\binom{2k}{k}=[x^N]\frac{1}{1-4x}=[x^N]\sum_{k=0}^{\infty}(4x)^k=4^N, $$ as claimed.

$\endgroup$
1
$\begingroup$

Starting $$\tag 1\binom {n}{k}\binom{n-1/2}{k}=\binom{2n}{2k}\binom{2k}{k}/2^{2k}$$ In particular:

$$ \tag 2 \binom{-1/2}{k}=\bigg (\frac {-1}{4}\bigg) ^k\binom{2k}{k}$$

Now consider following Vandermonde's identity:

$$\sum\limits_{k}\binom{-1/2}{k}\binom{-1/2}{n-k}=\binom{-1}{n}=(-1)^n$$

Inserting $(2)$ and remove summing

$$\tag3 \binom{-1/2}{k}\binom{-1/2}{n-k}=\bigg (\frac {-1}{4}\bigg) ^k\binom{2k}{k}\bigg (\frac {-1}{4}\bigg) ^{n-k}\binom{2n-2k}{n-k}=\bigg (\frac {-1}{4}\bigg)^n\binom{2k}{k}\binom{2n-2k}{n-k}$$

Finally summing again:

$$\sum\limits_{k}\binom{2k}{k}\binom{2n-2k}{n-k}=4^n$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.