145. Una congruenza combinatorica

[Karl Zsigmondy]

Dato p primo dispari, mostrare che vale:
$ \displaystyle \sum_{j=0}^{p}{\binom{p}{j} \binom{p+j}{j}} \equiv 2^p + 1 \pmod{p^2} $

[Leonida]

Lemma 1: se $j <p$, vale $\displaystyle {p \choose j} {{p+j} \choose j} \equiv {p \choose j} \pmod {p^2}$.
Dim.: per $j=0$ si verifica essere vero. Altrimenti, semplifico dai due membri della congruenza $\displaystyle {p \choose j}$, a patto di passare da modulo $p^2$ a modulo $p$: questo perchè $\displaystyle v_p {p \choose j} =1$. La congruenza diventa: $\displaystyle {{p+j} \choose j} \equiv 1 \pmod {p}$, vera in quanto $\displaystyle {{p+j} \choose j} = \frac{(p+j)(p+j-1)\cdot ... \cdot(p+1)}{j(j-1) \cdot... \cdot 1} \equiv \frac{j!}{j!} \equiv 1 \pmod {p}$.
Lemma 2: $\displaystyle {2p \choose p} \equiv 2 \pmod {p^2}$.
Dim.: è noto che $\displaystyle {2p \choose p} = \sum_{i=0}^{p} {p \choose i}^2$. Ora tutti i binomiali presenti nella sommatoria, eccetto il primo e l'ultimo, sono multipli di $p$, quindi il loro quadrato è multiplo di $p^2$. Segue che $\displaystyle {2p \choose p} = \sum_{i=0}^{p} {p \choose i}^2 \equiv {p \choose 0}^2 + {p \choose p}^2 \equiv 2 \pmod {p^2}$, che è il lemma.
E' noto inoltre che $\displaystyle \sum_{j=0}^{p} {p \choose j} = 2^p$. Per questi fatti, detta $S$ la sommatoria del testo, vale $\displaystyle S \equiv {p \choose p}{2p \choose p} + \sum_{j=0}^{p-1} {p \choose j} \equiv 1 \cdot 2 + 2^p - {p \choose p} = 2 +2^p -1 = 2^p +1 \pmod {p^2}$, che è la tesi.

Problema simpatico! Aspetto conferme/smentite!

[Karl Zsigmondy]

Sono contento che ti sia piaciuto! Vai col prossimo...

[Hawk]

Scusate se mi intrometto ma non ho capito una cosa. Sappiamo che è vero che $ p \mid \dbinom{p}{j} $ con $ 1<j<p $. Ma se così fosse come faccio a semplificare nella congruenza? Verrebbe: $ \displaystyle {p \choose j} {{p+j} \choose j} \equiv {p \choose j} \equiv 0 \pmod{p} $, per semplificare il termine, cioè per dividere nella congruenze, non dovrebbe valere $ gcd\left(\dbinom{p}{j},p\right)=1 $?

[Leonida]

Se ho capito il tuo dubbio, la congruenza originale era modulo $p^2$: proprio perchè $\displaystyle \gcd \left({p \choose j}, p^2 \right) = p$, ho semplificato un fattore $p$ dalla congruenza, passando da modulo $p^2$ a modulo $p$.

[Hawk]

Sì, grazie per il chiarimento.