Fibonacci: $f_n + 1$ è composto, se $n \ge 4$.

[DavidHilbert]

Sia $f_{n+2} = f_{n+1} + f_n$, per ogni $n \in NN$, con $f_0 = 0$ ed $f_1 = 1$. Dimostrare che $f_n + 1$ è composto, per ogni intero $n \ge 4$.

[Aethelmyth]

Un numero composto non è un numero naturale che ha almeno un altro divisore oltre a 1 e sé stesso? fibonacci è 0,1,1,2,3,5,8,13 etc. . $f_5$ non mi sembra composto..

[elgiovo]

Infatti David Hilbert chiedeva di verificare se $f_n+1$ è composto, non se lo è $f_(n+1)$.

[DavidHilbert]

Sì, è come dice elgiovo.

[TomSawyer]

La mia soluzione non è molto bella, ma eccola.

Chiaramente vanno presi in considerazione solo gli $f_n$ pari, cioè quelli di indice $3m$.

Dato che $f_n=f_(k+1)f_(n-k)+f_(k)f_(n-k-1)$. Per $m$ dispari si ha $f_(3m)=f_((3m-1)/2)^2+f_((3m+1)/2)^2$, e per $m$ pari $f_(3m)=f_(3m/2+1)f_(3m/2)+f_(3m/2)f_(3m/2-1)$.

Considero prima il caso in cui $m$ è dispari. Vogliamo mostrare che $f_(3m)+1$ è sempre divisibile per $f_((3m+1)/2)$, cioè che $f_((3m+1)/2)|f_((3m-1)/2)^2+1$. Per qualsiasi $m in NN^+$ si ha che (*) $f_m^2=f_(m-1)f_(m+1)-(-1)^m$. Quindi $f_((3m-1)/2)^2=f_((3m-3)/2)f_((3m+1)/2)-1-=-1(modf_((3m+1)/2))$. E con $m$ dispari abbiamo finito.

Ora sia $m$ pari. Mostrerò che $f_(3m)+1=f_(3m/2+1)f_(3m/2)+f_(3m/2)f_(3m/2-1)+1$ è sempre divisibile o per $f_(3m/2+1)$ o per $f_(3m/2-1)$. Raccogliendo otteniamo (**) $f_(3m)+1=f_(3m/2)(f_(3m/2-1)+f_(3m/2+1))+1$. Ora ci sono due casi: i)$3m/2$ pari e ii)$3m/2$ dispari. Nel primo caso, scriviamo la (**) $f_(3m/2)(f_(3m/2-1)+f_(3m/2-1)+f_(3m/2))+1=2f_(3m/2-1)f_(3m/2)+f_(3m/2)^2+1$ che, sfruttando la (*), diventa $2f_(3m/2-1)f_(3m/2)+f_(3m/2-1)f_(3m/2+1)-1+1$, che è divisibile per $f_(3m/2-1)$. Nel secondo caso, scriviamo la (**) $f_(3m/2)(f_(3m/2+1)-f_(3m/2)+f_(3m/2+1))$, che sviluppando e utilizzando di nuovo la (*) diventa $2f_(3m/2+1)f_(3m/2)-f_(3m/2-1)f_(3m+1)-1+1$, che è divisibile per $f_(3m/2+1)$.

[DavidHilbert]

Considero prima il caso in cui $m$ è dispari. [...] Per qualsiasi $m in NN^+$ si ha [...] $f_m^2=f_(m-1)f_(m+1)-(-1)^m$. Quindi $f_((3m-1)/2)^2=f_((3m-3)/2)f_((3m+1)/2)-1-=-1(modf_((3m+1)/2))$.

No, casomai si ha $f_((3m-1)/2)^2 \equiv -(-1)^{(3m-1)/2}$ mod $f_((3m+1)/2))$.

[TomSawyer]

A me risulta quello che ho scritto, non capisco. Il mio intento è di dimostrare che $f_((3m-1)/2)^2+1$ è divisibile per $f_((3m+1)/2)$, perché, poi raccogliendo, si ha che $f_(3m)+1$ è composto, per $m$ dispari. Dato che $f_((3m-1)/2)^2=f_((3m-1)/2-1)f_((3m-1)/2+1)-(-1)^((3m-1)/2)=f_((3m-1)/2-1)f_((3m-1)/2+1)-1$, e sommandoci $1$ diventa divisibile per $f_((3m+1)/2)$

[DavidHilbert]

@Crook: hai scritto che, per ogni $n \in NN$: $f_n^2 = f_(n-1)f_(n+1)-(-1)^n$ (identità di Cassini). Se adesso supponi m = 1 mod 2 e assumi di conseguenza n = (3m-1)/2, la relazione precedente assume la forma $f_{(3m-1)/2}^2 = f_{(3m-3)/2}f_{(3m+1)/2}-(-1)^{(3m-1)/2}$. E poiché (3m-1)/2 potrebbe essere, in linea di principio, sia pari che dispari, non ti è permesso scrivere quel che viceversa hai scritto.

EDIT: l'italiano.

[TomSawyer]

Sì, ho assunto stupidamente che $n=(3m-1)/2$ fosse pari. Dividiamo i casi anche qui: se $(3m-1)/2$ è pari, allora è come ho detto sopra; altrimenti $(3m-1)/2+1$ è pari ed, essendo che $f_(3m)=f_((3m-1)/2)^2+f_((3m-1)/2^2+1)$, si ha che $f_((3m-1)/2+1)^2+1=f_((3m-1)/2)f_((3m-1)/2+2)-1+1$, quindi divisibile per $f_((3m-1)/2)$.

E con questo i casi sono finiti. Se tu hai una soluzione più elegante, la posti?

[DavidHilbert]

Vale $f_n^4 - f_{n-2} f_{n-1} f_{n+1} f_{n+2} = 1$, per ogni $n \in NN$ (identità di Gelin-Cesàro). Da qui $(f_n - 1)(f_n + 1)(f_n^2 + 1) = f_{n-2} f_{n-1} f_{n+1} f_{n+2}$. Per assurdo, $f_n + 1$ sia primo, per $n \ge 4$. Allora $f_n + 1$ divide l'uno o l'altro fra $f_{n+1}$ ed $f_{n+2}$ (lemma di Euclide). Senonché questa condizione si riconosce assurda senza particolari difficoltà.