145. Una congruenza combinatorica

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

145. Una congruenza combinatorica

Messaggio da Karl Zsigmondy » 08 feb 2013, 19:50

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} $
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Re: 145. Una congruenza combinatorica

Messaggio da Leonida » 10 feb 2013, 21:22

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! :D Aspetto conferme/smentite!
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: 145. Una congruenza combinatorica

Messaggio da Karl Zsigmondy » 11 feb 2013, 14:47

Sono contento che ti sia piaciuto! :D Vai col prossimo...
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: 145. Una congruenza combinatorica

Messaggio da Hawk » 11 feb 2013, 21:22

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 $?
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »

Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Re: 145. Una congruenza combinatorica

Messaggio da Leonida » 11 feb 2013, 21:55

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$.
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"

Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: 145. Una congruenza combinatorica

Messaggio da Hawk » 11 feb 2013, 22:56

Sì, grazie per il chiarimento.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »

Rispondi