Proving a formula about binomial coefficients

Question

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?

Answer 1

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$.

Answer 2

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$.