Successione con numeri primi

[Gi8]

Ho trovato su internet il seguente quesito:


"Sia data la seguente successione

\( \displaystyle {a}_{{0}}={3} \)
\( \displaystyle {a}_{{1}}={0} \)
\( \displaystyle {a}_{{2}}={2} \)

\( \displaystyle {a}_{{n}}={a}_{{{n}-{2}}}+{a}_{{{n}-{3}}} \)

Dimostrare che \( \displaystyle \forall{p} \) primo, \( \displaystyle {p} \) divide \( \displaystyle {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
\( \displaystyle {a}_{{3}}={3} \)
\( \displaystyle {a}_{{4}}={2} \)
\( \displaystyle {a}_{{5}}={5} \)
\( \displaystyle {a}_{{6}}={5} \)
\( \displaystyle {a}_{{7}}={7} \)
...
\( \displaystyle {a}_{{11}}={22} \)
...
\( \displaystyle {a}_{{13}}={39} \)
...
\( \displaystyle {a}_{{17}}={119} \)
...
\( \displaystyle {a}_{{19}}={209} \)
...
\( \displaystyle {a}_{{23}}={644} \)
...
\( \displaystyle {a}_{{29}}={3480} \)

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

L'unica cosa che ho notato è la seguente:


\( \displaystyle {a}_{{n}}-{a}_{{{n}-{1}}}={a}_{{{n}-{2}}}+{a}_{{{n}-{3}}}-{\left({a}_{{{n}-{3}}}+{a}_{{{n}-{4}}}\right)}={a}_{{{n}-{2}}}-{a}_{{{n}-{4}}} \)

cioè \( \displaystyle {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

[Gi8]

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?

[Martino]

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'.

[Rggb]

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

[Gi8]

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

[Umby]

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":

Testo nascosto, fai click qui per vederlo

Now we prove that if \( \displaystyle {p} \) is a prime, then \( \displaystyle {p} \) divides \( \displaystyle {a}_{{p}} \) . The characteristic polynomial of the sequence is \( \displaystyle {{x}}^{{3}}-{x}-{1}={0} \), with roots, say, \( \displaystyle {a} \), \( \displaystyle {b} \), and \( \displaystyle {c} \). We find that the general term is
\( \displaystyle {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 \( \displaystyle {p} \) be a prime. Then, since \( \displaystyle {a}+{b}+{c}={0} \), we have \( \displaystyle {0}={{\left({a}+{b}+{c}\right)}}^{{p}}={{a}}^{{p}}+{{b}}^{{p}}+{{c}}^{{p}}+{p}{s} \), where \( \displaystyle {s} \) is a symmetric polynomial (with integer coefficients) in \( \displaystyle {a},{b},{c} \). Hence, by the fundamental theorem of symmetric polynomials (see Bonus), \( \displaystyle {s} \) is a polynomial in the elementary symmetric polynomials in \( \displaystyle {a},{b},{c} \). The elementary symmetric polynomials are \( \displaystyle {a}+{b}+{c} \), \( \displaystyle {a}{b}+{b}{c}+{c}{a} \), and \( \displaystyle {a}{b}{c} \). These expressions are given by the coefficients of the characteristic polynomial of the recurrence relation: \( \displaystyle {{x}}^{{3}}-{x}-{1}={\left({x}-{a}\right)}{\left({x}-{b}\right)}{\left({x}-{c}\right)}={{x}}^{{3}}-{\left({a}{b}+{b}{c}+{c}{a}\right)}{{x}}^{{2}}+{\left({a}+{b}+{c}\right)}{x}-{a}{b}{c} \). Since the characteristic polynomial has integer coefficients, \( \displaystyle {s} \) is an integer. It follows that \( \displaystyle {p} \) divides \( \displaystyle {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!

[Rggb]

Ganzo

[Martino]

We find that the general term is \( \displaystyle {a}_{{n}}={{a}}^{{n}}+{{b}}^{{n}}+{{c}}^{{n}} \).

E questo è stato abilmente dato per scontato

[a_g_t]

Testo nascosto, fai click qui per vederlo

Possiamo scrivere \( \displaystyle {a}_{{n}}={x}{{a}}^{{n}}+{y}{{b}}^{{n}}+{z}{{c}}^{{n}} \), vediamo che \( \displaystyle {x}={y}={z}={1} \):

\( \displaystyle {n}={0} \): \( \displaystyle {x}+{y}+{z}={3} \); \( \displaystyle {n}={1}:{x}{a}+{y}{b}+{z}{c}={0} \); \( \displaystyle {n}={2}:{x}{{a}}^{{2}}+{y}{{b}}^{{2}}+{z}{{c}}^{{2}}={2} \)

\( \displaystyle {a}+{b}+{c}={0},{a}{b}+{b}{c}+{c}{a}=-{1},{a}{b}{c}={1} \), quindi \( \displaystyle {{a}}^{{2}}+{{b}}^{{2}}+{{c}}^{{2}}={{\left({a}+{b}+{c}\right)}}^{{2}}-{2}{\left({a}{b}+{b}{c}+{c}{a}\right)}={2} \)

Allora \( \displaystyle {\left({x}-{1}\right)}+{\left({y}-{1}\right)}+{\left({z}-{1}\right)}={a}{\left({x}-{1}\right)}+{b}{\left({y}-{1}\right)}+{c}{\left({z}-{1}\right)}={{a}}^{{2}}{\left({x}-{1}\right)}+{{b}}^{{2}}{\left({y}-{1}\right)}+{{c}}^{{2}}{\left({z}-{1}\right)}={0} \)

Il vettore \( \displaystyle {\left({x}-{1},{y}-{1},{z}-{1}\right)} \) è ortogonale a \( \displaystyle {\left({1},{1},{1}\right)} \), \( \displaystyle {\left({a},{b},{c}\right)} \), \( \displaystyle {\left({{a}}^{{2}},{{b}}^{{2}},{{c}}^{{2}}\right)} \)

\( \displaystyle {a}\ne{b},{a}\ne{c},{b}\ne{c} \) (\( \displaystyle {a}\in\mathbb{R},{b},{c}\in\mathbb{C}-\mathbb{R},{c}={\overline{{{b}}}} \))

\( \displaystyle {\det{{\left(\matrix{{1}&{1}&{1}\\{a}&{b}&{c}\\{{a}}^{{2}}&{{b}}^{{2}}&{{c}}^{{2}}}\right)}}}={\left({b}-{a}\right)}{\left({c}-{a}\right)}{\left({c}-{b}\right)}\ne{0} \) (Vandermonde)

Quindi \( \displaystyle {\left({x}-{1},{y}-{1},{z}-{1}\right)}={\left({0},{0},{0}\right)} \)