Maths Olympiad Prep

Library / Problems of Ukrainian Authors /11 of 40

Problems of Ukrainian Authors

Combinatorics Difficulty 5.2 AIME, harder Prove it Ukraine

Prove for any positive integer nn:
∑k=0n−1((n−1k))2k+1=(2n−1n)2n \sum_{k=0}^{n-1} \frac{\left(\binom{n-1}{k}\right)^2}{k+1} = \frac{\binom{2n-1}{n}}{2n}

Solution

Since n(n−1k)k+1=n(n−1)!(k+1)k!(n−k−1)!=n!k!(n−k−1)!=(nk+1)\frac{n \binom{n-1}{k}}{k+1} = \frac{n(n-1)!}{(k+1)k!(n-k-1)!} = \frac{n!}{k!(n-k-1)!} = \binom{n}{k+1}, the left-hand-side sum takes the form
∑k=0n−1(n−1k)(nk+1)=∑k=0n−1(n−1k)(nn−k−1)=(2n−1n). \sum_{k=0}^{n-1} \binom{n-1}{k} \binom{n}{k+1} = \sum_{k=0}^{n-1} \binom{n-1}{k} \binom{n}{n-k-1} = \binom{2n-1}{n}.
The latter equality follows from the properties of binomial coefficients. On the other hand,
(2nn)=(2n−1n−1)+(2n−1n)=2(2n−1n−1), \binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n} = 2\binom{2n-1}{n-1},
which finishes the proof.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.