Prove the statement $\binom{n}{3k+1}=\sum_{i=k+1}^{n-2k}{\binom{i-1}{k}}{\binom{n-i}{2k}}$using combinatorial arguments:

Question

Prove the following statement using combinatorial arguments:

For all $n,k\in\mathbb{N} $ such that $3k+1\le n$: $\binom{n}{3k+1}=\sum_{i=k+1}^{n-2k}{\binom{i-1}{k}}{\binom{n-i}{2k}}$

Hey everyone. I've been thinking about this for a while and I'm lost. I don't even know how to begin. Would be happy to get some help. Thanks in advance :)

Answer 1

Hint: The left-hand side counts the number of ways $3k + 1$ elements can be selected from the set $\{1, 2, 3, \ldots, n\}$. The right-hand side counts the number of selections in which the $(k + 1)$st smallest element is $i$. To see this, count how many ways you can select $k$ elements that are smaller than $i$ and $2k$ elements that are larger than $i$.