Let $k$ be a positive integer, $p>3$ a prime, and $n$ an integer with $0\le n\le p^{k-1}$. Prove that $\binom{p^k}{pn}\equiv\binom{p^{k-1}}n\pmod{p^{2k+1}}.$
This is CMO 2019 P2
$\binom{p^k}{pn}=\frac{p^k!}{pn!\cdot {(p^k-pn)}!}$
This problem is giving me Lucas vibes. We have $\binom{pa}{pb}\equiv \binom{a}{b}\mod p.$
We write $${p^k \choose pn}= \frac{p^k(p^k-1)\cdot\cdot (p^k-pn+1)}{(pn)!}={p^{k-1} \choose n}(1+Q_n).$$ and since, by Kummer theorem, the $p$-adic order $v$ of ${p^{k-1} \choose n}$ is $v\Big({p^{k-1} \choose n}\Big)=k-1 -v(n)$, we need to show that $v(Q_n) \ge k+2 + v(n)$.
When $n=1$ this is true, as $v(1)=0$ and $$ 1+Q_1 = \frac{(p^{k}-1)\cdot\cdot(p^{k}-p+1)}{(p-1)!} $$ then, expanding and keeping the lowest powers of $p$ only, with $H_{p-1}$ the $(p-1)^{\text{th}}$ Harmonic number, we have $$ 1+Q_1 = (-1)^{p-1} -(-1)^{p-1}p^k H_{p-1}+ \cdot\cdot $$ If $p\gt3$, by Wolstenholme's theorem $H_{p-1} \equiv 0 \bmod p^2$ and then $Q_1\equiv 0 \bmod p^{k+2}$ and then ${p^k \choose p}-{p^{k-1} \choose 1} \equiv 0 \bmod p^{2k+1}$.
Now, if $n\gt 1$, $$ 1+Q_n = \frac{\frac{p^k}{p^{k-1}}\frac{p^k-1}{p^{k-1}-1}\cdot\cdot \frac{p^k-n+1}{p^{k-1}-n+1}(p^{k}-n)\cdot\cdot(p^{k}-pn+1)}{{pn\choose n}((p-1)n)!} $$ $$ 1+Q_n = \frac{\frac{p^k-1}{p^{k-1}-1}\cdot\cdot \frac{p^k-n+1}{p^{k-1}-n+1}(p^{k}-n)\cdot\cdot(p^{k}-pn+1)}{{pn-1\choose n-1}((p-1)n)!} $$
$$ 1+Q_n = \frac{p^k-1}{p^{k-1}-1}\cdot\cdot \frac{p^k-n+1}{p^{k-1}-n+1}\frac{(p^{k}-n)\cdot\cdot(p^{k}-pn+1)}{(pn-1)(pn-2)\cdot\cdot (pn-(p-1)n-1)} $$ $$ 1+Q_n = \prod_{j=1}^{n-1}\frac{1-\frac{p^k}{j}}{1-\frac{p^{k-1}}{j}}\prod_{j=n}^{pn-1}\Big(\frac{p^k}{j}-1\Big)$$ but since $p\gt3$ is odd, we have $$ 1+Q_n = \prod_{j=1}^{n-1}\frac{1}{1-\frac{p^{k-1}}{j}}\prod_{j=1}^{pn-1}\Big(1-\frac{p^k}{j}\Big)$$ $$ 1+Q_n= (1+Q_{n-1})\frac{1}{1-\frac{p^{k-1}}{n-1}}\prod_{j=0}^{p-1}\Big(1-\frac{p^k}{p(n-1)+j}\Big) $$ $$ 1+Q_n= (1+Q_{n-1})\prod_{j=1}^{p-1}\Big(1-\frac{p^k}{p(n-1)+j}\Big)$$ $$ 1+Q_n= \prod_{h=1}^{n}\prod_{j=1}^{p-1}\Big(1-\frac{p^k}{ph-j}\Big)= \prod_{j=1}^{p-1}\prod_{h=1}^{n}\Big(1-\frac{p^k}{ph-j}\Big).$$ Then introducing the elementary symetric polynomials $e_h$, we have: $$1+Q_n=\prod_{j=1}^{p-1}\sum_{h=1}^{n}\Big(1+ (-1)^h e_h(\frac{p^k}{p-j},\cdot\cdot ,\frac{p^k}{pn-j})\Big)$$ $$1+Q_n=\prod_{j=1}^{p-1}\sum_{h=1}^{n}\Big(1+ (-1)^h p^{kh} e_h(\frac{1}{p-j},\cdot\cdot ,\frac{1}{pn-j})\Big).$$
We seek to show that $v(Q_n) \ge k+2 +v(n)$. Since $v(n) \le k-1$, $k+2+v(n)\le 2k+1$ and since $p$ does not divide $j$ the $e_h$ are $p$-integral, we may limit the expansion of $1+Q_n$ to $h=2$.
Then, $$1+Q_n=\prod_{j=1}^{p-1}\Big(1- p^{k} e_1(\frac{1}{p-j},\cdot\cdot ,\frac{1}{pn-j})+ p^{2k} e_2(\frac{1}{p-j},\cdot\cdot ,\frac{1}{pn-j})\Big) + \text{ terms of order } p^{3k} .$$ $$1+Q_n=\prod_{j=1}^{p-1}\Big(1+ p^{k} \sum_{h=1}^n\frac{1}{j-ph}+ p^{2k} \sum_{1\le h_1\le h_2\le n}\frac{1}{j-ph_1}\frac{1}{j-ph_2}\Big) + \text{ terms of order } p^{3k} .$$ $$1+Q_n=\prod_{j=1}^{p-1}\Big(1+ p^{k} \sum_{g \ge 0}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g+ p^{2k} \sum_{1\le h_1\le h_2\le n}\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_1^g\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_2^g\Big) + \text{ terms of order } p^{3k} .$$ Now we may discard the terms corresponding to $g \ge 1$ in the sums multiplied by $p^{2k}$, and then $$1+Q_n=\prod_{j=1}^{p-1}\Big(1+ p^{k} \sum_{g \ge 0}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g+ p^{2k}\frac{1}{j^2} {n\choose 2}\Big) + \text{ terms of order higher than } p^{2k} .$$
Then again introducing the first $e_j$, $j\le2$
$$ Q_n=p^k\sum_{j=1}^{p-1} \sum_{h=1}^{n}\sum_{g\ge 0}\frac{p^gh^g}{j^{g+1}}+p^{2k}{n\choose 2}\sum_{j=1}^{p-1}\frac{1}{j^2}+ p^{2k}\sum_{1\le j_1 \lt j_2 \le p-1}\sum_{g\ge 0}\frac{p^g\sum_{h=1}^{n}h^g}{j_1^{g+1}}\sum_{g\ge 0}\frac{p^g\sum_{h=1}^{n}h^g}{j_2^{g+1}} + \text{ terms of order higher than } p^{2k} . $$
$$ Q_n=p^k\sum_{j=1}^{p-1} \sum_{h=1}^{n}\sum_{g\ge 0}\frac{p^gh^g}{j^{g+1}}+p^{2k}{n\choose 2}\sum_{j=1}^{p-1}\frac{1}{j^2}+ p^{2k}n^2\sum_{1\le j_1 \lt j_2 \le p-1}\frac{1}{j_1j_2} + \text{ terms of order higher than } p^{2k} . $$
$$ Q_n=p^k\sum_{j=1}^{p-1} \sum_{h=1}^{n}\sum_{g\ge 0}\frac{p^gh^g}{j^{g+1}}+p^{2k}{n\choose 2}\sum_{j=1}^{p-1}\frac{1}{j^2}+ p^{2k}n^2\frac{\Big(\sum_{j=1}^{p-1}\frac{1}{j}\Big)^2-\sum_{j=1}^{p-1}\frac{1}{j^2}}{2} + \text{ terms of order higher than } p^{2k} . $$
$$ Q_n= \sum_{g\ge 0}p^{g+k} H_{p-1}^{(g+1)} \sum_{h=1}^{n}h^g +p^{2k}{n\choose 2}H_{p-1}^{(2)}+ p^{2k}n^2\frac{H_{p-1}^2-H_{p-1}^{(2)}}{2}+ \text{ terms of order higher than } p^{2k} . $$ where $H_{p-1}^{(g+1)}=\sum_{j=1}^{p-1}\frac{1}{j^{g+1}}$ is the generalized Harmonic number.
But $H_{p-1} \equiv 0 \bmod p$ and also,by Wolstenholmes theorem, when $p\gt 3$, we have $ H_{p-1}^{(2)} \equiv 0 \bmod p $ and then
$$ Q_n= \sum_{g\ge 0}p^{g+k} H_{p-1}^{(g+1)} \sum_{h=1}^{n}h^g + \text{ terms of order higher than } p^{2k} . $$
On the other hand, we know that $\sum_{h=1}^{n}h^g \equiv 0 \bmod {n+1\choose 2}$ when $g$ is odd (see this post) and that $\sum_{h=1}^{n}h^g \equiv 0 \bmod \frac{n}{\mathbb{rad}n}$ when $g$ positive is even (see the appendix in this post).
Then $v\Big( \sum_{h=1}^{n}h^g\Big) \ge v(n)$ or $v(n)-1$ when $g\gt0$ is odd or even, respectively. Also it is easily seen that $H_{p-1}^{(g)} \equiv 0 \bmod p$ when $g$ is odd. Then $v\Big( H_{p-1}^{(g+1)} \sum_{h=1}^{n}h^g\Big) \ge v(n)$ for all $g \ge 0$.
$$ Q_n= p^{k} H_{p-1}n + p^{k+1}H_{p-1}^{(2)}\frac{n(n+1)}{2} +\sum_{g\ge 2}p^{g+k} H_{p-1}^{(g+1)} \Big( \sum_{h=1}^{n}h^g \Big)+ \text{ terms of order higher than } p^{2k} . $$
and then, again with Wolstenholme's theorem when $p \gt3$, $H_{p-1} \equiv 0 \bmod p^2 $ and $H_{p-1}^{(2)} \equiv 0 \bmod p $, we have $$ v(Q_n) \ge k+2 +v(n)$$
and then, when $p \gt 3$ $$ {p^k \choose n\cdot p} - {p^{k-1} \choose n} \equiv 0 \bmod p^{2k+1}. $$
With expansions at higher orders in the above derivations, one should be able to obtain the stronger $$ v(Q_n) \ge k+2 +2v(n)$$ and $$ {p^k \choose n\cdot p} - {p^{k-1} \choose n} \equiv 0 \bmod p^{2k+1+v(n)} $$ as stated in @Merosity answer.
If we allow ourselves to start with the strong result from p-adic considerations; the Kazandzidis congruence for $p>3$,
$$\binom{pn}{pk} \equiv \binom{n}{k} \mod p^3nk(n-k) \binom{n}{k} \mathbb{Z}_p$$
Here $\mathbb{Z}_p$ is the p-adic integers.
We can make the appropriate substitutions for our problem to get to,
$$\binom{p^k}{pn} \equiv \binom{p^{k-1}}{n} \mod p^{k+2}n(p^{k-1}-n) \binom{p^{k-1}}{n} \mathbb{Z}_p$$
On its own this is not enough, we need to refine this by focusing on the power of $p$ dividing the binomial term. I think there's a better way of doing this than how I'm about to do it, but this works. We can look at it through Legendre's formula/Kummer's theorem which says the p-adic valuation of the binomial coefficient is related to sums of digits of some numbers when written in base $p$,
$$v_p\left(\binom{a}{b}\right) = \frac{s_p(b)+s_p(a-b)-s_p(a)}{p-1}$$
In our case,
$$v_p\left(\binom{p^{k-1}}{n}\right) = \frac{s_p(n)+s_p(p^{k-1}-n)-s_p(p^{k-1})}{p-1}$$
We can do a few simplifications, immediately $s_p(p^{k-1})=1$ and we can use the fact that $p^{k-1}-1$ has exactly $k-1$ digits that are $p-1$ to rewrite: $s_p(p^{k-1}-n) = s_p(p^{k-1}-1-(n-1)) = (p-1)(k-1) - s_p(n-1)$,
$$v_p\left(\binom{p^{k-1}}{n}\right) = \frac{s_p(n)+(p-1)(k-1) - s_p(n-1)-1}{p-1}$$
$$v_p\left(\binom{p^{k-1}}{n}\right) = k-1 + \frac{s_p(n) - s_p(n-1)-1}{p-1}$$
The last term can be simplified with Legendre's formula in reverse,
$$v_p\left(\binom{p^{k-1}}{n}\right) = k-1 + v_p((n-1)!)-v_p(n!)$$
$$v_p\left(\binom{p^{k-1}}{n}\right) = k-1 - v_p(n)$$
This is much more promising, let's put this back in our formula and amend it by putting $n=p^{v_p(n)}m$ (here $v_p(m)=0$) everywhere along with $\binom{p^{k-1}}{n} = p^{k-1-v_p(n)}u$
$$\binom{p^k}{pn} \equiv \binom{p^{k-1}}{n} \mod p^{k+2}p^{v_p(n)}m(p^{k-1}-p^{v_p(n)}m) p^{k-1-v_p(n)}u \mathbb{Z}_p$$
$$\binom{p^k}{pn} \equiv \binom{p^{k-1}}{n} \mod p^{2k+1}(p^{k-1}-p^{v_p(n)}m)\mathbb{Z}_p$$
The $m$ and $u$ terms are units in $\mathbb{Z}_p$ and so are safely removed. What we have here is actually a bit more general than the problem asks, so we can discard the extra $p^{k-1}-p^{v_p(n)}m$ term if we like, which gives us a higher power of $p$ that this congruence holds in the case that $n$ is divisible by a power of $p$.
Here is a proof that $$ v(Q_n) \ge k+2 +2v(n).$$ In the expansion of $1+Q_n$ we may still discard the terms with powers higher than or equal to $3k$ since $k+2+2v(n)\le k+2 +2(k-1)=3k$.
Then, starting from $(*)$ in the previous answer, $\bmod {p^{3k}}$ we have $$1+Q_n \equiv \prod_{j=1}^{p-1}\Big(1+ p^{k} \sum_{g \ge 0}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g+ p^{2k} \sum_{1\le h_1\le h_2\le n}\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_1^g\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_2^g\Big) .$$ We may also limit the expansion in symetric polynomials $e_j$ to $j\le2$ since obviously $e_j$ is divisible by $p^{3k}$, for $j \ge 3$.
Moreover, with $x_j=p^{k} \sum_{g \ge 0}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g+ p^{2k} \sum_{1\le h_1\le h_2\le n}\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_1^g\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_2^g$, we clearly have
$$e_2(x_1,\cdot\cdot, x_{p-1}) \equiv p^{2k}\sum_{1\le j_1 \lt j_2 \le p-1}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g}{j_1^{g+1}}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g }{j_2^{g+1}} \pmod {p^{3k}}$$
Then, $\bmod p^{3k}$, we have
$$Q_n \equiv \sum_{j=1}^{p-1}\Big(p^{k} \sum_{g \ge 0}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g+ p^{2k} \sum_{1\le h_1\le h_2\le n}\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_1^g\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_2^g\Big)+p^{2k}\sum_{1\le j_1 \lt j_2 \le p-1}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g}{j_1^{g+1}}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g }{j_2^{g+1}} .$$
$$Q_n \equiv \sum_{j=1}^{p-1}\Big(p^{k} \sum_{g \ge 0}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g+ p^{2k} \sum_{1\le h_1\le h_2\le n}\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_1^g\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h_2^g\Big) +\frac{p^{2k}}{2}\Big(\sum_{j=1}^{p-1}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g}{j^{g+1}} \Big)^2-\frac{p^{2k}}{2}\sum_{j=1}^{p-1}\Big(\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g }{j^{g+1}}\Big)^2 .$$
$$Q_n \equiv p^{k} \sum_{g \ge 0}\sum_{j=1}^{p-1}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g +\frac{p^{2k}}{2}\sum_{j=1}^{p-1} \Big(\sum_{1\le h\le n}\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h^g\Big)^2 - \frac{p^{2k}}{2}\sum_{j=1}^{p-1}\sum_{1\le h\le n}\Big(\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h^{g}\Big)^2 +\frac{p^{2k}}{2}\Big(\sum_{j=1}^{p-1}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g}{j^{g+1}} \Big)^2 -\frac{p^{2k}}{2}\sum_{j=1}^{p-1}\Big(\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g }{j^{g+1}} \Big)^2 .$$
$$Q_n \equiv p^{k} \sum_{g \ge 0}\sum_{j=1}^{p-1}\frac{p^g}{j^{g+1}}\sum_{h=1}^nh^g - \frac{p^{2k}}{2}\sum_{j=1}^{p-1}\sum_{1\le h\le n}\Big(\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h^{g}\Big)^2 +\frac{p^{2k}}{2}\Big(\sum_{j=1}^{p-1}\sum_{g \ge 0}\frac{p^g\sum_{h=1}^nh^g}{j^{g+1}} \Big)^2 .$$
$$Q_n \equiv p^{k} \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g - \frac{p^{2k}}{2}\sum_{j=1}^{p-1}\sum_{1\le h\le n}\Big(\sum_{g \ge 0}\frac{p^g}{j^{g+1}}h^{g}\Big)^2 +\frac{p^{2k}}{2}\Big(\sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g \Big)^2 .$$
$$Q_n \equiv p^{k} \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g - \frac{p^{2k}}{2}\sum_{j=1}^{p-1}\sum_{1\le h\le n}\sum_{g \ge 0}(g+1)(-1)^g\frac{p^g}{j^{g+1}}h^{g} +\frac{p^{2k}}{2}\Big(\sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g \Big)^2 .$$ $$Q_n \equiv p^{k} \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g - \frac{p^{2k}}{2}\sum_{g \ge 0}(g+1)(-p)^g H_{p-1}^{(g+1)}\sum_{1\le h\le n}h^{g} +\frac{p^{2k}}{2}\Big(\sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g \Big)^2 \pmod {p^{3k}} .$$
$$Q_n \equiv p^{k} \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g - \frac{p^{2k}}{2}nH_{p-1} - \frac{p^{2k+1}}{2}\sum_{g \ge 1}(g+1)(-p)^{g-1} H_{p-1}^{(g+1)}\sum_{1\le h\le n}h^{g} +\frac{p^{2k}}{2}\Big(\sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g \Big)^2 \pmod {p^{3k}} .$$
Now, recall that $ k-1 \ge v(n)$ and that for all $g \ge 0$, $H_{p-1}^{(g+1)}\sum_{h=1}^nh^g \equiv 0 \bmod p^{v(n)}$, so that the last three terms on the right-hand-side are zero $\bmod p^{k+2+2v(n)}$ and then
$$Q_n \equiv p^{k} \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}\sum_{h=1}^nh^g \pmod {p^{k+2 +2v(n)}} .$$
To finish the proof, we make use of the well-known expression of the sum of consecutive powers involving the Bernoulli numbers $B_h$ whereby
$$\sum_{h=1}^nh^g= \frac{1}{g+1}\sum_{h=1}^{g+1} {g+1 \choose h}(-1)^{g+1-h} B_{g+1-h} n^{h}$$ $$\sum_{h=1}^nh^g= (-1)^gB_g n + \sum_{h=2}^{g+1} {g \choose h-1} (-1)^{g+1-h}B_{g+1-h} \frac{n^{h}}{h}$$
then
$$Q_n \equiv p^{k}n \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}(-1)^g B_g + p^{k}\sum_{g \ge 1}p^gH_{p-1}^{(g+1)}\sum_{h=2}^{g+1} {g \choose h-1} (-1)^{g+1-h}B_{g+1-h} \frac{n^{h}}{h} \pmod {p^{k+2 +2v(n)}} .$$ $$Q_n \equiv p^{k}n \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}(-1)^gB_g +p^{k+1}H_{p-1}^{(2)}\frac{n^2}{2}+ p^{k+2}\sum_{g \ge 2}p^{g-2}H_{p-1}^{(g+1)}\sum_{h=2}^{g+1} {g \choose h-1} (-1)^{g+1-h}B_{g+1-h} \frac{n^{h}}{h} \pmod {p^{k+2 +2v(n)}} .$$
By Wolstenholme's theorem, when $p\gt 3$, $H_{p-1}^{(2)} \equiv 0 \bmod p$. We also have $v ( \frac{n^h}{h}) \ge 2 v(n)$ when $h \ge 2$ and $ H_{p-1}^{(g+1)}B_{g+1-h} $ is $p$-integral since $v(H_{p-1}^{(g+1)}) \ge 1$ and $v(B_{g+1-h}) \ge -1$ , by the Von Staudt-Clausen theorem.
Then we are left with
$$Q_n \equiv p^{k}n \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}(-1)^gB_g \pmod {p^{k+2 +2v(n)}} .$$
But it is known that $ \sum_{g \ge 0}p^gH_{p-1}^{(g+1)}(-1)^gB_g = 0 $, ($p$-adically) see here an elementary (but somewhat lengthy) proof.
Then, when $p \gt 3$ $$Q_n \equiv 0 \pmod {p^{k+2 +2v(n)}} $$ and then, when $p \gt 3$ $$ {p^k \choose n\cdot p} - {p^{k-1} \choose n} \equiv 0 \bmod p^{2k+1+v(n)}. $$
