153. disuguaglianza con fibonacci

[jordan]

Own (mix di fatti noti). Per ogni intero positivo n sia d(n) il numero di divisori di n e $f_n$ l'n-esimo numero di fibonacci. Dimostrare che
\[ d\left(\frac{f_1^2+f_2^2+...+f_n^2}{f_n}\right) \ge d(n+1)-1 \]

[dario2994]

$ d\left(\frac{f_1^2+f_2^2+f_3^2}{f_3}\right)=d\left(\frac{1^2+1^2+2^2}{2}\right)=d(3)=2<3=d(3+1) $

[Lasker]

Per prima cosa dimostro per induzione il lemma (in realtà fatto noto) sulla somma dei quadrati dei numeri di Fibonacci:
Lemma quadrati:$\sum_{k=1}^n {F_k}^2=F_nF_{n+1}$
1) Per $n=1$ è banalmente verificato
2)Passo induttivo:
$$\sum_{k=1}^n {F_k^2}+F_{n+1}^2=F_nF_{n+1}+F_{n+1}^2$$
$$\sum_{k=1}^{n+1} {F_k^2}=F_{n+1}(F_n+F_{n+1})$$
Per definizione dei numeri di Fibonacci vale $F_n+F_{n+1}=F_{n+2}$, dunque il lemma si può dire dimostrato .
Ora, sostituisco la relazione del "Lemma quadrati" nella disuguaglianza di partenza, ottenendo:
$$d\left(F_{n+1}\right)\geq d(n+1)-1$$
Per concludere, mi servo del seguente teorema:
Teorema di "divisibilità":se $r\mid s $, allora $F_r\mid F_s$
Dunque, se $n+1$ ha come divisori $(a_1,a_2,...,a_i)$, allora $F_{n+1}$ ha sicuramente come divisori $(F_{a_1},...,F_{a_i})$, che sono tutti diversi, a parte il caso particolare $F_1=F_2=1$.
Dunque ne posso sempre trovare almeno $d(n+1)-1$, che è proprio la tesi.

Testo nascosto:

Lo so che ho fortemente imbrogliato sul secondo teorema, ma è citato su wikipedia, e non so come dimostrarlo

EDIT:ho cambiato la parte confusionaria in cui pretendevo di aver dimostrato una cosa falsa

[Triarii]

Beh veramente il tuo metodo credo non funzioni ogni volta che hai $ f_a $ con $ a $ pari, visto che stai considerando anche $ f_2=f_1=1 $ come divisori, e non solo in quel caso. Dovresti trovare un altro divisore.

[jordan]

No, triari, quel -1 c'e' apposta.

[edit]

[Triarii]

Non avevo visto che avevi editato sorry

[jordan]

Lasker, non hai fortemente imbrogliato: prova prima a mostrare che \[ f_{a+b}=f_{a-1}f_b+f_af_{b+1}\] e poi vedi come questo implica ciò che ti serve..

[Lasker]

Ok, faccio il tentativo!
$$F_{a+b}=F_{a-1}F_{b}+F_{a}F_{b+1}$$
Ora vado di induzione su $b$
1)Passo base:$b=1$ (due casi base, $b=F_1$ e $b=F_2$)
$F_{a+1}=F_{a-1}+F_{a}$, che è vero per definizione dei numeri di Fibonacci.
2)Passo induttivo:
$F_{a+b}+F_{a+b-1}=(F_{a-1}F_{b}+F_{a}F_{b+1})+(F_{a-1}F_{b-1}+F_{a}F_{b})$
$ F_{a+b+1}=F_{a}(F_b+F_{b+1})+F_{a-1}(F_b+F_{b-1})$
Sostituendo nelle parentesi, ottengo:
$F_{a+b+1}=F_{a-1}F_{b+1}+F_{a}F_{b+2}$, che è la tesi.
A questo punto, provo a dimostrare il mistico "teorema di divisibilità":

Procedo usando la relazione precedente, per dimostrare che $r\mid {r+s} \Rightarrow F_r\mid F_{r+s}$ per ogni $s,r$.
$F_{r+s}=F_{r-1}F_{s}+F_{r}F_{s+1}=F_r(k_1F_{r-1}+F_{s+1})$
Da cui, $r\mid r+s$ è condizione sufficiente per la quale $F_r\mid F_{r+s}$.
Dunque dovrei aver concluso la dimostrazione (si spera )

[jordan]

Apposto, vai col prossimo

[Drago96]

Io invece "imbroglio" davvero e dico che
$$\displaystyle d(F_n)\ge2^{\Omega(n) }$$
Dove $\displaystyle\Omega\left(p_1^{\alpha_1}\cdots p_k^{\alpha_k}\right):=\alpha_1+\dots+\alpha_k$
In realtà ci vorrebbe un $-1$ all'esponente in alcuni (infiniti ) casi, ma sono piuttosto sicuro che si possa omettere tranne che con $n=4$...

[jordan]

come lo dimostri?

[<enigma>]

come lo dimostri?

Io ho usato $F_k|F_{kn}$+il teorema di Carmichael

[Drago96]

Esatto!
Io l'avevo fatto spezzando sulle potenze di primi (ovvero scrivendo $\displaystyle F(p_1^{\alpha_1}\cdots p_k^{\alpha_k})=h\cdot F(p_1^{\alpha_1})\cdots F(p_k^{\alpha_k})$ ) e poi mostrando il fatto sulle potenze dei primi e usando il fatto sul gcd... però mi accorgo che in effetti basta continuare a togliere primi e quindi divisori primitivi... xD

Tra l'altro alla pagina di wiki c'è anche un link ad una dimostrazione che mi pare del tutto elementare...

EDIT: vorrei anche fare notare a Lasker che il lemma dei quadrati ha anche una bella interpretazione geometrica, ovvero nientemeno che la costruzione della spirale aurea!

[jordan]

Uh, figo, non lo conoscevo! Sa molto di generalizzazione di Zsigmondy per classi di sequenze $(a_n)_{n \in \mathbb{N}_0}$ della forma $a_{n+2}=\alpha a_{n+1}+\beta a_n$. Per la disuguaglianza di sopra, direi che hai considerato solo divisori della forma $f_d$ con $\omega(d)=1$, ma dimenticato le 3 eccezioni del teorema, e dovrebbe quindi essere della forma $\sigma_0(f_n) \ge 2^{\Omega(n)-4}$ Il fatto che $(f_n)_{n \in \mathbb{N}_0}$ è una sequenza di Mersenne non mi pare sia utilizzato (premesso che non conosco la dimostrazione del teorema di Carmichael); l'insieme degli $f_d$ con $d\mid n$ è un sottoinsieme dell'insieme dei divisori di $f_n$. Bene, mettiamoli in ordine crescente. Nel caso peggiore $n$ è pari, cosicchè $f_1=f_2=1$ e questo sottoinsieme dei divisori di $f_n$ avrà almeno $\sigma_0(n)-1$ elementi distinti. Tra questi ultimi, apparte le tre eccezioni dei teorema di sopra, esiste sempre un divisore primitivo. Questo mostra che, nel caso peggiore, il numero di fattori di $f_n$ (con $n\ge 12$) verifica $\omega(f_n) \ge \sigma_0(n)-4$. A sua volta, implica \[ \sigma_0(f_n) \ge 2^{\sigma_0(n)-4} \ge 2^{2^{\omega(n)}-4}, \]
che è piu' forte di quella di sopra. Ho fallato da qualche parte?

[Drago96]

Woo! Sì, direi che il tuo bound funziona e surclassa il mio!
Io infatti considero solo roba coprima (Fibonacci delle potenze dei primi) mentre in realtà ogni divisore porta un nuovo fattore!

Ah, nel mio non devo considerare le eccezioni perché non sono potenze di primi, e io come ho detto prima scompongo in prodotto di Fibonacci di potenze di primi per spezzare la funzione dei divisori e con l'induzione dire che $\sigma_0(F_{p^k})\ge2^k$ tranne nel caso del 2, in cui ci va appunto il -1...

P.S: mi scuso se è poco chiaro, ma dal telefono non sono troppo comodo a scrivere con LaTeX...