Successione con numeri primi

[Gi81]

Ho trovato su internet il seguente quesito:


"Sia data la seguente successione

$a_0=3$
$a_1=0$
$a_2=2$

$a_n= a_(n-2)+a_(n-3)$

Dimostrare che $AA p$ primo, $p$ divide $a_p$."

Ho provato a impostare qualcosa, ma non mi è venuto fuori nulla di significativo.
La propongo a voi... Così sicuramente si arriverà alla soluzione


Ho notato che
$a_3= 3$
$a_4=2$
$a_5=5$
$a_6=5$
$a_7=7$
...
$a_11= 22$
...
$a_13=39$
...
$a_17=119$
...
$a_19=209$
...
$a_23=644$
...
$a_29=3480$

Eccetera.... quindi sembra venire (ovviamente non ho dimostrato nulla)

L'unica cosa che ho notato è la seguente:


$a_n -a_(n-1)= a_(n-2) + a_(n-3) - (a_(n-3) + a_(n-4)) = a_(n-2) - a_(n-4)$

cioè $a_n -a_(n-1)= a_(n-2) - a_(n-4)$

Non so se servirà a qualcosa, ma non sono riuscito a fare molte altre considerazioni

Grazie in anticipo per i consigli (o per la dimostrazione completa) che darete

[Gi81]

Ancora nessuno? I casi sono 2

1) l'esercizio è troppo banale e non perdete nemmeno tempo a scriverne lo svolgimento (spero sia questo )
2) l'esercizio è troppo difficile

Davvero... nessuna idea?

[Studente Anonimo]

Problema molto interessante. Non mi sembra facile, così a occhio. C'è tutta una teoria generale per queste cosiddette "equazioni alle differenze", ma non sembra essere molto utile in questo caso. Un'altra idea potrebbe essere ridurre modulo p e vedere se succede qualcosa, ma ci devo pensare un po'.

[Rggb1]

Anche a me sembra abbastanza complicato, più di quanto sembri ad un primo approccio. Una curiosità: dove l'hai trovato?

[Gi81]

"Rggb":Anche a me sembra abbastanza complicato, più di quanto sembri ad un primo approccio. Una curiosità: dove l'hai trovato?

L'ho trovato 3/4 mesi fa su Yahoo Answers [sezione "Matematica", ovviamente]
Quello che ha postato la domanda non ha ricevuto alcuna risposta, e se non ricordo male, l'ha cancellata... Io ho provato a farlo ma, come detto prima, non ho ottenuto molto

[Umby2]

"Rggb":Anche a me sembra abbastanza complicato, più di quanto sembri ad un primo approccio. Una curiosità: dove l'hai trovato?

Si tratta della sequenza di Perrin.
Trovi diversi link su google ricercando "Perrin sequence".

Anche su Wikipedia se ne parla

[a_g_t]

Ho trovato questo in uno dei miei libri dopo sapere che si chiamava "sequenza di Perrin":

Now we prove that if $p$ is a prime, then $p$ divides $a_p$ . The characteristic polynomial of the sequence is $x^3 -x -1 = 0$, with roots, say, $a$, $b$, and $c$. We find that the general term is
$a_n = a^n + b^n + c^n$. The simplicity of this general term is one of the nice traits of Perrin's sequence. Let $p$ be a prime. Then, since $a + b + c = 0$, we have $0 = (a + b + c)^p = a^p + b^p + c^p + ps$, where $s$ is a symmetric polynomial (with integer coefficients) in $a, b, c$. Hence, by the fundamental theorem of symmetric polynomials (see Bonus), $s$ is a polynomial in the elementary symmetric polynomials in $a, b, c$. The elementary symmetric polynomials are $a + b + c$, $ab + bc + ca$, and $abc$. These expressions are given by the coefficients of the characteristic polynomial of the recurrence relation: $x^3 - x -1 = (x - a)(x - b)(x - c) = x^3 - (ab + bc + ca)x^2 + (a + b + c)x - abc$. Since the characteristic polynomial has integer coefficients, $s$ is an integer. It follows that $p$ divides $a_p$.

Prima di trovarlo, ero riuscita a risolvere il problema senza aiuto, e avevo trovato la stessa soluzione (ma ho fatto tutti i dettagli). Mi sono divertita un sacco!

[Rggb1]

Ganzo

[Studente Anonimo]

We find that the general term is $a_n = a^n + b^n + c^n$.

E questo è stato abilmente dato per scontato

[a_g_t]

Possiamo scrivere $a_n=xa^n+yb^n+zc^n$, vediamo che $x=y=z=1$:

$n=0$: $x+y+z=3$; $n=1: xa+yb+zc=0$; $n=2: xa^2+yb^2+zc^2=2$

$a+b+c=0, ab+bc+ca=-1, abc=1$, quindi $a^2+b^2+c^2=(a+b+c)^2-2(ab+bc+ca)=2$

Allora $(x-1)+(y-1)+(z-1)=a(x-1)+b(y-1)+c(z-1)=a^2(x-1)+b^2(y-1)+c^2(z-1)=0$

Il vettore $(x-1, y-1, z-1)$ è ortogonale a $(1, 1, 1)$, $(a, b, c)$, $(a^2,b^2, c^2)$

$a \ne b, a \ne c, b \ne c$ ($a \in RR , b, c \in CC-RR , c=\bar(b)$)

$det( (1,1,1) , (a,b,c) , (a^2,b^2,c^2) ) = (b-a)(c-a)(c-b) \ne 0$ (Vandermonde)

Quindi $(x-1,y-1,z-1)=(0,0,0)$

[Studente Anonimo]

Convinto

In pratica l'idea è che detti $a,b,c$ gli autovalori, $a^p+b^p+c^p = (a+b+c)^p = 0$ modulo $p$, per Frobenius - essendo $a+b+c$ il coefficiente del termine di secondo grado del polinomio associato $x^3-x-1$ ($=(x-a)(x-b)(x-c)$), cioè $0$.

[a_g_t]

Per chi non conosca Frobenius:

$f_{(i,j,k)}(X,Y,Z)=\sum_{\sigma \in S(\{i,j,k\})} X^{\sigma (i)}Y^{\sigma (j)}Z^{\sigma (k)} \in ZZ$

$0=(a+b+c)^n=\sum_{((0 \leq i \leq j \leq k \leq n),(i+j+k=n))} \frac{n!}{i!j!k!} f_{(i,j,k)}(a,b,c)$

($\frac{n!}{i!j!k!}=((n),(i))$ . $((n-i),(j)) \in NN$)



$n=p$ primo:

$\frac{p!}{0!+0!+p!} f_{(0,0,p)}(a,b,c)=a^p+b^p+c^p$

$\forall (i,j,k) \ne (0,0,p), p$ | $\frac{p!}{i!j!k!}$

($0\leq \cdots \leq i \leq \cdots \leq j \leq \cdots \leq k < p$ e $p$ è primo, quindi $i!j!k!$ | $(p-1)!$)