Fibonacci: $f_n + 1$ è composto, se $n \ge 4$.
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$.
Risposte
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..
Infatti David Hilbert chiedeva di verificare se $f_n+1$ è composto, non se lo è $f_(n+1)$.
Sì, è come dice elgiovo.
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)$.
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)$.
"Crook":
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))$.
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)$
@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.
EDIT: l'italiano.
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?
E con questo i casi sono finiti. Se tu hai una soluzione più elegante, la posti?
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à.
Mille volte più facile con l'identità di Gelin-Cesàro, che non conoscevo proprio.
Decisamente.
Mi sono impuntato cercando di dimostrare la tesi a partire dalla formula di Binet $f_n=1/sqrt5 {((1+sqrt5)/2)^n-((1-sqrt5)/2)^n}$.
Sviluppando le potenze nella parentesi graffa con il binomio di Newton, si trova l'identità $f_n=1/2^(n-1) sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k$ (sapete se esiste già?).
Ora, $f_n+1=2^(1-n)[ sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k+2^(n-1)]=2^(1-n)[ sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k+sum_(k=0)^(n-1)((n-1),(k))]$.
Ogni coefficiente binomiale della prima sommatoria si può accoppiare con uno o più coefficienti binomiali della prima e della seconda: a questo proposito si ricordi che $((n),(k))=((n),(n-k))$.
Ad esempio, se $n=6$, $f_6=2^(-5)[ ((6),(1))5^0+((6),(3))5^1+((6),(5))5^2+((5),(0))+((5),(1))+((5),(2))+((5),(3))+((5),(4))+((5),(5)) ]=2^(-5)[((6),(1))5^0+((6),(3))5^1+((6),(5))5^2+((6),(1))+((6),(3))+((6),(5))]=2^(-5)[((6),(1))(5^0+5^2+2)+((6),(3))(5^1+1)]$.
Quindi, in generale, nelle quadre ci saranno coefficienti binomiali che raccolgono numeri nella forma $5^i+5^j+2$ o $5^h+1$.
Poichè tali numeri sono sempre pari, dalle quadre possiamo raccogliere $2n!$. Se $n>=4$, i $2$ di $2n!$ si semplificano con quelli di $2^(1-n)=1/2^(n-1)$.
In generale, $f_n+1=2^(1-n)[ sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k+sum_(k=0)^(n-1)(k+1)/n((n),(k+1))]=(n!)/(2^(n-1))[ sum_(k=0)^(|__ (n-1)/2 __|)5^k/((2k+1)!(n-2k-1)!)+1/n sum_(k=0)^(n-1)1/(k!(n-k-1)!)]$
dove, nel penultimo passaggio, si sfrutta il fatto che $((n),(k+1))=n/(k+1) ((n-1),(k))$.
E qui mi impunto, perchè non riesco a mostrare che almeno un numero del prodotto di numeri interi $(2n!)/(2^(n-1))$ non si semplifica, facendo sì che $f_n+1$ sia composto.
Mi sono impuntato cercando di dimostrare la tesi a partire dalla formula di Binet $f_n=1/sqrt5 {((1+sqrt5)/2)^n-((1-sqrt5)/2)^n}$.
Sviluppando le potenze nella parentesi graffa con il binomio di Newton, si trova l'identità $f_n=1/2^(n-1) sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k$ (sapete se esiste già?).
Ora, $f_n+1=2^(1-n)[ sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k+2^(n-1)]=2^(1-n)[ sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k+sum_(k=0)^(n-1)((n-1),(k))]$.
Ogni coefficiente binomiale della prima sommatoria si può accoppiare con uno o più coefficienti binomiali della prima e della seconda: a questo proposito si ricordi che $((n),(k))=((n),(n-k))$.
Ad esempio, se $n=6$, $f_6=2^(-5)[ ((6),(1))5^0+((6),(3))5^1+((6),(5))5^2+((5),(0))+((5),(1))+((5),(2))+((5),(3))+((5),(4))+((5),(5)) ]=2^(-5)[((6),(1))5^0+((6),(3))5^1+((6),(5))5^2+((6),(1))+((6),(3))+((6),(5))]=2^(-5)[((6),(1))(5^0+5^2+2)+((6),(3))(5^1+1)]$.
Quindi, in generale, nelle quadre ci saranno coefficienti binomiali che raccolgono numeri nella forma $5^i+5^j+2$ o $5^h+1$.
Poichè tali numeri sono sempre pari, dalle quadre possiamo raccogliere $2n!$. Se $n>=4$, i $2$ di $2n!$ si semplificano con quelli di $2^(1-n)=1/2^(n-1)$.
In generale, $f_n+1=2^(1-n)[ sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k+sum_(k=0)^(n-1)(k+1)/n((n),(k+1))]=(n!)/(2^(n-1))[ sum_(k=0)^(|__ (n-1)/2 __|)5^k/((2k+1)!(n-2k-1)!)+1/n sum_(k=0)^(n-1)1/(k!(n-k-1)!)]$
dove, nel penultimo passaggio, si sfrutta il fatto che $((n),(k+1))=n/(k+1) ((n-1),(k))$.
E qui mi impunto, perchè non riesco a mostrare che almeno un numero del prodotto di numeri interi $(2n!)/(2^(n-1))$ non si semplifica, facendo sì che $f_n+1$ sia composto.
"elgiovo":
Mi sono impuntato cercando di dimostrare la tesi a partire dalla formula di Binet [...] Sviluppando le potenze nella parentesi graffa con il binomio di Newton, si trova l'identità $f_n=1/2^(n-1) sum_(k=0)^(|__ (n-1)/2 __|)((n),(2k+1))5^k$ (sapete se esiste già?).
Be', di sicuro, visto che io l'ho utilizzata - ormai sono due anni - per dimostrare che, comunque scelto $n \in NN^+$, esiste un intero positivo $m \le 2n$ tale che $n$ divide $f_m$. All'epoca l'articolo finì sulla scrivania di Doug Hensley.
Doug Hensley è sempre il tizio dell'AMM? E' stata anche pubblicata la dimostrazione? Se sì, in che mese?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo