Maths Olympiad Prep

Library / /208 of 520

Combinatorics Difficulty 6.0 AIME, harder Prove it

Theorem 1.2. Let nn and kk be positive integers with n⩾kn \geqslant k. Then
(nk)+(nk−1)=(n+1k)\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}

Solution

Proof. We perform the addition
(nk)+(nk−1)=n!k!(n−k)!+n!(k−1)!(n−k+1)!\binom{n}{k}+\binom{n}{k-1}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}
by using the common denominator k!(n−k+1)k!(n-k+1) !. This gives
(nk)+(nk−1)=n!(n−k+1)k!(n−k+1)!+n!kk!(n−k+1)!=n!((n−k+1)+k)k!(n−k+1)!=n!(n+1)k!(n−k+1)!=(n+1)!k!(n−k+1)!=(n+1k)\begin{aligned} \binom{n}{k}+\binom{n}{k-1} & =\frac{n!(n-k+1)}{k!(n-k+1)!}+\frac{n!k}{k!(n-k+1)!} \\ & =\frac{n!((n-k+1)+k)}{k!(n-k+1)!} \\ & =\frac{n!(n+1)}{k!(n-k+1)!} \\ & =\frac{(n+1)!}{k!(n-k+1)!} \\ & =\binom{n+1}{k} \end{aligned}

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.