Maths Olympiad Prep

Library / /5 of 12

Combinatorics Difficulty 5.2 AIME, harder Prove it Bulgaria

Do there exist positive integers nn and kk, 1kn21 \le k \le n-2, such that
(nk)2+(nk+1)2=(nk+2)4? \binom{n}{k}^2 + \binom{n}{k+1}^2 = \binom{n}{k+2}^4 ?

Solution

By applying the formula (ab)=a!b!(ab)!\binom{a}{b} = \frac{a!}{b!(a-b)!} we obtain the equation
1+(nk)2(k+1)2=(nk)2(nk1)2(k+1)2(k+2)2(nk+2)2. 1 + \frac{(n-k)^2}{(k+1)^2} = \frac{(n-k)^2(n-k-1)^2}{(k+1)^2(k+2)^2} \binom{n}{k+2}^2.
Hence (k+2)2[(k+1)2+(nk)2]=(nk)2(nk1)2(nk+2)2(k+2)^2 [(k+1)^2 + (n-k)^2] = (n-k)^2(n-k-1)^2 \binom{n}{k+2}^2, which implies that (k+1)2+(nk)2(k+1)^2 + (n-k)^2 is a perfect square.
Let (k+1)2+(nk)2=t2(k+1)^2 + (n-k)^2 = t^2, where tNt \in \mathbb{N}. We have
(k+2)t=(nk)(nk1)(nk+2)2(nk+2). (k+2)t = (n-k)(n-k-1) \binom{n}{k+2} \ge 2 \binom{n}{k+2}.
Using that k+2nk+2 \le n and t=(k+1)2+(nk)2<n+1t = \sqrt{(k+1)^2 + (n-k)^2} < n+1 we conclude that (k+2)tn2(k+2)t \le n^2.
Let 3k+2n33 \le k+2 \le n-3 (the left hand side of this inequality follows from the condition of the problem). If n6n \ge 6, we have
2(nk+2)2(n3)=n(n1)(n2)3>n2, 2 \binom{n}{k+2} \ge 2 \binom{n}{3} = \frac{n(n-1)(n-2)}{3} > n^2,
i.e. the equation has no solution in this case.
When k+2=n2k+2 = n-2 we obtain t2=(n3)2+16t^2 = (n-3)^2 + 16, hence t=5t = 5, n=6n = 6, k=2k = 2. Direct computation shows that n=6n = 6 and k=2k = 2 is not a solution. If k+2=n1k+2 = n-1 we have t2=(n2)2+9t^2 = (n-2)^2 + 9, so t=5t = 5, n=6n = 6, k=3k = 3 and as above we conclude that no solution exists. Therefore positive integers nn and kk satisfying the equation do not exist.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.