Exercise 1.19

Question

Give a story proof that
$$
\sum_{k=2}^{n}\left(\begin{array}{l}
k \
2
\end{array}ight)\left(\begin{array}{c}
n-k+2 \
2
\end{array}ight)=\left(\begin{array}{c}
n+3 \
5
\end{array}ight)
$$
for all integers $n \geq 2$.

fifthist x · Accepted Answer

Since the subsets have size $5$, a middle element can range from $3$ to $n+1$. 
Let us label middle elements as $k+1$. Then, there are ${k \choose 2}$ choises 
of elements for the left half of a subset and 
${n+3-(k+1) \choose 2} = {n+2-k \choose 2}$ choices for the right half.

Taking the sum as $k+1$ ranges from $3$ to $n+1$, we get the desired result.

Exercise 1.19

Answers

Comments

Exercise 1.19

Answers

Comments

Add answer