New Year 2023. No.2

[rsoldo]

Let $B_n^k$ be the coefficients in the polynomial expansion $\left(1+x+x^2\right)^n=\sum_{k=0}^{2n}B_n^k x^k.$ Prove that for all prime number $p$, $s<p, r<p$ hold:

$$B_{mp+r}^{lp+s}\equiv \left(B_m^l\cdot B_r^s+B_m^{l-1}\cdot B_r^{s+p}\right)\pmod p.$$

[rsoldo]

This is one old Problem from Kvant ( No 4 from 1972. ). I think it is useful to prove first:

$$B_n^k=B_n^{2n-k}.$$

[rsoldo]

My solution:
We use two facts:

$$X^n-Y^n=(X-Y)\cdot (X^{n-1}+X^{n-2}\cdot Y+...+X\cdot Y^{n-2}+X^{n-1}),$$

if $m$ and $n$ are relatively prime numbers then $n\mid \binom{n}{m}.$
Now, it's obiviously

$$p\mid (X+Y)^p-(X^p+Y^p),$$

so it's

$$p\mid \left((1+x)+x^2\right)^p-\left((1+x)^p+x^{2p}\right).$$

But, $p\mid \sum_{k=2}^{p-1} \binom{p}{k} x^k$ so we can write

$$p\mid (1+x+x^2)^p-(1+x^p+x^{2p}).$$

We define

$$P(x)=(1+x+x^2)^{mp+r}-(1+x+x^2)^r\cdot (1+x^p+x^{2p})^n$$

$$=(1+x+x^2)^r\cdot \left[(1+x+x^2)^{mp}-(1+x^p+x^{2p})^m \right]$$

$$=(1+x+x^2)^r\cdot \left[(1+x+x^2)^p-(1+x^p+x^{2p})\right]\cdot\left[(1+x+x^2)^{p(n-1)}+\cdots+(1+x^p+x^{2p})^{n-1}\right]$$

$$\Rightarrow p\mid P(x).$$

Now we look at the coefficient with $x^{lp+s}$ in the development of the expression:
1) $B_{mp+r}^{lp+s}$ is coefficient in $(1+x+x^2)^{mp+r};$
2)

$$(1+x+x^2)^r\cdot (1+x^p+x^{2p})^n=(1+B_r^1 x+B_r^2 x^2+\cdots+\boxed{B_r^sx^s}+\cdots+\boxed{B_r^{s+p} x^{s+p}}+ \cdots+x^{2r})$$ $$\cdot(1+B_m^1 x^p+B_m^2 x^{2p}+\cdots+\boxed{B_m^{l-1}x^{(l-1)p}}+\boxed{B_m^lx^{lp}}+\cdots+x^{2pm})$$

By multiplication marked expression give the coefficient with $x^{lp+s}$ and it is $B_m^l\cdot B_r^s+B_m^{l-1}\cdot B_r^{s+p}$$\blacksquare$