Proving a formula about binomial coefficients I found the following formula in a book without any proof:
$$\sum_{j=k}^{\lfloor\frac n2\rfloor}{\binom{n}{2j}}{\binom{j}{k}}=\frac{n}{n-k}\cdot2^{n-2k-1}{\binom{n-k}{k}}$$
where $n$ is a natural number and $k$ is an integer which satisfies $0\le k \le\frac n2$. 
I've tried to prove this, but I'm facing difficulty. Could you show me how to prove this?
 A: I've just been able to prove this relational expression. 
I'm going to use the followings : 
$$\cos{n\theta}=n\sum_{l=0}^{\lfloor\frac{n}{2}\rfloor}\{(-1)^l\cdot2^{n-2l-1}\cdot\frac{\binom{n-l}{l}}{n-l}\cos^{n-2l}{\theta}\}\ \ \ \cdots(\star),$$
$$\sin{n\theta}=\sum_{l=0}^{\lfloor\frac{n-1}{2}\rfloor}\{(-1)^l\cdot2^{n-2l-1}\cdot\binom{n-l-1}{l}\cos^{n-2l-1}{\theta}\sin\theta\}\ \ \ \cdots(\star\star).$$
(We can get $(\star)$ by induction about $n$. Also, we can get $(\star\star)$ by differentiating $(\star)$.)
Proof : Comparing the both sides of 
$$\cos{n\theta}+i\sin{n\theta}=(\cos\theta+i\sin\theta)^n=\sum_{k=0}^n\binom{n}{k}\cos^{n-k}\theta(i\sin)^k,$$
we get
$$\cos{n\theta}=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}\cos^{n-2k}{\theta}(\cos^2\theta-1)^k=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}\cos^{n-2k}{\theta}\cdot\sum_{l=0}^{k}\{\binom{k}{l}\cos^{2(k-l)}{\theta}\cdot(-1)^l\}=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\sum_{l=0}^{k}\{(-1)^l\cdot\binom{n}{2k}\cdot\binom{k}{l}\cdot\cos^{n-2l}{\theta}\}.$$
Hence, we know that the coefficient of $\cos^{n-2l}\theta$ is
$$\sum_{k=l}^{\lfloor\frac{n}{2}\rfloor}(-1)^l\cdot\binom{n}{2k}\cdot\binom{k}{l}.$$
On the other hand, $(\star)$ tells us that the coefficient of $\cos^{n-2l}\theta$ is
$$n\cdot(-1)^l\cdot2^{n-2l-1}\cdot\frac{\binom{n-l}{l}}{n-l}.$$
Hence, we get 
$$\sum_{k=l}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}\cdot\binom{k}{l}=n\cdot2^{n-2l-1}\cdot\frac{\binom{n-l}{l}}{n-l}$$
as desired. Now the proof is completed.
P.S. By the same argument about $\sin{n\theta}$, we can get
$$\sum_{j=k}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n}{2j+1}\cdot\binom{j}{k}=2^{n-2k-1}\binom{n-k-1}{k}$$
for $n\ge 2k+1$.
A: We will use induction to prove the identity (equivalent to the one given) that
1) $\displaystyle\sum_{j\ge0}\binom{n}{2j}\binom{j}{k}=2^{n-2k-1}\bigg[\binom{n-k}{k}+\binom{n-k-1}{k-1}\bigg]$ $\;\;$for $0\le k\le\frac{n}{2}$ and the identity
2) $\displaystyle\sum_{j\ge0}\binom{n}{2j+1}\binom{j}{k}=2^{n-2k-1}\binom{n-k-1}{k}$ $\;\;$for $0\le k\le\frac{n-1}{2}$.
If $n=1$, $k=0$ and both sides of both identities are 1;
so assume that both identities are valid for some $n\in\mathbb{N}$.
1) $\displaystyle\sum_{j\ge0}\binom{n+1}{2j}\binom{j}{k}=\sum_{j\ge0}\bigg[\binom{n}{2j}+\binom{n}{2j-1}\bigg]\binom{j}{k}=\sum_{j\ge0}\binom{n}{2j}\binom{j}{k}+\sum_{j\ge0}\binom{n}{2j-1}\binom{j}{k}$
$\;\;\;\displaystyle=\sum_{j\ge0}\binom{n}{2j}\binom{j}{k}+\sum_{l\ge0}\binom{n}{2l+1}\binom{l+1}{k}$
$\;\;\;\displaystyle=\sum_{j\ge0}\binom{n}{2j}\binom{j}{k}+\sum_{l\ge0}\binom{n}{2l+1}\bigg[\binom{l}{k}+\binom{l}{k-1}\bigg]$
$\;\;\;\displaystyle=\sum_{j\ge0}\binom{n}{2j}\binom{j}{k}+\sum_{l\ge0}\binom{n}{2l+1}\binom{l}{k}+\sum_{l\ge0}\binom{n}{2l+1}\binom{l}{k-1}$
$\;\;\;\displaystyle=2^{n-2k-1}\bigg[\binom{n-k}{k}+\binom{n-k-1}{k-1}\bigg]+2^{n-2k-1}\binom{n-k-1}{k}+2^{n-2k+1}\binom{n-k}{k-1}$
$\;\;\;\displaystyle=2^{n-2k-1}\bigg[\binom{n-k}{k}+\binom{n-k-1}{k-1}+\binom{n-k-1}{k}+4\binom{n-k}{k-1}\bigg]$
$\;\;\;\displaystyle=2^{n-2k-1}\bigg[\binom{n-k+1}{k}+\binom{n-k}{k}+\binom{n-k}{k-1}+2\binom{n-k}{k-1}\bigg]$
$\;\;\;\displaystyle=2^{n-2k-1}\bigg[2\binom{n-k+1}{k}+2\binom{n-k}{k-1}\bigg]=2^{n-2k}\bigg[\binom{n-k+1}{k}+\binom{n-k}{k-1}\bigg]$,
$\;\;\;\;$ so identity 1) holds for $n+1$.
2) $\displaystyle\sum_{j\ge0}\binom{n+1}{2j+1}\binom{j}{k}=\sum_{j\ge0}\bigg[\binom{n}{2j+1}+\binom{n}{2j}\bigg]\binom{j}{k}=\sum_{j\ge0}\binom{n}{2j+1}\binom{j}{k}+\sum_{j\ge0}\binom{n}{2j}\binom{j}{k}$
$\;\;\;\displaystyle=2^{n-2k-1}\binom{n-k-1}{k}+2^{n-2k-1}\bigg[\binom{n-k}{k}+\binom{n-k-1}{k-1}\bigg]$
$\;\;\;\displaystyle=2^{n-2k-1}\bigg[\binom{n-k}{k}+\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\bigg]=2^{n-2k-1}\bigg[\binom{n-k}{k}+\binom{n-k}{k}\bigg]$
$\;\;\;\displaystyle=2^{n-2k}\binom{n-k}{k}$, 
$\;\;\;$so identity 2) holds for $n+1$.
