Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
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$.
