<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-12-07 01:38, lordgauss wrote:
<BR>Sia dato un primo p > 3. Definiamo la sequenza a[n] come:
<BR>a[n] = n per n=0,1,...,p-1
<BR>a[n] = a[n-1] + a[n-p] per n > p-1
<BR>Determinare il resto di a[p³] modulo p.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Scrivo qui la mia soluzione del problema, come monito a chi mi accusa gratuitamente di \"non masticare la matematica\", per poi partorire una dimostrazione orripilante, oltre che sbagliata, di questo stesso problema.
<BR>[D\'ora in poi indichero\' con {a<sub>n</sub>} la successione dei resti modulo p (e non la successione originaria), e con = indichero\' la congruenza modulo p.]
<BR>
<BR>
<BR>- Notiamo che {a<sub>n</sub>} e\' periodica, in quanto il termine generico a<sub>n</sub> dipende solo da a<sub>n-1</sub> e da a<sub>n-p</sub>. Dunque, partizionando la successione in \"stringhe\" disgiunte di p elementi consecutivi, e\' sufficiente che 2 stringhe siano uguali affinche\' {a<sub>n</sub>} sia periodica. Ma siccome esistono solo p<sup>p</sup> stringhe distinte, per il principio dei cassetti ne esisteranno due uguali fra le prime p<sup>p</sup>+1.
<BR>
<BR>- Oltre ad essere periodica, {a<sub>n</sub>} non ha antiperiodo. Per convincersene, basta verificare che {a<sub>n</sub>} puo\' essere estesa in modo unico anche \"all\'indietro\" (sempre rispettando la regola che a<sub>n</sub> = a<sub>n-1</sub>+a<sub>n-p</sub>). Percio\', anche i primi elementi di {a<sub>n</sub>} fanno parte del periodo.
<BR>
<BR>- Dimostrero\' di seguito che {a<sub>n</sub>} ha periodo p<sup>2</sup>-1, da cui deriva che a<sub>p<sup>3</sup></sub> = a<sub>p</sub> = -1, in quanto p<sup>3</sup> = p(p<sup>2</sup>-1)+p.
<BR>
<BR>- A questo scopo, definiamo la funzione f(x,y) = a<sub>px+y</sub>, dove x e y sono interi compresi tra 0 e p-1. Ora, l\'idea chiave consiste nel dimostrare che
<BR>[1] f(x,y) = C(x+y,x+1)-C(x+y,y+1),
<BR>dove C(a,b) indica il coefficiente binomiale a!/(b!(a-b)!), con la convenzione che C(a,b)=0 se uno dei fattoriali e\' negativo.
<BR>
<BR>- Per farlo, occorre esaminare il triangolo di Tartaglia modulo p: siccome il termine k-esimo della riga n-esima vale C(n,k) (si dimostra facilmente per induzione), allora tutti i termini della riga p-esima valgono 0, esclusi il primo e l\'ultimo, che valgono 1. Cio\' deriva dal fatto che se k e\' compreso tra 1 e p-1, C(p,k)=p!/(k!(p-k)!), che e\' un multiplo di p perche\' il p a numeratore non puo\' essere annullato dal denominatore, che e\' il prodotto di interi minori di p. Questa riga di 0 (meno gli estermi) genera un triangolo di 0 nel triangolo di Tartaglia, e gli 1 agli estremi generano due file di 1 ai \"lati\" del triangolo di 0.
<BR>Tradotto, significa che:
<BR>[2] C(p+k,j)=0 se 0<=k<=p-2 e k+1<=j<=p-1,
<BR>[3] C(p+k,k)=C(p+k,p)=1 se 0<=k<=p-1.
<BR>
<BR>- Detto questo, la dimostrazione della [1] per induzione e\' automatica (si ricordi che x e y sono compresi tra 0 e p-1):
<BR>se x=0, f(0,y) = a<sub>y</sub> = y = C(y,1)-C(y,y+1), e la [1] e\' verificata (i primi p valori della successione sono dati dal problema).
<BR>La verifica per f(1,0) e\' immediata, perche\' f(1,0) = a<sub>p-1</sub>+a<sub>0</sub> = -1 = C(1,2)-C(1,1).
<BR>Se y=0, e supponendo la [1] vera fino ad un certo x-1 (con 2<=x<=p-1), allora f(x,0) = a<sub>px</sub> = a<sub>p(x-1)+p-1</sub>+a<sub>p(x-1)</sub> = f(x-1,p-1)+f(x-1,0) = C(p+x-2,x)-C(p+x-2,p)+C(x-1,x)-C(x-1,1) = 0-1+0-(x-1) = -x = C(x,x+1)-C(x,1), e la [1] e\' verificata (nell\'esplicitare i binomiali, abbiamo usato la [2] e la [3], prendendo k=x-2 e j=x).
<BR>In tutti gli altri casi, la verifica e\' ancora piu\' semplice: f(x,y) = f(x-1,y)+f(x,y-1) = C(x+y-1,x)-C(x+y-1,y+1)+C(x+y-1,x+1)-C(x+y-1,y) = C(x+y,x+1)-C(x+y,y+1) (ho usato la nota formula C(n,k)+C(n,k+1) = C(n+1,k+1)).
<BR>La [1] e\' cosi\' dimostrata per induzione.
<BR>
<BR>- Notiamo che f(x,y) e\' antisimmetrica rispetto alle 2 variabili, ovvero f(x,y)=-f(y,x). Infatti, f(x,y)+f(y,x) = C(x+y,x+1)-C(x+y,y+1)+C(y+x,y+1)-C(y+x,x+1) = 0.
<BR>
<BR>- Possiamo ora usare la [1] per calcolare gli a<sub>p<sup>2</sup>-p+y</sub> = a<sub>p(p-1)+y</sub> = f(p-1,y), con y compreso tra 0 e p-1:
<BR>per l\'antisimmetria, se y=0, allora f(p-1,0) = -f(0,p-1) = 1.
<BR>Sempre per l\'antisimmetria, se y=p-1, allora f(p-1,p-1) = -f(p-1,p-1), da cui f(p-1,p-1) = 0.
<BR>Per 1<=y<=p-2, vale f(p-1,y) = C(p+y-1,p)-C(p+y-1,y+1) = 1-0 = 1 (ho usato ancora la [2] e la [3] con k=y-1 e j=y+1).
<BR>
<BR>- Dunque, a<sub>p(p-1)+y</sub> = 1 per 0<=y<=p-2, e a<sub>p(p-1)+p-1</sub> = 0. Questo basta per concludere che {a<sub>n</sub>} ha periodo p<sup>2</sup>-1, perche\' abbiamo trovato nella successione p-1 volte 1 seguiti da uno 0, che sara\' quindi seguito da 1, 2, 3, ..., p-1, ripetendo i primi p valori della successione.
<BR>
<BR>- Allora {a<sub>n</sub>} ha periodo p<sup>2</sup>-1 e quindi, come detto sopra, a<sub>p<sup>3</sup></sub> = -1.
<BR>
<BR><!-- BBCode Start --><IMG SRC="
http://images.google.it/images?q=tbn:3g ... onspir.jpg"><!-- BBCode End --><BR><BR>[ Questo Messaggio è stato Modificato da: Antimateria il 13-12-2003 20:15 ]
