AIME II 2022 (Problem 10)CombinatoricsMediumFind the remainder when ((32)2)+((42)2)+⋯+((402)2)\binom{\binom{3}{2}}{2}+\binom{\binom{4}{2}}{2}+\cdots+\binom{\binom{40}{2}}{2}(2(23))+(2(24))+⋯+(2(240)) is divided by 100010001000.Related TopicsCoreCombinatorial IdentitiesMinorAlgebraic IdentitiesCheck AnswerYour answer:CheckHints (7)Hint 1((k2)2)=(k2)((k2)−1)2\binom{\binom{k}{2}}{2}=\frac{\binom{k}{2}\left(\binom{k}{2}-1\right)}{2}(2(2k))=2(2k)((2k)−1)=k(k−1)2(k(k−1)2−1)2=\frac{\frac{k(k-1)}{2}\left(\frac{k(k-1)}{2}-1\right)}{2}=22k(k−1)(2k(k−1)−1)Hint 2k(k−1)2(k(k−1)2−1)2\frac{\frac{k(k-1)}{2}\left(\frac{k(k-1)}{2}-1\right)}{2}22k(k−1)(2k(k−1)−1)=k(k−1)2(k2−k−22)2=\frac{\frac{k(k-1)}{2}\left(\frac{k^2-k-2}{2}\right)}{2}=22k(k−1)(2k2−k−2)Hint 3k(k−1)2(k2−k−22)2\frac{\frac{k(k-1)}{2}\left(\frac{k^2-k-2}{2}\right)}{2}22k(k−1)(2k2−k−2)=k(k−1)(k−2)(k+1)8=\frac{k(k-1)(k-2)(k+1)}{8}=8k(k−1)(k−2)(k+1)=3⋅(k+1)k(k−1)(k−2)4!=3\cdot\frac{(k+1)k(k-1)(k-2)}{4!}=3⋅4!(k+1)k(k−1)(k−2)=3(k+14)=3\binom{k+1}{4}=3(4k+1)Hint 4By Hint 3,((32)2)+((42)2)+⋯+((402)2)\binom{\binom{3}{2}}{2}+\binom{\binom{4}{2}}{2}+\cdots+\binom{\binom{40}{2}}{2}(2(23))+(2(24))+⋯+(2(240))=3(44)+3(54)+⋯+3(414)=3\binom{4}{4}+3\binom{5}{4}+\cdots+3\binom{41}{4}=3(44)+3(45)+⋯+3(441)By Hockey Stick Identity,3(44)+3(54)+⋯+3(414)=3(425)3\binom{4}{4}+3\binom{5}{4}+\cdots+3\binom{41}{4}=3\binom{42}{5}3(44)+3(45)+⋯+3(441)=3(542)Hint 53(425)=3⋅42⋅41⋅40⋅39⋅385⋅4⋅3⋅23\binom{42}{5}=3\cdot\frac{42\cdot41\cdot40\cdot39\cdot38}{5\cdot4\cdot3\cdot2}3(542)=3⋅5⋅4⋅3⋅242⋅41⋅40⋅39⋅38=42⋅41⋅39⋅38=42\cdot41\cdot39\cdot38=42⋅41⋅39⋅38=(40+2)(40+1)(40−1)(40−2)=(40+2)(40+1)(40-1)(40-2)=(40+2)(40+1)(40−1)(40−2)Hint 6By Difference of squares,(40+2)(40+1)(40−1)(40−2)(40+2)(40+1)(40-1)(40-2)(40+2)(40+1)(40−1)(40−2)=(40+2)(40−2)(40+1)(40−1)=(40+2)(40-2)(40+1)(40-1)=(40+2)(40−2)(40+1)(40−1)=(402−22)(402−12)=(40^2-2^2)(40^2-1^2)=(402−22)(402−12)=(1600−4)(1600−1)=(1600-4)(1600-1)=(1600−4)(1600−1)Hint 7(1600−4)(1600−1)(1600-4)(1600-1)(1600−4)(1600−1)=16002−5⋅1600+4=1600^2-5\cdot1600+4=16002−5⋅1600+4≡4(mod1000)\equiv4\pmod{1000}≡4(mod1000)Final Answer004004004Related Problems (1)MathCounts 2025 Chapter — Sprint Round (Problem 27)