5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you tried Gosper's algorithm? $\endgroup$ – Peter Taylor Sep 16 '13 at 16:02
  • $\begingroup$ @PeterTaylor: Sorry, but I don't know it. $\endgroup$ – mathlove Sep 16 '13 at 16:13
  • $\begingroup$ I am facing a very similar problem!, see this answer of mine to a certain question relating Hermite and Legendre polynomials. At the end I struggled (without success so far) with a sum of the same kind as the one above. $\endgroup$ – Matemáticos Chibchas Sep 21 '13 at 4:52
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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