Exercise 1.4.25* (Conundrum 7/8)

Question

Show that
$$\sum_{k=0}^{n+1} \left(\binom{n}{k} - \binom{n}{k-1}\right)^2 = \frac{2}{n+1}\binom{2n}{n}.$$

Richard Ganaye · Accepted Answer

\begin{proof} By brute force.

\begin{align*}
S &= \sum_{k=0}^{n+1} \left(\binom{n}{k} - \binom{n}{k-1}ight)^2 \
&= \sum_{k=0}^{n} \binom{n}{k}^2 +  \sum_{k=1}^{n+1} \binom{n}{k-1}^2  - 2  \sum_{k=1}^{n+1} \binom{n}{k}  \binom{n}{k-1}\
&=2U - 2V,
\end{align*}
where
$$U = \sum_{k=0}^{n} \binom{n}{k}^2 ,\qquad V = \sum_{k=1}^{n+1} \binom{n}{k}  \binom{n}{k-1}.$$
(because $ \sum_{k=1}^{n+1} \binom{n}{k-1}^2 =  \sum_{K=0}^{n} \binom{n}{K}^2 = U$.)

\medskip
By Vandermonde's formula (see Exercise 3),
$$U = \sum_{k=0}^{n} \binom{n}{k}^2 = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k} = \binom{2n}{n},$$
and
$$V =\sum_{k=1}^{n+1} \binom{n}{k}  \binom{n}{k-1} = \sum_{k=1}^{n+1} \binom{n}{k}  \binom{n}{n+1-k} = \binom{2n}{n+1}.$$
Moreover
$$\binom{2n}{n+1} = \frac{(2n)!}{(n+1)!(n-1)!} = \frac{(2n)!}{n!n!} \frac{n}{n+1} = \frac{n}{n+1} \binom{2n}{n}.$$
Therefore
\begin{align*}
\sum_{k=0}^{n+1} \left(\binom{n}{k} - \binom{n}{k-1}ight)^2 
&=2 \binom{2n}{n} \left( 1 - \frac{n}{n+1} ight)\
&= \frac{2}{n+1} \binom{2n}{n}.
\end{align*}
\end{proof}

Exercise 1.4.25* (Conundrum 7/8)

Answers

Comments

Exercise 1.4.25* (Conundrum 7/8)

Answers

Comments

Add answer