da TomSawyer » 22/01/2007, 17:13
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)$.
I watched a snail crawl along the edge of a straight razor. That's my dream. That's my nightmare. Crawling, slithering, along the edge of a straight... razor... and surviving., Walter E. Kurtz