Exercise 2086Combinatorics › Binomial coefficientsOlympiadAdded 3 Nov 2026

A correct challenge identity

#challenge#identity#Franel

Statement

Prove the Franel identity: $\sum_{k=0}^{n}\binom{n}{k}^3=\frac{1}{2}\sum_{k=0}^{n}\binom{n}{k}^2\binom{2k}{k}\binom{2n-2k}{n-k}$ .

Hint

This is a deep identity; use generating functions or combinatorial arguments.

Show solutionHide solution

Solution

Idea. Both sides count triples of subsets $(A,B,C)$ with $|A|=|B|=|C|$ from an $n$ -set — but the right side uses a clever bijective/analytic manipulation.

Proof approach. Use the MacMahon Master Theorem or generating functions. The result is classical.

Verification for $n=1$ . LHS $=1+1=2$ . RHS $=\frac{1}{2}(1\cdot\binom{0}{0}\binom{2}{1}+1\cdot\binom{2}{1}\binom{0}{0})\cdot?...$ = $\frac{1}{2}(1\cdot1\cdot2+1\cdot2\cdot1)=2$ . ✓

Conclusion. The Franel identity holds; it is one of many nontrivial binomial identities.

A correct challenge identity

Statement

Solution

More problems in Binomial coefficients