Show that the numerator of \[ \frac{2^{p-1}}{p+1} - \left(\sum_{k = 0}^{p-1}\frac{\binom{p-1}{k}}{(1-kp)^2}\right) \] is a multiple of $p^3$ for any odd prime $p$. Proposed by Yang Liu
Problem
Source: ELMO 2014 Shortlist N6, by Yang Liu
Tags: modular arithmetic, number theory proposed, number theory
25.07.2014 10:36
\begin{align*} \frac{2^{p-1}}{p+1}-\left(\sum_{k = 0}^{p-1}\frac{\binom{p-1}{k}}{(1-kp)^2}\right) &\equiv (p^2-p+1)\sum_{k=0}^{p-1}\binom{p-1}{k} - \sum_{k=0}^{p-1} \binom{p-1}{k} (k^2p^2+kp+1)^2 \\ &\equiv (p^2-p+1)\sum_{k=0}^{p-1} \binom{p-1}{k} - \sum_{k=0}^{p-1} \binom{p-1}{k} (3k^2p^2+2kp+1) \\ &\equiv (p^2-p)\sum_{k=0}^{p-1}\binom{p-1}{k} - \sum_{k=0}^{p-1}\binom{p-1}{k}(3k^2p^2+2kp) \pmod{p^3}\end{align*}. It suffices to show that $(p-1)\sum_{k=0}^{p-1}\binom{p-1}{k} - \sum_{k=0}^{p-1}\binom{p-1}{k}(3k^2p+2k) \equiv 0 \pmod{p^2}$. Now \begin{align*} \sum_{k=0}^{p-1} \binom{p-1}{k}k^2 &\equiv \sum_{k=0}^{p-1} (-1)^k k^2 \\ &\equiv \sum_{i=1}^{\frac{p-1}{2}} ((2i)^2 - (p-2i)^2)\\ &\equiv 0 \pmod{p} \end{align*} So we are done if we can show that $(p-1)\sum_{k=0}^{p-1}\binom{p-1}{k} - \sum_{k=0}^{p-1} 2k\binom{p-1}{k} \equiv 0 \pmod{p^2}$. In fact, this is identically $0$ as it all cancels out if we consider $k=l, k=(p-1)-l$.
21.09.2019 22:15
As an addendum, after noting that $\frac1{(1-kp)^2}=k^2p^2+kp+1,$ one can very blindly just push harder with the identities \[\sum_{k=0}^{p-1}\binom{p-1}kk=(p-1)\cdot2^{p-2}\]and
The second identity is similar.
09.03.2020 12:20
Nice! Here's my solution: We will use congruences on rationals, i.e. for $a,b \in \mathbb{Z}_p,$ we write $a \equiv b \pmod{p^e}$ iff $p^e$ divides the numerator of $a-b$ when written in simplest terms. Note that, by Binomial Theorem, we get $$\sum_{k=0}^{p-1} \frac{\binom{p-1}{k}}{(1-kp)^2}=\sum_{k=0}^{p-1} \binom{p-1}{k} \left(\sum_{i \geq 0} (i+1)(kp)^i \right) \equiv \sum_{k=0}^{p-1} \binom{p-1}{k}(1+2kp+3k^2p^2) \pmod{p^3}$$Now, from the identity $r\binom{n}{r}=n\binom{n-1}{r-1}$, we get $$\sum_{k=0}^{p-1} \binom{p-1}{k}=2^{p-1}$$$$\sum_{k=0}^{p-1} k\binom{p-1}{k}=\sum_{k=0}^{p-1} (p-1)\binom{p-2}{k-1}=(p-1)2^{p-2}$$$$\sum_{k=0}^{p-1} k^2\binom{p-1}{k}=\sum_{k=0}^{p-1} k(k-1)\binom{p-1}{k}+\sum_{k=0}^{p-1} k\binom{p-1}{k}=\sum_{k=0}^{p-1} (p-1)(p-2) \binom{p-3}{k-2}+\sum_{k=0}^{p-1} (p-1)\binom{p-2}{k-1}$$$$\Rightarrow \sum_{k=0}^{p-1} k^2\binom{p-1}{k}=(p-1)(p-2)2^{p-3}+(p-1)2^{p-2}=p(p-1)2^{p-3}$$Thus, we get $$\sum_{k=0}^{p-1} \frac{\binom{p-1}{k}}{(1-kp)^2} \equiv 2^{p-1}+2p(p-1)2^{p-2}+3p^3(p-1)2^{p-3} \equiv 2^{p-1}(p^2-p+1) \pmod{p^3}$$But, then we easily get the result by using the fact that $$(p+1)(p^2-p+1)=p^3+1 \equiv 1 \pmod{p^3} \Rightarrow 2^{p-1}(p^2-p+1) \equiv \frac{2^{p-1}}{p+1} \pmod{p^3} \text{ } \blacksquare$$