Proving an Identity involving $4^N$ 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. 
 A: 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.
A: 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.
A: 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$$
