Maths Olympiad Prep

Track / Stage 5 / 104 of 400 #1184 of 2444

Problem 1184

AIME late
Combinatorics Difficulty 5.2 Prove it Bulgaria competition problems · 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 ?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

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